Как вычислить центроид многоугольника, если заданы вершины многоугольника?

Question

http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon

Я посетил выше ссылку и пытался осуществить формулу сформулировать центроид не-самопересекающийся замкнутого многоугольник, определенный п вершин (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.

Answer 1

Я вижу следующие вопросы:

1. ar, x и y не инициализируются.

2. Расчет неправильно в линиях:

   x+=((p[i].first+p[i+1].first)*ar); 
   y+=((p[i].second+p[i+1].second)*ar); 
   

3. Вы не хватает одной итерации цикла с помощью:

   for(i=0;i<points-1;i++) 
   

Вот версия функции, которая работает для me:

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); 
} 

Answer 2

есть целый пару вещей, чтобы изменить в коде:

• Как заметил @R Сах, ar, x и y должны быть инициализированы до нуля перед циклом for. В противном случае вывод может быть неправильным, или он может меняться при разных прогонах.
• На итерации j, ar является

Так x+=(p[i].first+p[i+1].first)*ar; является ошибочным, так как оно должно быть:

• Присмотритесь на линии после формулы на wikipedia page

В этих формулах вершины предполагаются быть пронумерованы в порядке их появления по периметру полигона, и предполагается, что вершина (х, уп), чтобы быть таким же, как (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 не обеспечивается ...