Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


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

@JasonS I think you need to use vectors with a magnitude of 1 for this to work.

@zenna, i think you miss the precondition - For each consecutive pair of edges of the polygon, it means that the data point set must be clockwise or counterclockwise, then you can apply that to JasonS's algorithm

A polygon is a set of points in a list where the consecutive points form the boundary. It is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):

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]]]

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:

I know this post is more than two years old, but this answer comes up first in Google and it's not right: what you need is the cross product, not the dot product. The sign of the dot product only tells you if the angle between the vectors is greater than 90, what you need is the sign of the cross product, which tells you if vector B is to the left or right the vector A. I really hope this is right.

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]).

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

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.

ah, I think you are correct. I'll change the answer. Thanks!

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


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

@JasonS I think you need to use vectors with a magnitude of 1 for this to work.

@zenna, i think you miss the precondition - For each consecutive pair of edges of the polygon, it means that the data point set must be clockwise or counterclockwise, then you can apply that to JasonS's algorithm

A polygon is a set of points in a list where the consecutive points form the boundary. It is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):

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]]]

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:

I know this post is more than two years old, but this answer comes up first in Google and it's not right: what you need is the cross product, not the dot product. The sign of the dot product only tells you if the angle between the vectors is greater than 90, what you need is the sign of the cross product, which tells you if vector B is to the left or right the vector A. I really hope this is right.

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]).

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

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.

ah, I think you are correct. I'll change the answer. Thanks!

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


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

@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.

@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: 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.

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

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.

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.

The accepted 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.

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). Adding those direction-change angles will result in plus-or-minus one turn for a convex polygon, while a star polygon will have a different sum. 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. The combination of those checks catches all convex and non-convex polygons.

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.

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


Convex is fairly easy to test for: Consider each set of three points along the polygon. If every angle is 180 degrees or less you have a convex polygon. This test runs in O(n) time.

Edit: Peter Kirkham pointed out a polygon that this test won't catch. It's easy enough to catch his polygon, also: When you figure out each angle, also keep a running total of (180 - angle). For a convex polygon this will total 360.

For a convex polygon the total of interior angles in (n-2)*180 regentsprep.org/Regents/math/poly/LPoly1.htm which is another way of looking at it

I can't try this solution till I get back to work. But it looks promissing and it should work.

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.

Thats sounds like a good approach to the problem, but it still leave the problem of complex polygons

You can successfully use this algorithm for every case. Polygons whose sides intersect will fail this angle test.

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


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

@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.

@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: 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.

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

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.

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.

The accepted 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.

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). Adding those direction-change angles will result in plus-or-minus one turn for a convex polygon, while a star polygon will have a different sum. 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. The combination of those checks catches all convex and non-convex polygons.

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.

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


Convex is fairly easy to test for: Consider each set of three points along the polygon. If every angle is 180 degrees or less you have a convex polygon. This test runs in O(n) time.

Edit: Peter Kirkham pointed out a polygon that this test won't catch. It's easy enough to catch his polygon, also: When you figure out each angle, also keep a running total of (180 - angle). For a convex polygon this will total 360.

For a convex polygon the total of interior angles in (n-2)*180 regentsprep.org/Regents/math/poly/LPoly1.htm which is another way of looking at it

I can't try this solution till I get back to work. But it looks promissing and it should work.

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.

Thats sounds like a good approach to the problem, but it still leave the problem of complex polygons

You can successfully use this algorithm for every case. Polygons whose sides intersect will fail this angle test.

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


Assuming all your polygons are in counter-clockwise order, the moment your non-initial polar angle makes a left turn, you know it's not convex.

Not to mention that computing the convex hull is completely unnecessary in this case.

Please correct me if I am wrong. If the Convex hull that is computed by the Gift Wrapping Algorithm doesn't include all the points in the polygon then it is nonconvex? What about the case when the polygon is complex (intersecting sides)?

This algorithm was easier to implement correctly so finally decided to use it (had problems with Loren's answer because acos in C would not return values over 180 degree which is the criteria need to determine if the polygon was convex.

You could see if the line segments intersect with each other to figure out if the polygon is complex (but I'm not sure if that's the fastest way).

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


Assuming all your polygons are in counter-clockwise order, the moment your non-initial polar angle makes a left turn, you know it's not convex.

Not to mention that computing the convex hull is completely unnecessary in this case.

Please correct me if I am wrong. If the Convex hull that is computed by the Gift Wrapping Algorithm doesn't include all the points in the polygon then it is nonconvex? What about the case when the polygon is complex (intersecting sides)?

This algorithm was easier to implement correctly so finally decided to use it (had problems with Loren's answer because acos in C would not return values over 180 degree which is the criteria need to determine if the polygon was convex.

You could see if the line segments intersect with each other to figure out if the polygon is complex (but I'm not sure if that's the fastest way).

Note
Rectangle 27 0

algorithm How do determine if a polygon is complexconvexnonconvex?


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

@JasonS I think you need to use vectors with a magnitude of 1 for this to work.

A polygon is a set of points in a list where the consecutive points form the boundary. It is much easier to figure out whether a polygon is convex or not (and you don't have to calculate any angles, either):

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]]]

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:

I know this post is more than two years old, but this answer comes up first in Google and it's not right: what you need is the cross product, not the dot product. The sign of the dot product only tells you if the angle between the vectors is greater than 90, what you need is the sign of the cross product, which tells you if vector B is to the left or right the vector A. I really hope this is right.

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]).

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

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.

ah, I think you are correct. I'll change the answer. Thanks!

Note