Поиск центра тяжести многоугольника?

Чтобы получить центр, я попытался для каждой вершины добавить к сумме, делить на число вершин.

Я также попытался найти самую верхнюю, самую нижнюю → получить среднюю точку... найти крайний левый крайний край, найти среднюю точку.

Оба из них не вернули идеальный центр, потому что я полагаюсь на центр, чтобы масштабировать многоугольник.

Я хочу масштабировать мои полигоны, поэтому я могу разместить вокруг них границу.

Каков наилучший способ найти центроид многоугольника, учитывая, что многоугольник может быть вогнутым, выпуклым и иметь много сторон разной длины?

Ответ 1

Формула дается здесь.

Для тех, кто с трудом понимает сигма-нотацию в этих формулах, вот какой-то код на С++, показывающий, как выполнить вычисление:

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

Ответ 2

Центроид можно рассчитать как взвешенную сумму центроидов треугольников, к которым он может быть разбит.

Вот такой C исходный код для такого алгоритма:

/*
    Written by Joseph O'Rourke
    [email protected]
    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 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 FAQ), которая объясняет это.

Ответ 3

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

Ответ 4

Разделите его на треугольники, найдите область и центр тяжести каждого, затем вычислите среднее значение всех частичных центроидов, используя частичные области в качестве весов. С вогнутостью некоторые области могут быть отрицательными.