Finding the centroid of a polygon?

by

The formula is given here for vertices sorted by their occurance along the polygon’s perimeter.

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 separately to avoid performing an expensive
    // modulus operation in each iteration.
    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.0*signedArea);
    centroid.y /= (6.0*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.

If you don’t mind performing two (potentially expensive) extra modulus operations in each iteration, then you can simplify the previous compute2DPolygonCentroid function to the following:

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
    int i=0;
    for (i=0; i<vertexCount; ++i)
    {
        x0 = vertices[i].x;
        y0 = vertices[i].y;
        x1 = vertices[(i+1) % vertexCount].x;
        y1 = vertices[(i+1) % vertexCount].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;
}

More Related Contents:

  1. Invalid operands to binary expression while implementing vector [closed]
  2. Difficulties on atributting a array to another [closed]
  3. Erasing elements from a vector
  4. Why can’t I make a vector of references?
  5. Choice between vector::resize() and vector::reserve()
  6. Does C++11 allow vector?
  7. When vectors are allocated, do they use memory on the heap or the stack?
  8. How can I create cartesian product of vector of vectors?
  9. vector size – 1 when size is 0 in C++
  10. Erasing from a std::vector while doing a for each?
  11. How to read a binary file into a vector of unsigned chars
  12. sizeof() a vector
  13. How to cin values into a vector
  14. What is the simplest way to convert array to vector?
  15. pop_back() return value?
  16. How to implement 2D vector array?
  17. std::vector, default construction, C++11 and breaking changes
  18. Initial capacity of vector in C++
  19. How can I use something like std::vector?
  20. How to make elements of vector unique? (remove non adjacent duplicates)
  21. Compile time triggered range check for std::vector
  22. How do I pass multiple ints into a vector at once?
  23. Does clearing a vector affect its capacity?
  24. Can std::vector emplace_back copy construct from an element of the vector itself?
  25. Why is a C++ Vector called a Vector? [closed]
  26. How to use new std::byte type in places where old-style unsigned char is needed?
  27. gdb Could not find operator[]
  28. Write concurrently vector
  29. C++ – value of uninitialized vector
  30. How to cheaply assign C-style array to std::vector?

Leave a Comment