找到多边形的质心？

Question

为了获得中心,我已经尝试为每个顶点添加总数,除以顶点数.

我也试图找到最顶端,最底部 - >获得中点...找到最左边,最右边,找到中点.

这两个都没有返回完美的中心,因为我依靠中心来缩放多边形.

我想缩放我的多边形,所以我可以在它们周围放置一个边框.

找到多边形的质心的最佳方法是多边形可能是凹的,凸的并且有许多不同长度的边？

Answer 1

这里给出了公式.

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

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

我只测试了右上角x/y象限中的方形多边形.

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

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

Answer 2

可以将质心计算为可以划分为的三角形的质心的加权和.

以下是此类算法的C源代码:

/*
    Written by Joseph O'Rourke
    orourke@cs.smith.edu
    October 27, 1995

    Computes the centroid (center of gravity) of an arbitrary
    simple polygon via a weighted sum of signed triangle areas,
    weighted by the centroid of each triangle.
    Reads x,y coordinates from stdin.  
    NB: Assumes points are entered in ccw order!  
    E.g., input for square:
        0   0
        10  0
        10  10
        0   10
    This solves Exercise 12, p.47, of my text,
    Computational Geometry in C.  See the book for an explanation
    of why this works. Follow links from
        http://cs.smith.edu/~orourke/

*/
#include <stdio.h>

#define DIM     2               /* Dimension of points */
typedef int     tPointi[DIM];   /* type integer point */
typedef double  tPointd[DIM];   /* type double point */

#define PMAX    1000            /* Max # of pts in polygon */
typedef tPointi tPolygoni[PMAX];/* type integer polygon */

int     Area2( tPointi a, tPointi b, tPointi c );
void    FindCG( int n, tPolygoni P, tPointd CG );
int     ReadPoints( tPolygoni P );
void    Centroid3( tPointi p1, tPointi p2, tPointi p3, tPointi c );
void    PrintPoint( tPointd p );

int main()
{
    int n;
    tPolygoni   P;
    tPointd CG;

    n = ReadPoints( P );
    FindCG( n, P ,CG);
    printf("The cg is ");
    PrintPoint( CG );
}

/* 
    Returns twice the signed area of the triangle determined by a,b,c,
    positive if a,b,c are oriented ccw, and negative if cw.
*/
int Area2( tPointi a, tPointi b, tPointi c )
{
    return
        (b[0] - a[0]) * (c[1] - a[1]) -
        (c[0] - a[0]) * (b[1] - a[1]);
}

/*      
    Returns the cg in CG.  Computes the weighted sum of
    each triangle's area times its centroid.  Twice area
    and three times centroid is used to avoid division
    until the last moment.
*/
void FindCG( int n, tPolygoni P, tPointd CG )
{
    int     i;
    double  A2, Areasum2 = 0;        /* Partial area sum */    
    tPointi Cent3;

    CG[0] = 0;
    CG[1] = 0;
    for (i = 1; i < n-1; i++) {
        Centroid3( P[0], P[i], P[i+1], Cent3 );
        A2 =  Area2( P[0], P[i], P[i+1]);
        CG[0] += A2 * Cent3[0];
        CG[1] += A2 * Cent3[1];
        Areasum2 += A2;
    }
    CG[0] /= 3 * Areasum2;
    CG[1] /= 3 * Areasum2;
    return;
}

/*
    Returns three times the centroid.  The factor of 3 is
    left in to permit division to be avoided until later.
*/
void Centroid3( tPointi p1, tPointi p2, tPointi p3, tPointi c )
{
    c[0] = p1[0] + p2[0] + p3[0];
    c[1] = p1[1] + p2[1] + p3[1];
    return;
}

void PrintPoint( tPointd p )
{
    int i;

    putchar('(');
    for ( i=0; i<DIM; i++) {
        printf("%f",p[i]);
        if (i != DIM - 1) putchar(',');
    }
    putchar(')');
    putchar('\n');
}

/*
    Reads in the coordinates of the vertices of a polygon from stdin,
    puts them into P, and returns n, the number of vertices.
    The input is assumed to be pairs of whitespace-separated coordinates,
    one pair per line.  The number of points is not part of the input.
*/
int ReadPoints( tPolygoni P )
{
    int n = 0;

    printf("Polygon:\n");
    printf("  i   x   y\n");      
    while ( (n < PMAX) && (scanf("%d %d",&P[n][0],&P[n][1]) != EOF) ) {
        printf("%3d%4d%4d\n", n, P[n][0], P[n][1]);
        ++n;
    }
    if (n < PMAX)
        printf("n = %3d vertices read\n",n);
    else
        printf("Error in ReadPoints:\too many points; max is %d\n", PMAX);
    putchar('\n');

    return  n;
}

在CGAFaq(comp.graphics.algorithms常见问题解答)维基上有一个多边形质心文章解释它.

Answer 3

boost::geometry::centroid(your_polygon, p);