BLOG.CSHARPHELPER.COM: Determine whether a polygon is convex in C#

Determine whether a polygon is convex in C#

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.

// Return True if the polygon is convex.
public bool PolygonIsConvex()
{
    // For each set of three adjacent points A, B, C,
    // find the dot product AB · BC. If the sign of
    // all the dot 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;
}

Posted by Rod Stephens at 1/4/2010 7:23 AM

Categories: geometry, algorithms, graphics
Tags: geometric operations example program geometry algorithms convex C# example C# programming Windows Forms programming polygon concave

Trackbacks

Trackback specific URL for this post

No trackbacks exist for this post.

Comments

Display comments as (Linear | Threaded)

3/3/2013 12:23 PM Christodoulos wrote:
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!
Reply to this
1. 3/3/2013 2:54 PM Rod Stephens wrote:
  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.
  Reply to this
  1. 3/3/2013 9:00 PM Christodoulos wrote:
    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).
    Reply to this
    1. 3/5/2013 4:26 PM Rod Stephens wrote:
      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.
      Reply to this