Find the centroid of a polygon in C#

Polygon centroid

The centroid of a polygon is its “center of mass.” If you were to cut the polygon out of cardboard or wood, 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 (on a donut shape the centroid would be 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 = Σ[(Xi + Xi+1) * (Xi * Yi+1 - Xi+1 * Yi)] / 6 / A
Y = Σ[(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);
}

This method copies the polygon’s points into an array and repeats the first point at the end of the array to make looping through the polygon’s segments easier. It the loops through the segments and adds up the X and Y terms shown in the earlier equation. It divides the totals by 6 times the area returned by the PolygonArea method (described in the post Calculate the area of a polygon in C#). Finally the method returns a new PointF representing the calculated point.

The program marks the centroid with a yellow circle.


Download Example   Follow me on Twitter   RSS feed


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

11 Responses to Find the centroid of a polygon in C#

  1. 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 🙂

  2. Rod Stephens says:

    Cool! I’m glad you found it useful.

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

  4. Rod Stephens says:

    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.
  5. 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;
    }
  6. Alexander says:

    Hello Dear Rod Stephens.
    First of all thank you very much for your site and materials!
    I have one question for this code.
    Could you please explain why it is necessary to divide by 6 the polygon’s area?
    Thank you very much!

  7. Rod Stephens says:

    The short answer is because it says so at Wikipedia: Centroid.

    I tried to derive their formula but I’m having trouble. I can get a formula that works but it doesn’t look the same as theirs. There must be some identity that I’m missing that would convert mine into theirs.

    But I think this is the gist:

    You can consider the polygon as a series of trapezoids, add up their moments of inertia, and then divide by the total area to get the centroid’s coordinates. This is similar to the way you can calculate the area of the polygon. Some trapezoids give negative moments of inertia and those cancel out the areas in the other trapezoids that are not part of the polygon.

    To calculate the moment of inertia of a trapezoid, you can break it into two triangles. For each triangle, you get the moment of inertia by multiplying the area by the X coordinate (for example) of the triangle’s centroid. A triangle’s area is base * height / 2 so there’s a factor of 1/2.

    If a triangle has corners that have X coordinates x1, x2, and x3, then its centroid has X coordinate (x1 + x2 + x3) / 3. There’s a factor of 1/3.

    When you multiply them out, you get a factor of 1/2 * 1/3 = 1/6. That’s where the factor of 1/6 comes from.

    Sorry I can’t figure out how to get the full derivation to work. I’ve looked long and hard but can’t find anywhere on the internet that actually works it out.

    If anyone finds an explanation showing how this works, please email me or post a followup here.

  8. Rod Stephens says:

    I found a derivation at: Area and center of mass of a polygon
    [This link no longer works so I have disabled it. I’m looking for a replacement.]

    Look in the “Finding the center of mass” section. It’s pretty complicated, though. I’d still like a simpler explanation.

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

Leave a Reply

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