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