|Polygon Area and Centroid||Lab Report|
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
Delphi 3/4/5 (to recompile)
Method 1 in calculating the area of a polygon is based on Green's Theorem in a plane. Given points (xi, yi), i = 0, ..., n, with x0 = xn and y0 = yn, the following formula can be used for rapidly calculating the area of a polygon in a plane:
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:
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 vhV'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
|Case||Method 1||Method 2||Method 3|
|Non-Convex Polygon 1||0.3050||0.3054||N/A|
|Non-Convex Polygon 2||119.24||119.17||N/A|
See Paul Bourke's Calculating
the area and centoid of a polygon.
For Point in Polygon links, see efg's Delphi Graphics Algorithms page or (non-Delphi) Graphics page.
- 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
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)
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
Delphi 3/4/5 Source Code and EXE (140 KB): PolygonArea.ZIP
Since 8 Dec 1998