Determine whether a polygon is convex in C#

example

To see if a polygon is convex, calculate the angles at each of the polygon’s corners. If all of the angles have the same sign (either positive or negative depending on the orientation), then the polygon is convex.

Rather than actually finding the angles, you can just find the cross product of the segments on either side of the angles. If the segments at point B are AB and BC, then the cross product has value |AB| * |BC| * Sin(theta) where theta is the angle between the two segments. Because the lengths are always positive, the result is positive if the angle is positive and negative if the angle is negative.

The following code shows how this example’s Polygon class determines whether a polygon is convex.

// Return True if the polygon is convex.
public bool PolygonIsConvex()
{
    // For each set of three adjacent points A, B, C,
    // find the cross product AB ยท BC. If the sign of
    // all the cross products is the same, the angles
    // are all positive or negative (depending on the
    // order in which we visit them) so the polygon
    // is convex.
    bool got_negative = false;
    bool got_positive = false;
    int num_points = Points.Length;
    int B, C;
    for (int A = 0; A < num_points; A++)
    {
        B = (A + 1) % num_points;
        C = (B + 1) % num_points;

        float cross_product =
            CrossProductLength(
                Points[A].X, Points[A].Y,
                Points[B].X, Points[B].Y,
                Points[C].X, Points[C].Y);
        if (cross_product < 0)
        {
            got_negative = true;
        }
        else if (cross_product > 0)
        {
            got_positive = true;
        }
        if (got_negative && got_positive) return false;
    }

    // If we got this far, the polygon is convex.
    return true;
}

This method loops through the polygon’s points. For each point A, it finds the indices of the preceding and following points A and C. It then uses the CrossProductLength method to calculate AB cross BC. The code keeps track of whether it has found positive or negative cross products. If it has found both, the method returns false to indicate that the polygon is not convex. If the code never finds both positive and negative cross products, it returns true to indicate that the polygon is convex.

The following code shows the CrossProductLength method.

// Return the cross product AB x BC.
// The cross product is a vector perpendicular to AB
// and BC having length |AB| * |BC| * Sin(theta) and
// with direction given by the right-hand rule.
// For two vectors in the X-Y plane, the result is a
// vector with X and Y components 0 so the Z component
// gives the vector's length and direction.
public static float CrossProductLength(float Ax, float Ay,
    float Bx, float By, float Cx, float Cy)
{
    // Get the vectors' coordinates.
    float BAx = Ax - Bx;
    float BAy = Ay - By;
    float BCx = Cx - Bx;
    float BCy = Cy - By;

    // Calculate the Z coordinate of the cross product.
    return (BAx * BCy - BAy * BCx);
}

For more information on the cross product and how it is calculated, see Wikipedia and Wolfram MathWorld.

example

Note that the definition of convex for self-intersecting polygons is a bit fuzzy. If you interpret convex to mean that all angles have the same signs, then this example works just fine. That means, for example, that the star on the right is convex.

If you want convex to mean that the polygon has no “inner corners” like those the star has, then the method described here doesn’t work for self-intersecting polygons. In that case, you should probably just check for self-intersection separately.


Download Example   Follow me on Twitter   RSS feed




This entry was posted in algorithms, geometry, graphics, mathematics and tagged , , , , , , , , , , , . Bookmark the permalink.

9 Responses to Determine whether a polygon is convex in C#

  1. Christodoulos says:

    Well take a look at the following polygon:

    all of the angles have the same sign (either positive or negative depending on the orientation) and it is certainly non convex!

  2. Rod Stephens says:

    Sorry, I should have said that the assumption is that the polygon is not self-intersecting. If it is, then the definition of convex is a bit less clear.

  3. Christodoulos says:

    I think, correct me if I am wrong, that a self intersecting polygon is certainly non convex (I came along to your post when I was searching for an O(n) convexity test that works for *any* polygon).

  4. Rod Stephens says:

    That would fit my definition but I can imagine people who might want to treat those polygons differently. Wolfram Mathworld’s definition is:

    A planar polygon is convex if it contains all the line segments connecting any pair of its points.

    That works for me and would rule out most self-intersecting polygons.

    But I can imagine one that basically has a convex outline by contains an interior loop. Depending on how you define the interior (alternating or winding rule), I think it might be considered convex by that definition.

    My preference would be to just test for self-intersection and not count that as convex.

  5. Pingback: Determine whether a point is inside a polygon in C# |

  6. Pingback: Determine whether a point is inside a polygon in C# |

  7. Pingback: Perform geometric operations on polygons in C# |

  8. Ben says:

    Nice work. I’ve gotta look into this one.

    But before checking whether it’s convex, is there a method to check if the polygon is closed?

    I’d imagine it wouldn’t work if the polygon was still open somewhere?

    chrs

    • RodStephens says:

      Well, it’s not a polygon if it’s not closed. Then it would be a polyline.

      Normally you specify a polygon as a sequence of points that you connect in order and then you connect the last one to the first one to close it. If that’s the way you store them, then you can’t have a non-closed polygon.

      The only weird case along those lines would be a polygon with only 2 points, or one that has duplicate points so it isn’t a polygon. For example, 3 points where two are repeated or a bunch of points that all lie along a line. You could test for those if they might occur. (It would depend on how you generate the polygons.)

Leave a Reply

Your email address will not be published. Required fields are marked *