Click here to Skip to main content
15,880,956 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
C++
#include <iostream.h>
 #include <graphics.h>
 #include    <conio.h>
 #include     <math.h>

 void show_screen( );

 void Polygon(const int,const int []);

 void Line(const int,const int,const int,const int);

 int main( )
    {
       int driver=VGA;
       int mode=VGAHI;

       int n=0;

       do
      {
	 show_screen( );

	 gotoxy(12,13);
	 cout<<"Enter the number of points : ";
	 cin>>n;

	 int *coordinates=new int[(n*2)];

	 for(int count=0;count<n;count++)>
	{
	   gotoxy(8,18);
	   cout<<"Coordinates of Point-"<<(count+1)<<" (x"<<(count+1)<<",y"<<(count+1)<<") :";


	   gotoxy(12,21);
	   cout<<"Enter the value of x"<<(count+1)<<" = ";
	   cin>>coordinates[(count*2)];

	   gotoxy(12,22);
	   cout<<"Enter the value of y"<<(count+1)<<" = ";
	   cin>>coordinates[((count*2)+1)];

	   gotoxy(8,18);
	   cout<<"                                            ";

	   gotoxy(12,21);
	   cout<<"                                            ";

	   gotoxy(12,22);
	   cout<<"                                            ";
	 }

	 initgraph(&driver,&mode,"c:\\tc\\Bgi");

	 setcolor(15);
	   Polygon(n,coordinates);

	     delete coordinates;

	 setcolor(15);
	   outtextxy(110,460,"Press <enter> to continue or any other key to exit.");

	 int key=int(getch( ));

	 if(key!=13)
	break;
      }
       while(1);

       return 0;
    }

 void Polygon(const int n,const int coordinates[])
    {
       if(n>=2)
      {
	 Line(coordinates[0],coordinates[1],
			 coordinates[2],coordinates[3]);

	 for(int count=1;count<(n-1);count++)
	Line(coordinates[(count*2)],coordinates[((count*2)+1)],
			coordinates[((count+1)*2)],
			coordinates[(((count+1)*2)+1)]);
      }
    }

void Line(const int x_1,const int y_1,const int x_2,const int y_2)
    {
       int color=getcolor( );

       int x1=x_1;
       int y1=y_1;

       int x2=x_2;
       int y2=y_2;

       if(x_1>x_2)
      {
	 x1=x_2;
	 y1=y_2;

	 x2=x_1;
	 y2=y_1;
      }

       int dx=abs(x2-x1);
       int dy=abs(y2-y1);
       int inc_dec=((y2>=y1)?1:-1);

       if(dx>dy)
      {
	 int two_dy=(2*dy);
	 int two_dy_dx=(2*(dy-dx));
	 int p=((2*dy)-dx);

	 int x=x1;
	 int y=y1;

	 putpixel(x,y,color);

	 while(x<x2)>
	{
	   x++;

	   if(p<0)
	      p+=two_dy;

	   else
	      {
	     y+=inc_dec;
	     p+=two_dy_dx;
	      }

	   putpixel(x,y,color);
	}
      }

       else
      {
	 int two_dx=(2*dx);
	 int two_dx_dy=(2*(dx-dy));
	 int p=((2*dx)-dy);

	 int x=x1;
	 int y=y1;

	 putpixel(x,y,color);

	 while(y!=y2)
	{
	   y+=inc_dec;

	   if(p<0)
	      p+=two_dx;

	   else
	      {
	     x++;
	     p+=two_dx_dy;
	      }

	   putpixel(x,y,color);
	}
      }
    }

void show_screen( )
    {
       restorecrtmode( );
       textmode(C4350);

       textbackground(1);
       cprintf(" Polygon ");
       textbackground(8);


       gotoxy(1,2);
    }

how to calculate area and perimeter of polygon?
Posted
Updated 30-Jun-15 0:43am
v2
Comments
Stefan_Lang 30-Jun-15 6:45am    
I've fixed your code formatting. Please next time do so yourself, using the formatting buttons [code] or [var] at the top of the edit box, and verify the result in the preview shown below.
Kenneth Haugland 30-Jun-15 6:58am    
http://www.mathopenref.com/coordpolygonarea.html

There's a simple algorithm for calculating the area of a polygon:

1. Choose one point P1. Interpret this point as 3D point by setting the z-coordinate to 0.
2. For all remaining (n-1) points Pi:
- interpret Pi and Pi+1 as 3D points by setting the z-coordinate to 0.
- calculate the vector product (Pi-P1)x(Pi+1-P1)
- add up the resulting vectors
3. the length of the vector sum is the total area of the polygon

The concept behind this is that the length of the vector you get from each vector product corresponds to the area of the triangle of the three involved points. At concave points, however, the vector will point in the opposite direction, and therefore the area will be subtracted rather than added. If you draw a few example polygons you'll see that it is indeed necessary to subtract these areas rather than add them.

P.S.: you don't actually have to introduce 3D vectors, as the vector product will always have it's x and y coordinate at 0, so you only need to calculate the z-coordinate, which happens to be the 2D determinant of the two 2D vectors (Pi-P1) and (Pi+1-P1).

P.P.S.: fixed the index values. See for instance paragraph 2.0.1 in here: http://www.faqs.org/faqs/graphics/algorithms-faq/[^]

Another P.S.:
I've tried to pinpoint the source of this algorithm, but found that what I described here is a specialized version that I actually used to determine the orientation of a polygon, not it's area, although it does calculate the area as described. In fact, if you're just interested in the area, the first point can be any point, including (0,0), and the firmula you get, then can be found on various sites, e. g. http://mathworld.wolfram.com/PolygonArea.html[^] or here: https://en.wikipedia.org/wiki/Shoelace_formula[^]
 
Share this answer
 
v5
Comments
Kenneth Haugland 30-Jun-15 10:07am    
I think this formula has been known since Archimedes, as it is just a Cauchy Integration (which ironically enough was known to Archimedes).

Oh, the formula does not work if the Polygon is self intersecting.
Stefan_Lang 30-Jun-15 10:52am    
IIRC Cauchy integration would more like this: https://www.mathsisfun.com/geometry/area-irregular-polygons.html

It does result in a similar formula that turns out to be algebraically identical (of course), but the method used to derive it is slightly different.

And yes, it indeed doesn't work for self-intersecting polygons. I'll leave that as an exercise to the interested reader ;-p
Kenneth Haugland 30-Jun-15 12:52pm    
Yes, you are right. The reason for saying that Archimedes knew it is this:
https://en.wikipedia.org/wiki/Archimedes_Palimpsest
The areas can get computed via triangulation: you seperate the polygon in triangles and add their areas. The perimeter is more complex. You need to find all outsides and add them.

For that you may look for some algorhitm. I would write a test function to proof that a points is NOT in a triangle, so it is part of a next triangle.

Or maybe you compute the centerpoint of all points, than compute the vector (and angle) to sort the points for triangles and perimeter.

Good luck.
 
Share this answer
 
Comments
Matt T Heffron 30-Jun-15 12:47pm    
Perimeter is just the sum of the lengths of the edge line segments, so it is quite easy.
I think you're thinking of the "convex hull" of the polygon which would have the complexity you imply.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900