Shoelace formula

From Wikipedia, the free encyclopedia
  (Redirected from Gauss's area formula)
Jump to: navigation, search

The shoelace formula, or shoelace algorithm, is a mathematical algorithm to determine the area of a simple polygon whose vertices are described by ordered pairs in the plane.[1] The user cross-multiplies corresponding coordinates to find the area encompassing the polygon, and subtracts it from the surrounding polygon to find the area of the polygon within. It is called the shoelace formula because of the constant cross-multiplying for the coordinates making up the polygon, like tying shoelaces.[1] It is also sometimes called the shoelace method. It is also known as Gauss's area formula, after Carl Friedrich Gauss. It has applications in surveying and forestry,[2] among other areas. It is also called the surveyor's formula.[3]

The formula was described by Meister (1724-1788) in 1769[4] and by Gauss in 1795. It can be verified by dividing the polygon into triangles, but it can also be seen as a special case of Green's theorem.

The area formula is derived by taking each edge AB, and calculating the (signed) area of triangle ABO with a vertex at the origin O, by taking the cross-product (which gives the area of a parallelogram) and dividing by 2. As one wraps around the polygon, these triangles with positive and negative area will overlap, and the areas between the origin and the polygon will be cancelled out and sum to 0, while only the area inside the reference triangle remains. This is why the formula is called the Surveyor's Formula, since the "surveyor" is at the origin; if going counterclockwise, positive area is added when going from left to right and negative area is added when going from right to left, from the perspective of the origin.

Definition[edit]

The formula can be represented by the expression:

 \begin{align} \mathbf{A} & = {1 \over 2} \Big | \sum_{i=1}^{n-1} x_iy_{i+1} + x_ny_1 - \sum_{i=1}^{n-1} x_{i+1}y_i - x_1y_n \Big | \\
 & = {1 \over 2}|x_1y_2 + x_2y_3 + \cdots + x_{n-1}y_n + x_ny_1 - x_2y_1 - x_3y_2 - \cdots - x_ny_{n-1} - x_1y_n| \\ \end{align}

where

  • A is the area of the polygon,
  • n is the number of sides of the polygon, and
  • (xiyi), i = 1, 2,..., n are the vertices (or "corners") of the polygon.

Alternatively:[2][5][6]

\mathbf{A} = {1 \over 2} \Big | \sum_{i=1}^{n} x_i(y_{i+1}-y_{i-1}) \Big | = {1 \over 2} \Big | \sum_{i=1}^{n} y_i(x_{i+1}-x_{i-1}) \Big | = {1 \over 2} \Big | \sum_{i=1}^{n} x_iy_{i+1}-x_{i+1}y_i \Big | = {1 \over 2} \Big | \sum_{i=1}^{n} \det\begin{pmatrix} x_i & x_{i+1} \\ y_i & y_{i+1} \end{pmatrix} \Big |

where xn+1 = x1 and x0 = xn, as well as yn+1 = y1 and y0 = yn.

If the points are labeled sequentially in the counterclockwise direction, then the above determinants are positive and the absolute value signs can be omitted;[3] if they are labeled in the clockwise direction, the determinants will be negative. This is because the formula can be viewed as a special case of Green's Theorem.

Examples[edit]

The user must know the points of the polygon in a Cartesian plane. For example, take a triangle with coordinates {(2, 1), (4, 5), (7, 8)}. Take the first x-coordinate and multiply it by the second y-value, then take the second x-coordinate and multiply it by the third y-value, and repeat, and repeat again, until you do it for all points. This can be defined by this formula:[7]

 \mathbf{A}_\text{tri.} = {1 \over 2}|x_1y_2 + x_2y_3 + x_3y_1 - x_2y_1 - x_3y_2 - x_1y_3|

for xi and yi representing each respective coordinate. This formula is just the expansion of those given above for the case n = 3. Using it, one can find that the area of the triangle equals one half of the absolute value of 10 + 32 + 7 − 4 − 35 − 16, which equals 3. The number of variables depends on the number of sides of the polygon. For example, a pentagon will be defined up to x5 and y5:

 \mathbf{A}_\text{pent.} = {1 \over 2}|x_1y_2 + x_2y_3 + x_3y_4 + x_4y_5 + x_5y_1 - x_2y_1 - x_3y_2 - x_4y_3 - x_5y_4 - x_1y_5|

A quadrilateral will be defined up to x4 and y4:

 \mathbf{A}_\text{quad.} = {1 \over 2}|x_1y_2 + x_2y_3 +x_3y_4 + x_4y_1 - x_2y_1 - x_3y_2 - x_4y_3 - x_1y_4|

More complex example[edit]

Consider the polygon defined by the points (3,4), (5,11), (12,8), (9,5), and (5,6), and illustrated in the following diagram:

Figure of this example

The area of this polygon is:


\begin{align}
\mathbf{A} & = {1 \over 2}|3 \times 11 + 5 \times 8 + 12 \times 5 + 9 \times 6 + 5 \times 4 \\
& {} \qquad {} - 4 \times 5 - 11 \times 12 - 8 \times 9 - 5 \times 5 - 6 \times 3| \\[10pt]
& = {60 \over 2} = 30
\end{align}

Explanation of name[edit]

The reason this formula is called the shoelace formula is because of a common method used to evaluate it. This method uses matrices. As an example, choose the triangle with vertices (2,4), (3,−8), and (1,2). Then construct the following matrix by “walking around” the triangle and ending with the initial point.[8]

 \begin{bmatrix} 2 & 4 \\ 3 & -8 \\ 1 & 2 \\ 2 & 4 \end{bmatrix}

First, draw diagonal down and to the right slashes (as shown below),

  ShoelaceMatrix2.GIF

and multiply the two numbers connected by each slash, then add all the products: (2 × −8) + (3 × 2) + (1 × 4) = −6. Do the same thing with slashes diagonal down and to the left (shown below with former slashes):

  ShoelaceMatrix3.GIF

(4 × 3) + (−8 × 1) + (2 × 2) = 8. Then take the difference of these two numbers: |(−6 )−( 8)| = 14. Halving this gives the area of the triangle: 7. Organizing the numbers like this makes the formula easier to recall and evaluate. With all the slashes drawn, the matrix loosely resembles a shoe with the laces done up, giving rise to the algorithm's name.

References[edit]

  1. ^ a b Dahlke, Karl. "Shoelace Formula". Retrieved 9 June 2008. 
  2. ^ a b Hans Pretzsch, Forest Dynamics, Growth and Yield: From Measurement to Model, Springer, 2009, ISBN 3-540-88306-1, p. 232.
  3. ^ a b Bart Braden (1986). "The Surveyor’s Area Formula". The College Mathematics Journal 17 (4): 326–337. doi:10.2307/2686282. 
  4. ^ Meister, A. L. F. (1769), "Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus", Nov. Com. Gött. (in Latin) 1: 144 .
  5. ^ Shoelace Theorem, Art of Problem Solving Wiki.
  6. ^ Weisstein, Eric W. "Polygon Area". Wolfram MathWorld. Retrieved 24 July 2012. 
  7. ^ Richard Rhoad; George Milauskas; Robert Whipple (1991). Geometry for Enjoyment and Challenge (new ed.). McDougal Littell. pp. 717–718. ISBN 0-86609-965-4. 
  8. ^ IMSA JHMC Guide, Page. 10 "Shoelace" by Cindy Xi