How do I efficiently determine if a polygon is convex, non-convex or complex?

Question

From the man page for XFillPolygon:

• If shape is Complex, the path may self-intersect. Note that contiguous coincident points in the path are not treated as self-intersection.

• If shape is Convex, for every pair of points inside the polygon, the line segment connecting them does not intersect the path. If known by the client, specifying Convex can improve performance. If you specify Convex for a path that is not convex, the graphics results are undefined.

• If shape is Nonconvex, the path does not self-intersect, but the shape is not wholly convex. If known by the client, specifying Nonconvex instead of Complex may improve performance. If you specify Nonconvex for a self-intersecting path, the graphics results are undefined.

I am having performance problems with fill XFillPolygon and, as the man page suggests, the first step I want to take is to specify the correct shape of the polygon. I am currently using Complex to be on the safe side.

Is there an efficient algorithm to determine if a polygon (defined by a series of coordinates) is convex, non-convex or complex?

Solution 1

You can make things a lot easier than the Gift-Wrapping Algorithm... that's a good answer when you have a set of points w/o any particular boundary and need to find the convex hull.

In contrast, consider the case where the polygon is not self-intersecting, and it consists of a set of points in a list where the consecutive points form the boundary. In this case it is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):

For each consecutive pair of edges of the polygon (each triplet of points), compute the z-component of the cross product of the vectors defined by the edges pointing towards the points in increasing order. Take the cross product of these vectors:

 given p[k], p[k+1], p[k+2] each with coordinates x, y:
 dx1 = x[k+1]-x[k]
 dy1 = y[k+1]-y[k]
 dx2 = x[k+2]-x[k+1]
 dy2 = y[k+2]-y[k+1]
 zcrossproduct = dx1*dy2 - dy1*dx2

The polygon is convex if the z-components of the cross products are either all positive or all negative. Otherwise the polygon is nonconvex.

If there are N points, make sure you calculate N cross products, e.g. be sure to use the triplets (p[N-2],p[N-1],p[0]) and (p[N-1],p[0],p[1]).

---

If the polygon is self-intersecting, then it fails the technical definition of convexity even if its directed angles are all in the same direction, in which case the above approach would not produce the correct result.

Solution 2

This question is now the first item in either Bing or Google when you search for "determine convex polygon." However, none of the answers are good enough.

The (now deleted) answer by @EugeneYokota works by checking whether an unordered set of points can be made into a convex polygon, but that's not what the OP asked for. He asked for a method to check whether a given polygon is convex or not. (A "polygon" in computer science is usually defined [as in the XFillPolygon documentation] as an ordered array of 2D points, with consecutive points joined with a side as well as the last point to the first.) Also, the gift wrapping algorithm in this case would have the time-complexity of O(n^2) for n points - which is much larger than actually needed to solve this problem, while the question asks for an efficient algorithm.

@JasonS's answer, along with the other answers that follow his idea, accepts star polygons such as a pentagram or the one in @zenna's comment, but star polygons are not considered to be convex. As @plasmacel notes in a comment, this is a good approach to use if you have prior knowledge that the polygon is not self-intersecting, but it can fail if you do not have that knowledge.

@Sekhat's answer is correct but it also has the time-complexity of O(n^2) and thus is inefficient.

@LorenPechtel's added answer after her edit is the best one here but it is vague.

A correct algorithm with optimal complexity

The algorithm I present here has the time-complexity of O(n), correctly tests whether a polygon is convex or not, and passes all the tests I have thrown at it. The idea is to traverse the sides of the polygon, noting the direction of each side and the signed change of direction between consecutive sides. "Signed" here means left-ward is positive and right-ward is negative (or the reverse) and straight-ahead is zero. Those angles are normalized to be between minus-pi (exclusive) and pi (inclusive). Summing all these direction-change angles (a.k.a the deflection angles) together will result in plus-or-minus one turn (i.e. 360 degrees) for a convex polygon, while a star-like polygon (or a self-intersecting loop) will have a different sum ( n * 360 degrees, for n turns overall, for polygons where all the deflection angles are of the same sign). So we must check that the sum of the direction-change angles is plus-or-minus one turn. We also check that the direction-change angles are all positive or all negative and not reverses (pi radians), all points are actual 2D points, and that no consecutive vertices are identical. (That last point is debatable--you may want to allow repeated vertices but I prefer to prohibit them.) The combination of those checks catches all convex and non-convex polygons.

Here is code for Python 3 that implements the algorithm and includes some minor efficiencies. The code looks longer than it really is due to the the comment lines and the bookkeeping involved in avoiding repeated point accesses.

TWO_PI = 2 * pi

def is_convex_polygon(polygon):
    """Return True if the polynomial defined by the sequence of 2D
    points is 'strictly convex': points are valid, side lengths non-
    zero, interior angles are strictly between zero and a straight
    angle, and the polygon does not intersect itself.

    NOTES:  1.  Algorithm: the signed changes of the direction angles
                from one side to the next side must be all positive or
                all negative, and their sum must equal plus-or-minus
                one full turn (2 pi radians). Also check for too few,
                invalid, or repeated points.
            2.  No check is explicitly done for zero internal angles
                (180 degree direction-change angle) as this is covered
                in other ways, including the `n < 3` check.
    """
    try:  # needed for any bad points or direction changes
        # Check for too few points
        if len(polygon) < 3:
            return False
        # Get starting information
        old_x, old_y = polygon[-2]
        new_x, new_y = polygon[-1]
        new_direction = atan2(new_y - old_y, new_x - old_x)
        angle_sum = 0.0
        # Check each point (the side ending there, its angle) and accum. angles
        for ndx, newpoint in enumerate(polygon):
            # Update point coordinates and side directions, check side length
            old_x, old_y, old_direction = new_x, new_y, new_direction
            new_x, new_y = newpoint
            new_direction = atan2(new_y - old_y, new_x - old_x)
            if old_x == new_x and old_y == new_y:
                return False  # repeated consecutive points
            # Calculate & check the normalized direction-change angle
            angle = new_direction - old_direction
            if angle <= -pi:
                angle += TWO_PI  # make it in half-open interval (-Pi, Pi]
            elif angle > pi:
                angle -= TWO_PI
            if ndx == 0:  # if first time through loop, initialize orientation
                if angle == 0.0:
                    return False
                orientation = 1.0 if angle > 0.0 else -1.0
            else:  # if other time through loop, check orientation is stable
                if orientation * angle <= 0.0:  # not both pos. or both neg.
                    return False
            # Accumulate the direction-change angle
            angle_sum += angle
        # Check that the total number of full turns is plus-or-minus 1
        return abs(round(angle_sum / TWO_PI)) == 1
    except (ArithmeticError, TypeError, ValueError):
        return False  # any exception means not a proper convex polygon

Solution 3

The following Java function/method is an implementation of the algorithm described in this answer.

public boolean isConvex()
{
    if (_vertices.size() < 4)
        return true;

    boolean sign = false;
    int n = _vertices.size();

    for(int i = 0; i < n; i++)
    {
        double dx1 = _vertices.get((i + 2) % n).X - _vertices.get((i + 1) % n).X;
        double dy1 = _vertices.get((i + 2) % n).Y - _vertices.get((i + 1) % n).Y;
        double dx2 = _vertices.get(i).X - _vertices.get((i + 1) % n).X;
        double dy2 = _vertices.get(i).Y - _vertices.get((i + 1) % n).Y;
        double zcrossproduct = dx1 * dy2 - dy1 * dx2;

        if (i == 0)
            sign = zcrossproduct > 0;
        else if (sign != (zcrossproduct > 0))
            return false;
    }

    return true;
}

The algorithm is guaranteed to work as long as the vertices are ordered (either clockwise or counter-clockwise), and you don't have self-intersecting edges (i.e. it only works for simple polygons).

Solution 4

Here's a test to check if a polygon is convex.

Consider each set of three points along the polygon--a vertex, the vertex before, the vertex after. If every angle is 180 degrees or less you have a convex polygon. When you figure out each angle, also keep a running total of (180 - angle). For a convex polygon, this will total 360.

This test runs in O(n) time.

Note, also, that in most cases this calculation is something you can do once and save — most of the time you have a set of polygons to work with that don't go changing all the time.

Solution 5

The answer by @RoryDaulton seems the best to me, but what if one of the angles is exactly 0? Some may want such an edge case to return True, in which case, change "<=" to "<" in the line :

if orientation * angle < 0.0:  # not both pos. or both neg.

Here are my test cases which highlight the issue :

# A square    
assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) )

# This LOOKS like a square, but it has an extra point on one of the edges.
assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) )

The 2nd assert fails in the original answer. Should it? For my use case, I would prefer it didn't.

View more solutions

Comments

[zenna]

Correct me if I am wrong, but won't this fail for some complex polygons? For instance [[1 3] [9 7] [7 9] [7 2] [9 6] [1 8]]]

[emory]

I have no idea what this means. What does it mean for a point to be level, behind, or in front of a line?

[James Hill]

This should clarify things a bit: stackoverflow.com/questions/1560492/…

[plasmacel]

Here is a somewhat related, but easier approach without the need of trigonometric functions: math.stackexchange.com/questions/1743995/…

[Rory Daulton]

@plasmacel: That approach, like JasonS's answer, accepts star polygons such as a pentagram or the one in zenna's comment. If star polygons are acceptable, that is indeed better than my approach, but star polygons are not usually considered to be convex. This is why I took the time to write and test this function that rejects star polygons. Also, thanks for your edit--it did improve my answer. However, you did change the meaning of one sentence, so I'm editing that again--I hope it is more clear this time.

[plasmacel]

Star polygons are non just non-convex, but also self-intersecting. Your answer may extend the test to handle self-intersecting polygons correctly (good to have such a solution), however if only non-self-intersecting simple polygons are considered, then the mixed product (called zcrossproduct by @Jason) approach is preferable.

[Rory Daulton]

@plasmacel: Good point that JasonS's approach is good if you have prior knowledge that the polygon is not self-intersecting. I wanted to focus on the "convex" issue, which is what others were also focusing on. I also wanted a function that makes no assumptions at all on the polygon--my routine even checks that the "points" in the array actually are structures containing two values, i.e. point coordinates.

[plasmacel]

Nice. I linked your answer in a comment on the math.SE answer math.stackexchange.com/a/1745427/207654.

[Will Ness]

amazingly wrong answer, with all these upvotes. self-intersecting loop will pass this algorithm with flying colors.

[Will Ness]

there is no prior knowledge about (non-)self-intersection here. The Q explicitly asks for the test. all the deflections (the pun) about it here are hot air. --- signed change of direction is a.k.a. the deflection angle. indeed, just test that all have same sign (and they all are by definition <= 180 d, so Loren's answer is more than just being vague - it is incomprehensible on the face of it), and their sum total is = 360 d (you DO check this in code, but don't seem to mention this in the text itself!!). consecutive identical vertices are allowed BTW, just need to be dealt with specially.

[Will Ness]

(the deflections in the comments; not by you of course). BTW for the "star" i.e. looping "pseudo-convex" polygons the sum total of deflection angles will be 360 * n degrees, where n is the number of "turns". --- +1 but I think you really should add the test for 360d into the text more clearly. --- (isn't it just a huge shame though, this whole debacle of a Q&A here??)

[Rory Daulton]

@WillNess: I edited my answer to emphasize that my algorithm checks for plus-or-minus one turn (360 degrees). I also note that some users may prefer to allow repeated consecutive vertices. I prefer to prohibit them, for several reasons.

[Discrete lizard]

This is very vague. This isn't an algorithm. Could you expand and explain without vague links and simply edit the answer?

[Discrete lizard]

Ah, the edge cases. Good to see that you're taking care of them! Algorithms researchers tend to ignore those (as this is really implementation). The general problem here is that most geometric primitives are inexact, so '<=' and '<' are expected to have the same behaviour! However, implementing geometrical algorithms correctly is, for this reason, very hard.

[Nominal Animal]

@RoryDaulton: I'm the author of the aforementioned answer to another question, but missed the notes here! I rewrote that answer; please re-compare to yours. To account for self-intersecting (bowtie or star-shaped, for example) polygons, it is sufficient to calculate the number of sign changes (ignoring zero as if it had no sign) in the edge vectors' $x$ and $y$ components; there are exactly two, each, for a convex polygon. atan2() is slow. I can provide a Python implementation too, if desired, for comparison.

[Jason S]

I have updated this answer. Commenters are correct that it doesn't address the complex case, but it still has value.

[TurnipEntropy]

It only addresses part of the question, this is true. That's why it wasn't accepted. Other people have obviously found this question and been able to guarantee they don't have the complex case, thus found this answer useful.

[Qinqing Liu]

Hi, I am just not sure why when angle equal to 0, we should return False. According to the definition of convex, it could be convex. Thank you!

[Rory Daulton]

@QinqingLiu: As the docstring in my code states, I am checking for 'strictly convex' polygons, which is more "strict" than just 'convex'. In particular, for my code I want any point on an open line segment that joins two points on the polygon's border to be in the interior of the polygon. I allow a zero angle, such a point will end up on the border of the polygon. You may want to allow that, but I did not. My code should be easy to change if you want to allow zero angles.

[Qinqing Liu]

@RoryDaulton Why the angle can be equal to PI then? Will this introduce a single line that outside of the polygon? (In your definition, the angles for Equilateral triangle is 2/3 * PI instead of 1/3 * PI, am I understanding right?)

[Rory Daulton]

@QinqingLiu: My docstring states "interior angles are strictly between zero and a straight angle", so an angle of Pi is also not allowed. That angle, like a zero angle, will allow a line-segment point to be on the border rather than in the interior. Remember that the "angles" I discuss are turning angles, not the polygon angles--the absolute values of the two are supplementary (the sum equals Pi radians or 180°). So yes, an equilateral triangle has turning angles of 2/3*Pi radians or 120°, or the negative of that, depending on the direction of the turn.

[Qinqing Liu]

@RoryDaulton I am considering an extreme case for your code, when there are 3 angles, and each angle is exactly PI. Then angle_sum = 3* PI, so it will return True. But actually it is not strictly convex since the 3 vertices are on single line. So should we add a if condition to test if the angle == PI and return False when the condition holds?

[Qinqing Liu]

@RoryDaulton I mean, might return True due to computation precision.

[collapsar]

The criterion basically amounts to the definition of a convex polygon as the intersection of half planes, or of the convex hull. Since being convex for a polygon is tantamount to being its own convex hull, computing that hull admits to a convexity test, albeit with non-optimal complexity of O(n log n). This also would not distinguish between complex and non-convex simple polygons.

[Marco Ottina]

Wouldn't "fix" the "self-intersecting polygon issue" the addition of using the values held in "zcrossproduct" to check if the polygon does or not perform a perfect 360° twist?

[dashesy]

how could @LorenPechtel's answer be correct for this self intersecting polygon: [[1, 100],[200, 1], [200, 100], [1,1]]? all angles are less than 180, unless I do not understand that answer

[ElRudi]

Change the if ndx == 0 .. else with if not np.isclose(angle, 0.): # only check if direction actually changed if orientation is None: orientation = np.sign(angle) elif orientation != np.sign(angle): return False and it should work also for your edge case. Also add an orientation = None before the loop.

[Abraham Murciano Benzadon]

Is this a named/known algorithm? Anyone know where I can find a proof of correctness?

[WDUK]

Kinda confused how to do this for N points like a quadrilateral. Your last paragraph regarding N points is a bit hard to decipher.

[causa prima]

@Stef 3 points following the edge of the polygon, not all combinations of three vertexes.

[new QOpenGLWidget]

@Stef I believe the answerer means 3 consecutive points along the edge of the polygon.

[LiNKeR]

I find this approach very fast, it really makes a lot of sense! it’s also applicable in higher dimensions although I feel this answer however deserves to be better simplified. Here’s a simple illustration using a polytope in some dimension (2): for a polygon (2-polytope) to be convex then when each face (line) is selected (green) the vertices of all other faces (lines) not selected would be on the same level or behind the normal (blue arrow) of the selected face (line) i.e. never in front of it

[LiNKeR]

thus an algorithm implementing this logic for a given polytope would check each time that vertices from other faces are not in front of a selected face (via its normal).