Find a polygon's centroid in C#

If you were to cut the polygon out of cardboard, the centroid would be the point where you could balance the polygon on a pin. Note that the centroid does not necessarily lie on the polygon (imagine a donut shape with the centroid in the central hole) so you might need to glue the polygon to a piece of transparent plastic and place the pin on the plastic.

The formula for the centroid (X, Y) is given by: 

    X = SUM[(Xi + Xi+1) * (Xi * Yi+1 - Xi+1 * Yi)] / 6 / A
    Y = SUM[(Yi + Yi+1) * (Xi * Yi+1 - Xi+1 * Yi)] / 6 / A

Here A is the area of the polygon and the sum is taken over all of the adjacent pairs of points. 

// Find the polygon's centroid.
public PointF FindCentroid()
{
    // Add the first point at the end of the array.
    int num_points = Points.Length;
    PointF[] pts = new PointF[num_points + 1];
    Points.CopyTo(pts, 0);
    pts[num_points] = Points[0];

    // Find the centroid.
    float X = 0;
    float Y = 0;
    float second_factor;
    for (int i = 0; i < num_points; i++)
    {
        second_factor =
            pts[i].X * pts[i + 1].Y -
            pts[i + 1].X * pts[i].Y;
        X += (pts[i].X + pts[i + 1].X) * second_factor;
        Y += (pts[i].Y + pts[i + 1].Y) * second_factor;
    }

    // Divide by 6 times the polygon's area.
    float polygon_area = PolygonArea();
    X /= (6 * polygon_area);
    Y /= (6 * polygon_area);

    // If the values are negative, the polygon is
    // oriented counterclockwise so reverse the signs.
    if (X < 0)
    {
        X = -X;
        Y = -Y;
    }

    return new PointF(X, Y);
}

   

Posted by Rod Stephens at 1/4/2010 7:35 AM
Categories: geometry, algorithms, graphics
Tags: geometric operations example program center of gravity centroid Windows Forms programming algorithms center of mass example C# programming C# polygon geometry
Previous Post
Next Post

 

What did you think of this article?




Trackbacks
Trackback specific URL for this post
  • No trackbacks exist for this post.
Comments
Display comments as (Linear | Threaded)

  • 2/4/2010 8:09 AM Luca del Tongo wrote:
    Thanks a lot Rod for this post... i've slightly modified your code and used in a head tracking cv project...i've linked this post in my code :)
    Reply to this
    1. 2/4/2010 8:16 AM Rod Stephens wrote:
      Cool! I'm glad you found it useful.

      Reply to this
      1. 2/4/2010 8:35 AM Luca del Tongo wrote:
        The only little improvement i've done on your code has been to not use an extra temp array (dim = n+1). using modulo operator you can work directly on points array
        Reply to this
        1. 2/4/2010 9:52 AM Rod Stephens wrote:
          Yeah, I thought about that.

          You can even do it with neither, I think, if you save the "previous" points in variables x0 and y0. Then you loop through each of the points using the current point and the "previous" one. Something like this (untested):

              float x0 = Points[Points.Length - 1].X;
              float y0 = Points[Points.Length - 1].Y;
              for (int i = 0; i < num_points; i++)
              {
                  second_factor =
                      x0 * Points[i].Y -
                      Points[i].X * y0;
                  X += (x0 + Points[i].X) * second_factor;
                  Y += (y0 + Points[i].Y) * second_factor;
           
                  x0 = Points[i].X;
                  y0 = Points[i].Y;
          
    }
           
           
           But that's more confusing and probably wouldn't save much time unless it was a huge polygon.
          I'm not sure how you're using it for head tracking so I don't know if the savings would be worth
          the extra complexity.
           
          Your improvement to avoid copying the array probably gives more benefits with less complication
          so it's more worthwhile.

          Reply to this
  • 2/4/2010 10:40 AM Luca del Tongo wrote:
    This is for example the refactoring i've done of your area computing function:
    private float SignedPolygonArea(PointF[] Hull)
    {
        // Add the first point to the end.
        int num_points = Hull.Length;            
     
        // Get the areas.
        float area = 0;
        for (int i = 0; i < num_points; i++)
        {
            area +=
                (Hull[(i + 1)% num_points].X - Hull[i].X) *
                (Hull[(i + 1)% num_points].Y + Hull[i].Y) / 2;
        }
     
        // Return the result.
        return area;
    }

    Reply to this
Leave a comment

Submitted comments are subject to moderation before being displayed.

 Name

 Email (will not be published)

 Website

Your comment is 0 characters limited to 3000 characters.