¿Encontrando el centroide de un polígono?

Question

Para obtener el centro, he intentado, para cada vértice, sumar al total, dividir por el número de vértices.

También he intentado encontrar el punto más alto, más bajo -> obtener punto medio ... encontrar a la izquierda, más a la derecha, encontrar el punto medio.

Ambos no devolvieron el centro perfecto porque confío en el centro para escalar un polígono.

Quiero escalar mis polígonos, por lo que puedo poner un borde alrededor de ellos.

¿Cuál es la mejor manera de encontrar el centroide de un polígono dado que el polígono puede ser cóncavo, convexo y tener muchos lados de varias longitudes?

Answer 1

La fórmula se da here.

Para aquellos que tienen dificultades para entender la notación sigma en esas fórmulas, he aquí algo de código C++ que muestra cómo hacer el cálculo:

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

sólo lo he probado esto para un polígono cuadrado en la parte superior derecha x/y cuadrante.

---

Si no les importa realizar dos (potencialmente costosas operaciones de módulo) adicionales en cada iteración, entonces se puede simplificar el compute2DPolygonCentroid función anterior a lo siguiente:

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

Divídala en triángulos, encuentre el área y el centroide de cada uno, luego calcule el promedio de todos los centroides parciales usando las áreas parciales como pesos. Con concavidad algunas de las áreas podrían ser negativas.

Answer 3

El centro de gravedad se puede calcular como la suma ponderada de los centroides de los triángulos a los que se puede dividir.

Aquí es el C source code de tal algoritmo:

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

Hay un artículo en el polygon centroid CGAFaq (comp.graphics.algorithms FAQ) wiki que lo explica.

Answer 4

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