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

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

Consider each set of three points along the polygon--a vertex, the vertex before, the vertex after. 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.

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;
}

For a non complex (intersecting) polygon to be convex, vector frames obtained from any two connected linearly independent lines a,b must be point-convex otherwise the polygon is concave.

For example the lines a,b are convex to the point p and concave to it below for each case i.e. above: p exists inside a,b and below: p exists outside a,b

Similarly for each polygon below, if each line pair making up a sharp edge is point-convex to the centroid c then the polygon is convex otherwise it’s concave.

blunt edges (wronged green) are to be ignored

N.B
This approach would require you compute the centroid of your polygon beforehand since it doesn’t employ angles but vector algebra/transformations