Finding the centroid of a polygon?

Question

I have tried: for each vertex, add to total, divide by number of verities to get center.

I'v also tried: Find the topmost, bottommost -> get midpoint... find leftmost, rightmost, find midpoint.

Both of these did not return the perfect center because I'm relying on the center to scale a polygon.

I want to scale my polygons so I may put a border around them.

What is the best way to find the centroid of a polygon given that the polygon may be concave, convex and have many many sides of various lengths.

Thanks

Answer 1

Break it into triangles, find the area and centroid of each, then calculate the average of all the partial centroids using the partial areas as weights. With concavity some of the areas could be negative.

Answer 2

The formula is given here: http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon

For those having difficulty understanding the sigma notation in those formulas, here is some C++ code showing how to do the computation:

#include <iostream>

struct Point2D
{
    double x;
    double y;
};

Point2D compute2DPolygonCentroid(const Point2D* vertices, int vertexCount)
{
    Point2D centroid = {0, 0};
    double signedArea = 0.0;
    double x0 = 0.0; // Current vertex X
    double y0 = 0.0; // Current vertex Y
    double x1 = 0.0; // Next vertex X
    double y1 = 0.0; // Next vertex Y
    double a = 0.0;  // Partial signed area

    // For all vertices except last
    int i=0;
    for (i=0; i<vertexCount-1; ++i)
    {
        x0 = vertices[i].x;
        y0 = vertices[i].y;
        x1 = vertices[i+1].x;
        y1 = vertices[i+1].y;
        a = x0*y1 - x1*y0;
        signedArea += a;
        centroid.x += (x0 + x1)*a;
        centroid.y += (y0 + y1)*a;
    }

    // Do last vertex
    x0 = vertices[i].x;
    y0 = vertices[i].y;
    x1 = vertices[0].x;
    y1 = vertices[0].y;
    a = x0*y1 - x1*y0;
    signedArea += a;
    centroid.x += (x0 + x1)*a;
    centroid.y += (y0 + y1)*a;

    signedArea *= 0.5;
    centroid.x /= (6*signedArea);
    centroid.y /= (6*signedArea);

    return centroid;
}

int main()
{
    Point2D polygon[] = {{0.0,0.0}, {0.0,10.0}, {10.0,10.0}, {10.0,0.0}};
    size_t vertexCount = sizeof(polygon) / sizeof(polygon[0]);
    Point2D centroid = compute2DPolygonCentroid(polygon, vertexCount);
    std::cout << "Centroid is (" << centroid.x << ", " << centroid.y << ")\n";
}

I've only tested this for a square polygon in the upper-right x/y quadrant.

Answer 3

The centroid can be calculated as the weighted sum of the centroids of the triangles it can be partitioned to. Here is the C source code for such an algorithm. There's a polygon centroid article on the CGAFaq (comp.graphics.algorithms FAQ) wiki that explains it.