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

by

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.

More Related Contents:

  1. An algorithm for inflating/deflating (offsetting, buffering) polygons
  2. Largest circle inside a non-convex polygon
  3. How can I create an internal spiral for a polygon?
  4. Sort points in clockwise order?
  5. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  6. How to check if line segment intersects a rectangle?
  7. Polygon enclosing a set of points
  8. What is the most efficient algorithm to find a straight line that goes through most points?
  9. Find if a point is inside a convex hull for a set of points without computing the hull itself
  10. Compute the area of intersection between a circle and a triangle?
  11. Location of highest density on a sphere
  12. How to determine if a point is in a 2D triangle? [closed]
  13. Circle line-segment collision detection algorithm?
  14. Algorithm to detect intersection of two rectangles?
  15. Finding whether a point lies inside a rectangle or not
  16. How do you calculate the average of a set of circular data? [closed]
  17. What is an Efficient algorithm to find Area of Overlapping Rectangles
  18. How to Compute OBB of Multiple Curves?
  19. How to compare two shapes?
  20. Combined area of overlapping circles
  21. Calculate largest inscribed rectangle in a rotated rectangle
  22. What is the fastest way to find the closest point to a given point?
  23. Circle-circle intersection points
  24. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  25. Sort Four Points in Clockwise Order
  26. How to find convex hull in a 3 dimensional space
  27. Check if polygon is inside a polygon
  28. Calculating the position of points in a circle
  29. determine if a point sits inside an arbitrary shape?
  30. Distance from a point to a polygon

Leave a Comment