Search code examples
c++2dpolygoncentroid

Finding the centroid of a polygon

I use the following code to find the centroid of a polygon (I didn't write the code, it's from another question).

Point compute2DPolygonCentroid(const std::vector<Point> vertices) {
    Point centroid;
    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
    for (int i = 0; i < vertices.size() - 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 separately to avoid performing an expensive
    // modulus operation in each iteration.
    x0 = vertices.back().x;
    y0 = vertices.back().y;
    x1 = vertices.front().x;
    y1 = vertices.front().y;
    a = x0 * y1 - x1 * y0;
    signedArea += a;
    centroid.x += (x0 + x1) * a;
    centroid.y += (y0 + y1) * a;

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

    return centroid;
}

The problem is that it works ONLY when the points in the input vector vertices are in clockwise order. When the points are in counterclockwise order it doesn't work. Here's a picture of what I mean by cw && ccw order:

enter image description here

I don't understand why it doesn't work when just the order of the points change but the points are still the same.

Solution

  • The problem, as it turns out, is that Point had unsigned members. There's also a potential secondary problem, regarding floating point rounding issues.

    In this algorithm, if the wind order is the wrong way around, the computed area will be negative, and when you do something like

    centroid.x += (x0 + x1) * a;

    you'll get an incorrect value because a will be negative and centroid.x is unsigned.

    You should store the intermediate centroid values as a floating point of some kind, so that a) you won't get these signed/unsigned issues and b) so that you won't get rounding errors on every vertex; I'm not sure if these errors would end up being large enough to cause you problems, but it seems silly to risk it when it can be so easily avoided. You should cast to unsigned int (or whatever) at the very end when you return.