Polygon Area

From CGAFaq

The signed area of a polygon can be computed in linear time by a simple sum. The key formula is this:

If the polygon lies in the xy plane and the coordinates of vertex v_i are x_i and y_i, twice the signed area of a polygon is given by

2 A(P) = ∑_i=0^n-1 (x_i y_i+1 - y_i x_i+1).

Here n is the number of vertices of the polygon, and index arithmetic is mod n, so that x_n = x₀, etc. A rearrangement of terms in this equation can save multiplications and operate on coordinate differences, and so may be both faster and more accurate:

2 A(P) = ∑_i=0^n-1 ( x_i (y_i+1 - y_i-1) )

Here again modular index arithmetic is implied, with n=0 and -1=n-1. This can be avoided by extending the x[] and y[] arrays up to [n+1] with x[n]=x[0], y[n]=y[0] and y[n+1]=y[1], and using instead

2 A(P) = ∑_i=1ⁿ ( x_i (y_i+1 - y_i-1) )

References: [O'Rourke (C)] Thm. 1.3.3, p. 21; [Gems II] pp. 5-6: "The Area of a Simple Polygon", Jon Rokne. Dan Sunday's explanation:

• http://GeometryAlgorithms.com/Archive/algorithm_0101/

Here is a Matlab statement to calculate the area:

  area = sum(x([2:end 1]).*(y([3:end 1 2])-y))/2;

To find the area of a planar polygon not in the x-y plane, use:

2 A(P) = | N . (∑_i=1ⁿ (v_i x v_i+1)) |

where N is a unit vector normal to the plane. The '.' represents the dot product operator, the 'x' represents the cross product operator, and '||' is the absolute value function.

• [Gems II] pp. 170-171:

"Area of Planar Polygons and Volume of Polyhedra", Ronald N. Goldman.