找到多边形的质心?

问题描述

为了获得中心，我尝试将每个顶点添加到总数中，然后除以顶点数.

To get the center, I have tried, for each vertex, to add to the total, divide by the number of vertices.

我也试过找到最上面、最下面 -> 找到中点...找到最左边、最右边，找到中点.

I've also tried to find the topmost, bottommost -> get midpoint... find leftmost, rightmost, find the 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?

推荐答案

给出公式这里 表示顶点按照它们沿多边形周长的出现次数排序.

对于那些难以理解这些公式中的 sigma 符号的人，这里有一些 C++ 代码展示了如何进行计算:

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 << ")
";
}

我只针对右上 x/y 象限中的方形多边形进行了测试.

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

如果您不介意在每次迭代中执行两个(可能很昂贵)额外的模数运算，那么您可以将之前的 compute2DPolygonCentroid 函数简化为以下内容:

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;
}

这篇关于找到多边形的质心?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持html5模板网！