c++ - ポリゴンの図心を見つけますか？

Question

中心を取得するために、頂点ごとに、合計に追加して、頂点の数で割ってみました。

私はまた、最上部、最下部を見つけようとしました->中点を取得します...左端、右端を見つけ、中点を見つけます。

ポリゴンのスケーリングを中心に依存しているため、これらは両方とも完全な中心を返しませんでした。

ポリゴンを拡大縮小したいので、ポリゴンの周囲に境界線を付けることができます。

ポリゴンが凹面、凸面、さまざまな長さの多くの辺を持っている可能性がある場合、ポリゴンの重心を見つけるための最良の方法は何ですか？

Answer 1

ここでは、ポリゴンの周囲に沿って出現する頂点でソートされた頂点の式を示します。

これらの数式のシグマ表記を理解するのが難しい場合は、計算方法を示す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象限の正方形のポリゴンに対してのみテストしました。

---

各反復で2つの（潜在的に高価な）追加のモジュラス演算を実行してもかまわない場合は、前の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 FAQ）wikiに、それを説明するポリゴン重心の記事があります。

Answer 3

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

Answer 4

これは、重複コードや高価なモジュラス演算を使用しないEmile Cormierのアルゴリズムであり、両方の長所があります。

#include <iostream>

using namespace std;

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

    int lastdex = vertexCount-1;
    const Point2D* prev = &(vertices[lastdex]);
    const Point2D* next;

    // For all vertices in a loop
    for (int i=0; i<vertexCount; ++i)
    {
        next = &(vertices[i]);
        x0 = prev->x;
        y0 = prev->y;
        x1 = next->x;
        y1 = next->y;
        a = x0*y1 - x1*y0;
        signedArea += a;
        centroid.x += (x0 + x1)*a;
        centroid.y += (y0 + y1)*a;
        prev = next;
    }

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

Answer 5

それを三角形に分割し、それぞれの面積と重心を見つけてから、部分的な面積を重みとして使用して、すべての部分的な重心の平均を計算します。凹面があると、一部の領域がマイナスになる可能性があります。