Convexity of a polygon C++? [duplicate]

Question

This question already has answers here:

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

How to check if polygon is convex? [duplicate] (1 answer)

Closed 9 years ago.

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

Answer 1

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.

Answer 2

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

Answer 3

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.