# Thread: Polygon Area and Centroid :(

1. ## Polygon Area and Centroid :(

I don't know why this code is giving wrong answers. Is there any code you know or link ???

Code:
```#include<iostream.h>
#include<conio.h>

typedef struct
{
double x,y;
} Point;

inline float isLeft( Point P0, Point P1, Point P2 )
{
return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}

int ConvexHull( Point* P, int n, Point* H )
{
int    bot=0, top=(-1);
int    i;

int minmin = 0, minmax;
float xmin = P[0].x;

for (i=1; i<n; i++)
if (P[i].x != xmin) break;

minmax = i-1;

if (minmax == n-1)
{
H[++top] = P[minmin];
if (P[minmax].y != P[minmin].y)
H[++top] = P[minmax];
H[++top] = P[minmin];
return top+1;
}

int maxmin, maxmax = n-1;
float xmax = P[n-1].x;

for (i=n-2; i>=0; i--)
if (P[i].x != xmax) break;

maxmin = i+1;

H[++top] = P[minmin];
i = minmax;

while (++i <= maxmin)
{
if (isLeft( P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)
continue;

while (top > 0)
{
if (isLeft( H[top-1], H[top], P[i]) > 0)
break;
else
top--;
}
H[++top] = P[i];
}

if (maxmax != maxmin)
H[++top] = P[maxmax];

bot = top;
i = maxmin;

while (--i >= minmax)
{
if (isLeft( P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)
continue;
while (top > bot)
{
if (isLeft( H[top-1], H[top], P[i]) > 0)
break;
else
top--;
}
H[++top] = P[i];
}
if (minmax != minmin)
H[++top] = P[minmin];

return top+1;
}

double PolygonArea(Point *polygon,int N)
{
int i,j;
double area = 0;

for (i=0;i<N;i++)
{
j = (i + 1) % N;
area += polygon[i].x * polygon[j].y;
area -= polygon[i].y * polygon[j].x;
}

area /= 2;
return(area < 0 ? -area : area);
}

double Cx(Point *polygon,double A,int N)
{
int i,j;
double X = 0;

for (i=0;i<N;i++)
{
j = (i + 1) % N;
X += polygon[i].x * polygon[j].y;
X -= polygon[i].y * polygon[j].x;
X *= polygon[i].x + polygon[j].x;
}

return (X/(6*A));
}

double Cy(Point *polygon,double A,int N)
{
int i,j;
double Y = 0;

for (i=0;i<N;i++)
{
j = (i + 1) % N;
Y += polygon[i].x * polygon[j].y;
Y -= polygon[i].y * polygon[j].x;
Y *= polygon[i].y + polygon[j].y;
}

return (Y/(6*A));
}

int main()
{
Point p[100],ch[100];

cout << " ! CONVEX HULL TEST ! " << endl;

cout << " How many points : ";
int n;
cin >> n;

for(int i=0;i<n;++i)
{
cout << "POINT " << (i+1) << " : ";
cin >> p[i].x >> p[i].y;
}

cout << " Your entered points : " << endl;

for(int i=0;i<n;++i)
{
cout << "POINT " << (i+1) << " : ";
cout << p[i].x << "   " << p[i].y << endl;
}

int t = ConvexHull(p,n,ch);

cout << " Total : " << t << endl;

for(int i=0;i<t;++i)
{
cout << "POINT " << (i+1) << " : ";
cout << ch[i].x << "   " << ch[i].y << endl;
}

double Area = PolygonArea(ch,t);

cout << " The area of the convex hull is : " << Area << endl;
cout << " The centre of Hull : " << Cx(ch,Area,t) << "  " << Cy(ch,Area,t);

getche();
return 0;
}```

2. Oh! Here is the algo:

http://astronomy.swin.edu.au/~pbourk...etry/polyarea/

and I have problem in finding the Cx and Cy.........

Please help

3. Code:
```double Cx(Point *polygon,double A,int N)
{
int i,j;
double X = 0;

for (i=0;i<N;i++)
{
j = (i + 1) % N;
X += polygon[i].x * polygon[j].y;
X -= polygon[i].y * polygon[j].x;
X *= polygon[i].x + polygon[j].x;
}

return (X/(6*A));
}

double Cy(Point *polygon,double A,int N)
{
int i,j;
double Y = 0;

for (i=0;i<N;i++)
{
j = (i + 1) % N;
Y += polygon[i].x * polygon[j].y;
Y -= polygon[i].y * polygon[j].x;
Y *= polygon[i].y + polygon[j].y;
}

return (Y/(6*A));
}```
Do they fit with the algo shown (linked above) ???

4. I think so, yes.

5. At least it's about the same as the Java code given in the link.

6. >>return (Y/(6*A));
Try using 6.0 instead of just 6.

7. Yeah, that's right, the multiplication was always on the total sum of what was previously calculated.

8. Thanks! to you all
I am trying! If any problem arises I'll be back again

Popular pages Recent additions