寻找一个多边形的质心？
为了得到中心，我已经尝试过，为每个顶点添加总数，除以顶点的数量。
我也试图find最顶端，最底部 – >中点…find最左边，最右边，find中点。
这两个都没有返回完美的中心，因为我依靠中心来缩放多边形。
我想缩放我的多边形，所以我可以在他们周围放一个边框。
考虑到多边形可以是凹面的，凸的，并且具有许多不同长度的多边形，find多边形的质心的最好方法是什么？
公式如下： http : //en.wikipedia.org/wiki/Centroid#Centroid_of_polygon
对于那些难以理解这些公式中的西格马符号的人来说，下面是一些显示如何进行计算的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"; } 我只在右上angular的x / y象限中testing了这个方形多边形。
如果您不介意在每次迭代中执行两次（可能是昂贵的）额外模数运算，则可以将之前的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; }
质心可以被计算为它可以被分割到的三angular形的质心的加权和。
这里是这种algorithm的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! Eg, 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(" ixy\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上有一个多边形质心文章，它解释了它。
boost::geometry::centroid(your_polygon, p);
将其分解成三angular形，找出每个区域的面积和质心，然后使用局部面积作为权重来计算所有局部质心的平均值。 有些地方可能是负面的。
