Convexity of a polygon C++?

Question

How can i test if a polygon is convex or not only by knowing the points of the polygon with their coordonates in c++?

Surely you do not expect us to give you the full source code for such a problem. What have you tried? Are you stuck with the algorithm? Don't you know how to formulate the algorithm in C++? — Oswald, Mar 03 '13 at 21:04
You can go through the points one-by-one, grab the two neighbors of the current point, then use the cosine theorem to find out the angle enclosed by those three points. If you find an angle greater than 90 degrees, then the polygon is concave, if there aren't any angles greater than 90 degress, then it's convex. — , Mar 03 '13 at 21:04
I tried this way but i don't know how to determine if it's an interior angle or exterior because i need the interior one — user2116010, Mar 03 '13 at 21:08
@user2116010 The cosine theorem will always give you the smaller angle. Then you can deduce if it's the interior or exterior angle from the relative x and y coordinates of the central point relative to the two other points. — , Mar 03 '13 at 21:11

hate-engine · Accepted Answer · 2013-03-03T21:25:53.417

For each side of polygon, calculate line equation (Ax+By+C=0) and check (put x and y into equation and get sign of it), that all points are from one side of it.

EDIT: If travel convex polygon, you will always rotate into one direction (left or right) on every point. Using cross product, you can simply deduce, onto which side (negative or positive) you will rotate next turn. If all cross products of three consecutive points will have equal sign, then your polygon is convex.

masoud · Answer 2 · 2013-03-03T21:44:03.567

the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.

Pseudocode from wiki:

jarvis(S)
   pointOnHull = leftmost point in S
   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]  // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|-1
         if (endpoint == pointOnHull) or
            (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0] // wrapped around to first hull point

If your points match detected points of above algorithm then the polygon is convex.

score 1 · Answer 3 · answered Mar 03 '13 at 21:29

Find the convex hull using any of the common algorithms. A polygon is convex if and only if all its vertices belong to its convex hull.

This is O(n log n) but does not rely on the assumption that the points are given in the proper order around the edges of the polygon. If the assumption is true then the answer from hate-engine is optimal (i.e. linear time.)

Convexity of a polygon C++?

3 Answers3