如果给定多边形的顶点,如何计算多边形的质心?
How do I calculate centroid of a polygon if the vertices of the polygon are given?
http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon
我访问了上面的 link 并尝试实现公式来制定由 n 个顶点 (x0,y0), (x1,y1), 定义的非自相交闭合多边形的质心。 .., (xn−1,yn−1).
例如,如果坐标为:(0,1)
、(1,0)
、(-1,0)
和 (0,-1)
,则生成的质心坐标应为:
0.00 0.00
#include<stdio.h>
#include<iostream>
#include<utility>
using namespace std;
int main()
{
int t,points;
scanf("%d",&points);
pair<float,float>p[points];
int i;
for(i=0;i<points;i++)
{
scanf("%f %f",&p[i].first,&p[i].second);
}
float ar,x,y;
for(i=0;i<points-1;i++)
{
ar+=(p[i].first*p[i+1].second-(p[i+1].first*p[i].second));
x+=((p[i].first+p[i+1].first)*ar);
y+=((p[i].second+p[i+1].second)*ar);
}
x/=(3*ar);
y/=(3*ar);
printf("%.2f %.2f\n",x,y);
}
然而,当我运行上面的代码给定坐标时,质心的结果坐标是:
-1. -1.
您的代码中有几处需要更改:
- 正如@R Sahu 所注意到的,
ar
、x
和 y
必须在 for
循环之前初始化为零。否则,输出可能是错误的,或者它可能会在不同的运行中发生变化。
- 在迭代
j
处,ar
是
![eq](https://latex.codecogs.com/gif.latex?ar_j%3D%5Csum_%7Bi%3D0%7D%5E%7Bj%7Dx_iy_%7Bi+1%7D-x_%7Bi+1%7Dy_i)
所以 x+=(p[i].first+p[i+1].first)*ar;
是错误的,因为它必须是 :
![eq2](https://latex.codecogs.com/gif.latex?c_x%3D%5Csum_%7Bi%3D0%7D%5En%28x_i+x_%7Bi+1%7D%29%28x_iy_%7Bi+1%7D-x_%7Bi+1%7Dy_i%29)
- 仔细查看 wikipedia page
公式后的几行
In these formulas, the vertices are assumed to be numbered in order of their occurrence along the polygon's perimeter, and the vertex ( xn, yn ) is assumed to be the same as ( x0, y0 ).
由于最后一个点不等于程序中的第一个点,所以输出是错误的。并且没有任何东西可以确保这些点是按照它们在多边形周边出现的顺序输入的。
这里是g++ main.cpp -o main -Wall
编译的代码。选项 -Wall
启用所有警告...用它来调试代码是一个好习惯。
#include<stdio.h>
#include<iostream>
#include<utility>
using namespace std;
int main()
{
int points;
//scanf("%d",&points);
points=4;
pair<float,float>p[points];
int i;
/* for(i=0;i<points;i++)
{
scanf("%f %f",&p[i].first,&p[i].second);
} */
p[0].first=1;p[0].second=0;
p[1].first=0;p[1].second=1;
p[2].first=-1;p[2].second=0;
p[3].first=0;p[3].second=-1;
float ar=0,x=0,y=0,temp;
for(i=0;i<points-1;i++)
{
temp=p[i].first*p[i+1].second-p[i+1].first*p[i].second;
ar+=temp;
x+=(p[i].first+p[i+1].first)*temp;
y+=(p[i].second+p[i+1].second)*temp;
}
temp=p[points-1].first*p[0].second-p[0].first*p[points-1].second;
ar+=temp;
x+=(p[points-1].first+p[0].first)*temp;
y+=(p[points-1].second+p[0].second)*temp;
x/=(3*ar);
y/=(3*ar);
printf("%.6f %.6f\n",x,y);
}
请注意,通过测试 (1,0),(0,1),(-1,0),(0,-1)
,无法确保 ar
的正确性...
我看到以下问题:
ar
、x
和 y
未初始化。
行计算错误:
x+=((p[i].first+p[i+1].first)*ar);
y+=((p[i].second+p[i+1].second)*ar);
您错过了循环的一次迭代:
for(i=0;i<points-1;i++)
这是适合我的函数版本:
int main()
{
int points;
scanf("%d",&points);
pair<float,float>p[points];
int i;
for(i=0;i<points;i++)
{
scanf("%f %f",&p[i].first,&p[i].second);
}
float ar = 0.0;
float x = 0.0;
float y = 0.0;
for(i=0;i<points;i++)
{
// This allows wrap-around when are you dealing with
// the last point in the list.
int j = (i+1)%points;
float common = (p[i].first*p[j].second - p[j].first*p[i].second);
ar += common;
x+=(p[i].first+p[j].first)*common;
y+=(p[i].second+p[j].second)*common;
}
ar *= 0.5;
x /= (6*ar);
y /= (6*ar);
printf("area: %.2f, xc: %.2f, yc: %.2f\n", ar, x, y);
}
http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon
我访问了上面的 link 并尝试实现公式来制定由 n 个顶点 (x0,y0), (x1,y1), 定义的非自相交闭合多边形的质心。 .., (xn−1,yn−1).
例如,如果坐标为:(0,1)
、(1,0)
、(-1,0)
和 (0,-1)
,则生成的质心坐标应为:
0.00 0.00
#include<stdio.h>
#include<iostream>
#include<utility>
using namespace std;
int main()
{
int t,points;
scanf("%d",&points);
pair<float,float>p[points];
int i;
for(i=0;i<points;i++)
{
scanf("%f %f",&p[i].first,&p[i].second);
}
float ar,x,y;
for(i=0;i<points-1;i++)
{
ar+=(p[i].first*p[i+1].second-(p[i+1].first*p[i].second));
x+=((p[i].first+p[i+1].first)*ar);
y+=((p[i].second+p[i+1].second)*ar);
}
x/=(3*ar);
y/=(3*ar);
printf("%.2f %.2f\n",x,y);
}
然而,当我运行上面的代码给定坐标时,质心的结果坐标是:
-1. -1.
您的代码中有几处需要更改:
- 正如@R Sahu 所注意到的,
ar
、x
和y
必须在for
循环之前初始化为零。否则,输出可能是错误的,或者它可能会在不同的运行中发生变化。 - 在迭代
j
处,ar
是
所以 x+=(p[i].first+p[i+1].first)*ar;
是错误的,因为它必须是 :
- 仔细查看 wikipedia page 公式后的几行
In these formulas, the vertices are assumed to be numbered in order of their occurrence along the polygon's perimeter, and the vertex ( xn, yn ) is assumed to be the same as ( x0, y0 ).
由于最后一个点不等于程序中的第一个点,所以输出是错误的。并且没有任何东西可以确保这些点是按照它们在多边形周边出现的顺序输入的。
这里是g++ main.cpp -o main -Wall
编译的代码。选项 -Wall
启用所有警告...用它来调试代码是一个好习惯。
#include<stdio.h>
#include<iostream>
#include<utility>
using namespace std;
int main()
{
int points;
//scanf("%d",&points);
points=4;
pair<float,float>p[points];
int i;
/* for(i=0;i<points;i++)
{
scanf("%f %f",&p[i].first,&p[i].second);
} */
p[0].first=1;p[0].second=0;
p[1].first=0;p[1].second=1;
p[2].first=-1;p[2].second=0;
p[3].first=0;p[3].second=-1;
float ar=0,x=0,y=0,temp;
for(i=0;i<points-1;i++)
{
temp=p[i].first*p[i+1].second-p[i+1].first*p[i].second;
ar+=temp;
x+=(p[i].first+p[i+1].first)*temp;
y+=(p[i].second+p[i+1].second)*temp;
}
temp=p[points-1].first*p[0].second-p[0].first*p[points-1].second;
ar+=temp;
x+=(p[points-1].first+p[0].first)*temp;
y+=(p[points-1].second+p[0].second)*temp;
x/=(3*ar);
y/=(3*ar);
printf("%.6f %.6f\n",x,y);
}
请注意,通过测试 (1,0),(0,1),(-1,0),(0,-1)
,无法确保 ar
的正确性...
我看到以下问题:
ar
、x
和y
未初始化。行计算错误:
x+=((p[i].first+p[i+1].first)*ar); y+=((p[i].second+p[i+1].second)*ar);
您错过了循环的一次迭代:
for(i=0;i<points-1;i++)
这是适合我的函数版本:
int main()
{
int points;
scanf("%d",&points);
pair<float,float>p[points];
int i;
for(i=0;i<points;i++)
{
scanf("%f %f",&p[i].first,&p[i].second);
}
float ar = 0.0;
float x = 0.0;
float y = 0.0;
for(i=0;i<points;i++)
{
// This allows wrap-around when are you dealing with
// the last point in the list.
int j = (i+1)%points;
float common = (p[i].first*p[j].second - p[j].first*p[i].second);
ar += common;
x+=(p[i].first+p[j].first)*common;
y+=(p[i].second+p[j].second)*common;
}
ar *= 0.5;
x /= (6*ar);
y /= (6*ar);
printf("area: %.2f, xc: %.2f, yc: %.2f\n", ar, x, y);
}