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

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

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) ???

I think so, yes.

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

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

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

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