Polygon Area and Centroid :(

This is a discussion on Polygon Area and Centroid :( within the C++ Programming forums, part of the General Programming Boards category; I don't know why this code is giving wrong answers. Is there any code you know or link ??? Code: ...

  1. #1
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104

    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;
    }
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  2. #2
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    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
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  3. #3
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    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) ???
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    I think so, yes.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    At least it's about the same as the Java code given in the link.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    >>return (Y/(6*A));
    Try using 6.0 instead of just 6.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Yeah, that's right, the multiplication was always on the total sum of what was previously calculated.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Thanks! to you all
    I am trying! If any problem arises I'll be back again
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21