Trouver le centre de gravité d'un polygone?

Question

J'ai essayé: pour chaque sommet, ajouter à la totale, diviser par le nombre de vérités pour obtenir center.

Je v essayé aussi: Trouver le plus haut, en bas -> get milieu... trouver la plus à gauche, plus à droite, trouver le milieu.

Ces deux n'ont pas retourné le centre parfait parce que je suis s'appuyant sur le centre à l'échelle d'un polygone.

Je tiens à l'échelle de mes polygones afin que je puisse mettre une bordure autour d'eux.

Quelle est la meilleure façon de trouver le centre de gravité d'un polygone donné que le polygone peut être concave, convexe et a beaucoup de côtés de longueurs différentes.

Merci

Answer 1

La formule est donnée ici: http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon

Pour ceux qui ont du mal à comprendre la notation sigma dans ces formules, voici du code C ++ montrant comment faire le calcul:

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

Je n'ai testé cela que pour un polygone carré dans le quadrant supérieur droit x / y.

Answer 2

Le centre de gravité peut être calculée comme la somme pondérée des centroïdes des triangles, il peut être partitionné.

Voici le code source C pour un tel algorithme:

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

Il y a un polygone centre de gravité de l'article sur le CGAFaq (comp.les graphiques.les algorithmes FAQ) sur le wiki qui explique cela.

Answer 3

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

le tour est joué!

Answer 4

Divisez-le en triangles, trouvez l'aire et le centroïde de chacun, puis calculez la moyenne de tous les centroïdes partiels en utilisant les aires partielles comme poids. Avec concavité, certaines zones pourraient être négatives.