TWO_PI = 2 * pi
"""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:
# 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:
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.
# 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.