How do I efficiently determine if a polygon is con

Question

From the man page for XFillPolygon:

• If shape is Complex, the path may self-intersect. Note that contiguous coincident points in the path are not treated as self-intersection.

• If shape is Convex, for every pair of points inside the polygon, the line segment connecting them does not intersect the path. If known by the client, specifying Convex can improve performance. If you specify Convex for a path that is not convex, the graphics results are undefined.

• If shape is Nonconvex, the path does not self-intersect, but the shape is not wholly convex. If known by the client, specifying Nonconvex instead of Complex may improve performance. If you specify Nonconvex for a self-intersecting path, the graphics results are undefined.

I am having performance problems with fill XFillPolygon and, as the man page suggests, the first step I want to take is to specify the correct shape of the polygon. I am currently using Complex to be on the safe side.

Is there an efficient algorithm to determine if a polygon (defined by a series of coordinates) is convex, non-convex or complex?

Answer 1

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.

Answer 2

The answer by @RoryDaulton seems the best to me, but what if one of the angles is exactly 0? Some may want such an edge case to return True, in which case, change "<=" to "<" in the line :

if orientation * angle < 0.0:  # not both pos. or both neg.

Here are my test cases which highlight the issue :

# A square    
assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) )

# This LOOKS like a square, but it has an extra point on one of the edges.
assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) )

The 2nd assert fails in the original answer. Should it? For my use case, I would prefer it didn't.

Answer 3

Here's a test to check if a polygon is convex.

Consider each set of three points along the polygon. If every angle is 180 degrees or less you have a convex polygon. When you figure out each angle, also keep a running total of (180 - angle). For a convex polygon, this will total 360.

This test runs in O(n) time.

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.

Answer 4

I implemented both algorithms: the one posted by @UriGoren (with a small improvement - only integer math) and the one from @RoryDaulton, in Java. I had some problems because my polygon is closed, so both algorithms were considering the second as concave, when it was convex. So i changed it to prevent such situation. My methods also uses a base index (which can be or not 0).

These are my test vertices:

// concave
int []x = {0,100,200,200,100,0,0};
int []y = {50,0,50,200,50,200,50};

// convex
int []x = {0,100,200,100,0,0};
int []y = {50,0,50,200,200,50};

And now the algorithms:

private boolean isConvex1(int[] x, int[] y, int base, int n) // Rory Daulton
{
  final double TWO_PI = 2 * Math.PI;

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

  // needed for any bad points or direction changes
  // Check for too few points
  if (n <= 3) return true;
  if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
     n--;
  // Get starting information
  int old_x = x[n-2], old_y = y[n-2];
  int new_x = x[n-1], new_y = y[n-1];
  double new_direction = Math.atan2(new_y - old_y, new_x - old_x), old_direction;
  double angle_sum = 0.0, orientation=0;
  // Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon):
  for (int i = 0; i < n; i++)
  {
     // Update point coordinates and side directions, check side length
     old_x = new_x; old_y = new_y; old_direction = new_direction;
     int p = base++;
     new_x = x[p]; new_y = y[p];
     new_direction = Math.atan2(new_y - old_y, new_x - old_x);
     if (old_x == new_x && old_y == new_y)
        return false; // repeated consecutive points
     // Calculate & check the normalized direction-change angle
     double angle = new_direction - old_direction;
     if (angle <= -Math.PI)
        angle += TWO_PI;  // make it in half-open interval (-Pi, Pi]
     else if (angle > Math.PI)
        angle -= TWO_PI;
     if (i == 0)  // if first time through loop, initialize orientation
     {
        if (angle == 0.0) return false;
        orientation = angle > 0 ? 1 : -1;
     }
     else  // if other time through loop, check orientation is stable
     if (orientation * angle <= 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 Math.abs(Math.round(angle_sum / TWO_PI)) == 1;
}

And now from Uri Goren

private boolean isConvex2(int[] x, int[] y, int base, int n)
{
  if (n < 4)
     return true;
  boolean sign = false;
  if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex
     n--;
  for(int p=0; p < n; p++)
  {
     int i = base++;
     int i1 = i+1; if (i1 >= n) i1 = base + i1-n;
     int i2 = i+2; if (i2 >= n) i2 = base + i2-n;
     int dx1 = x[i1] - x[i];
     int dy1 = y[i1] - y[i];
     int dx2 = x[i2] - x[i1];
     int dy2 = y[i2] - y[i1];
     int crossproduct = dx1*dy2 - dy1*dx2;
     if (i == base)
        sign = crossproduct > 0;
     else
     if (sign != (crossproduct > 0))
        return false;
  }
  return true;
}