폴리곤의 중심을 찾으십니까?

폴리곤의 중심을 찾으십니까?

중심을 얻기 위해 각 정점에 대해 합계를 더해서 꼭지점 수로 나누려고 했습니다.

또, 최첨단의 botommost-> 중간점을 찾으려고 했습니다.가장 왼쪽, 가장 오른쪽, 중간점을 찾습니다.

폴리곤의 축척을 중심에 의존하기 때문에 둘 다 완벽한 중심을 반환하지 않았습니다.

폴리곤의 크기를 조정하고 싶기 때문에 둘레에 테두리를 둘 수 있습니다.

폴리곤이 오목하고 볼록하며 다양한 길이의 변이 많을 수 있다는 점을 감안할 때 폴리곤의 중심을 찾는 가장 좋은 방법은 무엇일까요?

이 공식은 폴리곤의 둘레를 따라 정렬된 정점에 대해 제공됩니다.

이러한 공식의 시그마 표기법을 이해하는 데 어려움을 겪고 있는 사용자를 위해 계산 방법을 보여 주는 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;
}

중심은 분할할 수 있는 삼각형의 중심 합계의 가중치로 계산할 수 있습니다.

이러한 알고리즘의 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) 위키에 폴리곤 중심 기사가 있습니다.

다음은 중복된 코드나 고가의 모듈러스 연산을 사용하지 않는 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";
}

삼각형을 삼각형으로 나누고 각 면적의 면적과 중심을 구한 다음 부분 영역을 가중치로 사용하여 모든 부분 중심체의 평균을 계산합니다.오목한 부분에서는 음이 될 수 있습니다.

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

언급URL : https://stackoverflow.com/questions/2792443/finding-the-centroid-of-a-polygon