Graphics

Polygon Area and Centroid

Lab Report

Area and Centroid of a Non-Convex Polygon

Purpose
The purpose of this experiment is to demonstrate two ways to compute the area of a polygon, whose coordinates are defined in "world" coordinates.   An additional method that can be applied only to triangles (Heron's formula) is also demonstrated.

Materials and Equipment

Software Requirements
Windows 95/98/NT/2000
Delphi 3/4/5 (to recompile) 
AreaAndCentroid.EXE

Hardware Requirements
VGA display

Procedure

1. Double click on the AreaAndCentroid.EXE icon to start the program.
   
2. The Scalene Triangle button will be depressed showing the three methods of computing area for an arbitrary triangle.  The blue "+" shows the location of the centroid.
   
3. Press the Convex Octagon button to see the area computed for a non-regular, but convex, octagon.
   
4. Press the Circle Approx. button to see the approximate area of a unit circle based on a N-agon, where N is 50 at first.  Experiment with other values of N from 3 to 999.
   
5. Press either the Non-Convex 1 or 2 buttons to see the area computed for a non-convex polygon.  (Briefly, in a non-convex polygon, part of a line drawn between two interior points lies outside the polygon.)
   

Discussion
Method 1 in calculating the area of a polygon  is based on Green's Theorem in a plane.  Given points (x_i, y_i), i = 0, ..., n, with x₀ = x_n and y₀ = y_n, the following formula can be used for rapidly calculating the area of a polygon in a plane:

where

The area computed this way is a signed value, where a negative sign indicates the vertices are in clockwise order and a positive sign indicates the vertices are in a counterclockwise order.

An interesting special case of this formula is for the triangle with the vertices (a,b), (c,d), (e,f), which can be written in compact form using the following matrix determinant:

The centroid and area can be computed at the same time.  The coordinates for the centroid

of a closed planar region R are:

 where

Look at the PolygonArea or PolygonCentroid functions in the PolygonLibrary.PAS unit for the implementation of these formulas.  Find this method explained in "Centroid of a Polygon" in Graphics Gems IV or in Chapter 8, "Image Measurements," in The Image Processing Handbook.

See Frank van het Veld's comments about numerical difficulties that can be encountered using this method, and Manuel Martin's comments about using relative coordinates to minimize loss of accuracy.

Method 2 in calculating a polygon's area is based on counting pixels.  First, an in-memory bitmap is filled with a solid color.  The polygon is plotted with a specified border color.  Finally, the "outside" is floodfilled with a background color.  The area is computed from the ratio of the solid color to the total number of pixels times the area in real coordinates.  An option is present (inside the program)  to include all, some or none of the "area" of the border line.  Normally, half of this area should be included.  

A 1024-by-1024 pf8bit in-memory bitmap was used in this program for Method 2.  The CalculateEnclosedArea function in the ScreenAreaAndCentroid.PAS unit has parameters to allow other sizes of in-memory bitmaps.

The PaletteIndex function was used to define colors in the pf8bit bitmap to avoid palette problems with 256-color displays.

A third method, which only applies to a triangle (the "Scalene triangle" option in this program), uses Heron's formula to compute the area, A,  of a triangle.  "s" is defined as the "half-perimeter" of a any triangle with sides of length of a, b and c:

s = (a + b + c) / 2

Heron's formula can be found in the CRC Standard Mathematical Tables.

Comparison of Methods
areas[unit²]

See Paul Bourke's Calculating the area and centoid of a polygon at 
http://astronomy.swin.edu.au/~pbourke/geometry/polyarea 

For Point in Polygon links, see efg's Delphi Graphics Algorithms page or (non-Delphi) Graphics page.

Related:  

- Paul Nicholls' UseNet Post about how to compute polygon area using 3D points
- Clive Tooth's UseNet Post about Area of Spherical Triangle
- efg's E-mail to Engineering Student at kmutt about how to computer perimeter of an object

Conclusions
Assuming the values from Method 1 (Green's Theorem) are the "exact" values, the values from Method 2 (pixel counting) are excellent approximations -- less than 0.1% error.

Thanks to Miroslav Kolar for pointing out an inaccuracy in the description of the formulas given above.   (May 2000)   
Thanks to Gary Williams for correcting an inaccuracy in the comments of the source code.  (January 2001)

Keywords
polygon area, polygon centroid, clockwise/counterclockwise order, Green's Theorem, pixel counting, Heron's formula, world coordinates, device coordinates, PaletteIndex, Canvas.FillRect, Canvas.Polyline, Canvas.FloodFill

Download
Delphi 3/4/5 Source Code and EXE (140 KB):  PolygonArea.ZIP

Updated 14 September 2004

since 8 Dec 1998