Difference between revisions of "Shoelace Theorem"

(New page: '''Shoelace Theorem''' is a nifty formula for finding the area of a polygon given the coordinates of it's vertices. ==Theorem== Let the coordinates, in "clockwise" orde...)
 
(Proof 2)
 
(50 intermediate revisions by 27 users not shown)
Line 1: Line 1:
'''Shoelace Theorem''' is a nifty formula for finding the [[area]] of a [[polygon]] given the coordinates of it's [[vertex|vertices]].
+
The '''Shoelace Theorem''' is a nifty formula for finding the [[area]] of a [[polygon]] given the [[Cartesian coordinate system | coordinates]] of its [[vertex|vertices]].
  
 
==Theorem==
 
==Theorem==
Let the coordinates, in "clockwise" order, be <math>(a_1, b_1)</math>, <math>(a_2, b_2)</math>, ... , <math>(a_n, b_n)</math>. The area of the polygon is
+
Suppose the polygon <math>P</math> has vertices <math>(a_1, b_1)</math>, <math>(a_2, b_2)</math>, ... , <math>(a_n, b_n)</math>, listed in clockwise order. Then the area (<math>A</math>) of <math>P</math> is
  
<cmath>\dfrac{1}{2} |a_1b_2+a_2b_3+\cdots +a_nb_1-b_1a_2-b_2a_3-\cdots -b_na_1|.</cmath>
+
<cmath>A = \dfrac{1}{2} \left|(a_1b_2 + a_2b_3 + \cdots + a_nb_1) - (b_1a_2 + b_2a_3 + \cdots + b_na_1) \right|</cmath>
  
Shoelace Theorem gets it's name by listing the coordinates like so:
+
You can also go counterclockwise order, as long as you find the absolute value of the answer.
  
<cmath>(a_1, b_1)</cmath>
+
The Shoelace Theorem gets its name because if one lists the coordinates in a column,
<cmath>(a_2, b_2)</cmath>
+
<cmath>\begin{align*}
<cmath>\vdots</cmath>
+
(a_1 &, b_1) \\
<cmath>(a_n, b_n)</cmath>
+
(a_2 &, b_2) \\
<cmath>(a_1, b_1)</cmath>
+
& \vdots \\
 +
(a_n &, b_n) \\
 +
(a_1 &, b_1) \\
 +
\end{align*}</cmath>
 +
and marks the pairs of coordinates to be multiplied,
 +
<asy>
 +
unitsize(1cm);
 +
string[] subscripts={"$1$","$2$"," ","$n$","$1$"};
 +
for(int i=1; i < 6; ++i)
 +
{
 +
  label(i==3 ? "$\vdots$" : "$a$",(0,-i*.7));
 +
  label(i==3 ? "$\vdots$" : "$b$",(1.2,-i*.7));
 +
  label(subscripts[i-1],(0,-i*.7),SE,fontsize(9pt));
 +
  label(subscripts[i-1],(1.2,-i*.7),SE,fontsize(9pt));
 +
}
 +
for(int i=1; i<5; ++i)
 +
  draw((0.3,-i*.7)--(1,-(i+1)*.7));
  
==Proof==
+
pair c=(1.2,0);
{{incomplete|proof}}
+
label("$-$",shift(c)*(1.2,-2.1));
 +
label("$A=\frac12$",shift(-c)*(0,-2.1));
 +
draw(shift(-1/3*c)*((0,-.5)--(0,-3.9)));
 +
draw(shift(13/3*c)*((0,-.5)--(0,-3.9)));
 +
 
 +
for(int i=1; i < 6; ++i)
 +
{
 +
  label(i==3 ? "$\vdots$" : "$a$",shift(3*c)*(0,-i*.7));
 +
  label(i==3 ? "$\vdots$" : "$b$",shift(3*c)*(1.2,-i*.7));
 +
  label(subscripts[i-1],shift(3*c)*(0,-i*.7),SE,fontsize(9pt));
 +
  label(subscripts[i-1],shift(3*c)*(1.2,-i*.7),SE,fontsize(9pt));
 +
}
 +
for(int i=1; i<5; ++i)
 +
  draw(shift(3*c)*(0.3,-(i+1)*.7)--shift(3*c)*(1,-i*.7));
 +
</asy>
 +
the resulting image looks like laced-up shoes.
 +
 
 +
==Other Forms==
 +
This can also be written in form of a summation <cmath>A = \dfrac{1}{2} \left|\sum_{i=1}^n{(x_{i+1}+x_i)(y_{i+1}-y_i)}\right|</cmath>
 +
or in terms of determinants as <cmath>A = \dfrac{1}{2} \left|\sum_{i=1}^n{\det\begin{pmatrix}x_i&x_{i+1}\\y_i&y_{i+1}\end{pmatrix}}\right|</cmath>
 +
which is useful in the <math>3D</math> variant of the Shoelace theorem,
 +
 
 +
or as the special case of Green's Theorem
 +
<center>
 +
<math>\tilde{A}=\iint\left(\frac{\partial M}{\partial x}-\frac{\partial L}{\partial y}\right)dxdy=</math><font size="6">∳</font><math>(Ldx+Mdy)</math>
 +
</center>
 +
where <math>L=-y</math> and <math>M=0</math> so <math>\tilde{A}=A</math>.
 +
 
 +
==Proof 1==
 +
Claim 1: The area of a triangle with coordinates <math>A(x_1, y_1)</math>, <math>B(x_2, y_2)</math>, and <math>C(x_3, y_3)</math> is <math>\frac{|x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2|}{2}</math>.
 +
 
 +
===Proof of claim 1:===
 +
 
 +
Writing the coordinates in 3D and translating <math>\triangle ABC</math> so that <math>A=(0, 0, 0)</math> we get the new coordinates <math>A'(0, 0, 0)</math>, <math>B(x_2-x_1, y_2-y_1, 0)</math>, and <math>C(x_3-x_1, y_3-y_1, 0)</math>. Now if we let <math>\vec{b}=(x_2-x_1 \quad y_2-y_1 \quad 0)</math> and <math>\vec{c}=(x_3-x_1 \quad y_3-y_1 \quad 0)</math> then by definition of the cross product <math>[ABC]=\frac{||\vec{b} \times \vec{c}||}{2}=\frac{1}{2}||(0 \quad 0 \quad x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2)||=\frac{x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2}{2}</math>.
 +
 
 +
===Proof:===
 +
 
 +
We will proceed with induction.
 +
 
 +
By claim 1, the shoelace theorem holds for any triangle. We will show that if it is true for some polygon <math>A_1A_2A_3...A_n</math> then it is also true for <math>A_1A_2A_3...A_nA_{n+1}</math>.
 +
 
 +
We cut <math>A_1A_2A_3...A_nA_{n+1}</math> into two polygons, <math>A_1A_2A_3...A_n</math> and <math>A_1A_nA_{n+1}</math>. Let the coordinates of point <math>A_i</math> be <math>(x_i, y_i)</math>. Then, applying the shoelace theorem on  <math>A_1A_2A_3...A_n</math> and <math>A_1A_nA_{n+1}</math> we get
 +
 
 +
<cmath>[A_1A_2A_3...A_n]=\frac{1}{2}\sum_{i=1}^{n}(x_iy_{i+1}-x_{i+1}y_i)</cmath>
 +
<cmath>[A_1A_nA_{n+1}]=\frac{1}{2}(x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2)</cmath>
 +
 
 +
Hence
 +
 
 +
<cmath>[A_1A_2A_3...A_nA_{n+1}]=[A_1A_2A_3...A_n]+[A_1A_nA_{n+1}]=\frac{1}{2}\sum_{i=1}^{n}(x_iy_{i+1}-x_{i+1}y_i)+\frac{1}{2}(x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2)</cmath>
 +
<cmath>=\frac{1}{2}((x_2y_1+x_3y_2+...+x_{n+1}y_n+x_1y_{n+1})-(x_1y_2+x_2y_3+...+x_ny_{n+1}+x_{n+1}y_1))=\boxed{\frac{1}{2}\sum_{i=1}^n(x_iy_{i+1}-x_{i+1}y_i)}</cmath>
 +
 
 +
As claimed.
 +
 
 +
~ShreyJ
 +
 
 +
==Proof 2==
 +
Let <math>\Omega</math> be the set of points belonging to the polygon.
 +
We have that
 +
<cmath>
 +
A=\int_{\Omega}\alpha,
 +
</cmath>
 +
where <math>\alpha=dx\wedge dy</math>.
 +
The volume form <math>\alpha</math> is an exact form since <math>d\omega=\alpha</math>, where
 +
<cmath>
 +
\omega=\frac{x\,dy}{2}-\frac{y\,dx}{2}.\label{omega}
 +
</cmath>
 +
Using this substitution, we have
 +
<cmath>
 +
\int_{\Omega}\alpha=\int_{\Omega}d\omega.
 +
</cmath>
 +
Next, we use the Theorem of Stokes to obtain
 +
<cmath>
 +
\int_{\Omega}d\omega=\int_{\partial\Omega}\omega.
 +
</cmath>
 +
We can write <math>\partial \Omega=\bigcup A(i)</math>, where <math>A(i)</math> is the line
 +
segment from <math>(x_i,y_i)</math> to <math>(x_{i+1},y_{i+1})</math>. With this notation,
 +
we may write
 +
<cmath>
 +
\int_{\partial\Omega}\omega=\sum_{i=1}^n\int_{A(i)}\omega.
 +
</cmath>
 +
If we substitute for <math>\omega</math>, we obtain
 +
<cmath>
 +
\sum_{i=1}^n\int_{A(i)}\omega=\frac{1}{2}\sum_{i=1}^n\int_{A(i)}{x\,dy}-{y\,dx}.
 +
</cmath>
 +
If we parameterize, we get
 +
<cmath>
 +
\frac{1}{2}\sum_{i=1}^n\int_0^1{(x_i+(x_{i+1}-x_i)t)(y_{i+1}-y_i)}-{(y_i+(y_{i+1}-y_i)t)(x_{i+1}-x_i)\,dt}.
 +
</cmath>
 +
Performing the integration, we get
 +
<cmath>
 +
\frac{1}{2}\sum_{i=1}^n\frac{1}{2}[(x_i+x_{i+1})(y_{i+1}-y_i)-
 +
(y_{i}+y_{i+1})(x_{i+1}-x_i)].
 +
</cmath>
 +
More algebra yields the result
 +
<cmath>
 +
\frac{1}{2}\sum_{i=1}^n(x_iy_{i+1}-x_{i+1}y_i).
 +
</cmath>
 +
 
 +
==Proof 3==
 +
This is a very nice approach that directly helps in understanding the sum as terms which are areas of trapezoids.
 +
 
 +
See page 281 in this book (in the Polygon Area section.)
 +
https://cses.fi/book/book.pdf
 +
 
 +
(The only thing that needs to be modified in this proof is that one must shift the entire polygon up by k, until all the y coordinates are positive, but this term gets canceled in the resulting sum.)
 +
 
 +
== Problems ==
 +
=== Introductory ===
 +
In right triangle <math>ABC</math>, we have <math>\angle ACB=90^{\circ}</math>, <math>AC=2</math>, and <math>BC=3</math>. [[Median]]s <math>AD</math> and <math>BE</math> are drawn to sides <math>BC</math> and <math>AC</math>, respectively. <math>AD</math> and <math>BE</math> intersect at point <math>F</math>. Find the area of <math>\triangle ABF</math>.
 +
=== Exploratory ===
 +
Observe that <cmath>\frac12\left|\det\begin{pmatrix}
 +
x_1 & y_1\\
 +
x_2 & y_2
 +
\end{pmatrix}\right|</cmath> is the area of a triangle with vertices <math>(x_1,y_1),(x_2,y_2),(0,0)</math> and <cmath>\frac16\left|\det\begin{pmatrix}
 +
x_1 & y_1 & z_1\\
 +
x_2 & y_2 & z_2\\
 +
x_3 & y_3 & z_3
 +
\end{pmatrix}\right|</cmath> is the volume of a tetrahedron with vertices <math>(x_1, y_1, z_1), (x_2, y_2, z_2),(x_3, y_3, z_3),(0,0,0)</math>. Does a similar formula hold for <math>n</math>Dimensional triangles for any <math>n</math>? If so how can we use this to derive the <math>n</math>D Shoelace Formula?
 +
 
 +
== External Links==
 +
A good explanation and exploration into why the theorem works by James Tanton:
 +
[http://www.jamestanton.com/wp-content/uploads/2012/03/Cool-Math-Essay_June-2014_SHOELACE-FORMULA.pdf]
 +
 
 +
Nice geometric approach and discussion for proving the 3D Shoelace Theorem by Nicholas Patrick and Nadya Pramita: [http://media.icys2018.com/2018/04/IndonesiaPatrickNicholas105190.pdf]
 +
 
 +
Nice integral approach for proving the 3D Shoelace Theorem (ignoring sign of volume) by @george2079: [https://mathematica.stackexchange.com/a/26015]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
[[Category:Geometry]]
 +
[[Category:Theorems]]
 +
AOPS

Latest revision as of 12:24, 9 January 2021

The Shoelace Theorem is a nifty formula for finding the area of a polygon given the coordinates of its vertices.

Theorem

Suppose the polygon $P$ has vertices $(a_1, b_1)$, $(a_2, b_2)$, ... , $(a_n, b_n)$, listed in clockwise order. Then the area ($A$) of $P$ is

\[A = \dfrac{1}{2} \left|(a_1b_2 + a_2b_3 + \cdots + a_nb_1) - (b_1a_2 + b_2a_3 + \cdots + b_na_1) \right|\]

You can also go counterclockwise order, as long as you find the absolute value of the answer.

The Shoelace Theorem gets its name because if one lists the coordinates in a column, \begin{align*} (a_1 &, b_1) \\ (a_2 &, b_2) \\ & \vdots \\ (a_n &, b_n) \\ (a_1 &, b_1) \\ \end{align*} and marks the pairs of coordinates to be multiplied, [asy] unitsize(1cm); string[] subscripts={"$1$","$2$"," ","$n$","$1$"}; for(int i=1; i < 6; ++i) {   label(i==3 ? "$\vdots$" : "$a$",(0,-i*.7));   label(i==3 ? "$\vdots$" : "$b$",(1.2,-i*.7));   label(subscripts[i-1],(0,-i*.7),SE,fontsize(9pt));    label(subscripts[i-1],(1.2,-i*.7),SE,fontsize(9pt));  } for(int i=1; i<5; ++i)   draw((0.3,-i*.7)--(1,-(i+1)*.7));  pair c=(1.2,0); label("$-$",shift(c)*(1.2,-2.1)); label("$A=\frac12$",shift(-c)*(0,-2.1)); draw(shift(-1/3*c)*((0,-.5)--(0,-3.9))); draw(shift(13/3*c)*((0,-.5)--(0,-3.9)));  for(int i=1; i < 6; ++i) {   label(i==3 ? "$\vdots$" : "$a$",shift(3*c)*(0,-i*.7));   label(i==3 ? "$\vdots$" : "$b$",shift(3*c)*(1.2,-i*.7));   label(subscripts[i-1],shift(3*c)*(0,-i*.7),SE,fontsize(9pt));    label(subscripts[i-1],shift(3*c)*(1.2,-i*.7),SE,fontsize(9pt));  } for(int i=1; i<5; ++i)   draw(shift(3*c)*(0.3,-(i+1)*.7)--shift(3*c)*(1,-i*.7)); [/asy] the resulting image looks like laced-up shoes.

Other Forms

This can also be written in form of a summation \[A = \dfrac{1}{2} \left|\sum_{i=1}^n{(x_{i+1}+x_i)(y_{i+1}-y_i)}\right|\] or in terms of determinants as \[A = \dfrac{1}{2} \left|\sum_{i=1}^n{\det\begin{pmatrix}x_i&x_{i+1}\\y_i&y_{i+1}\end{pmatrix}}\right|\] which is useful in the $3D$ variant of the Shoelace theorem,

or as the special case of Green's Theorem

$\tilde{A}=\iint\left(\frac{\partial M}{\partial x}-\frac{\partial L}{\partial y}\right)dxdy=$$(Ldx+Mdy)$

where $L=-y$ and $M=0$ so $\tilde{A}=A$.

Proof 1

Claim 1: The area of a triangle with coordinates $A(x_1, y_1)$, $B(x_2, y_2)$, and $C(x_3, y_3)$ is $\frac{|x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2|}{2}$.

Proof of claim 1:

Writing the coordinates in 3D and translating $\triangle ABC$ so that $A=(0, 0, 0)$ we get the new coordinates $A'(0, 0, 0)$, $B(x_2-x_1, y_2-y_1, 0)$, and $C(x_3-x_1, y_3-y_1, 0)$. Now if we let $\vec{b}=(x_2-x_1 \quad y_2-y_1 \quad 0)$ and $\vec{c}=(x_3-x_1 \quad y_3-y_1 \quad 0)$ then by definition of the cross product $[ABC]=\frac{||\vec{b} \times \vec{c}||}{2}=\frac{1}{2}||(0 \quad 0 \quad x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2)||=\frac{x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2}{2}$.

Proof:

We will proceed with induction.

By claim 1, the shoelace theorem holds for any triangle. We will show that if it is true for some polygon $A_1A_2A_3...A_n$ then it is also true for $A_1A_2A_3...A_nA_{n+1}$.

We cut $A_1A_2A_3...A_nA_{n+1}$ into two polygons, $A_1A_2A_3...A_n$ and $A_1A_nA_{n+1}$. Let the coordinates of point $A_i$ be $(x_i, y_i)$. Then, applying the shoelace theorem on $A_1A_2A_3...A_n$ and $A_1A_nA_{n+1}$ we get

\[[A_1A_2A_3...A_n]=\frac{1}{2}\sum_{i=1}^{n}(x_iy_{i+1}-x_{i+1}y_i)\] \[[A_1A_nA_{n+1}]=\frac{1}{2}(x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2)\]

Hence

\[[A_1A_2A_3...A_nA_{n+1}]=[A_1A_2A_3...A_n]+[A_1A_nA_{n+1}]=\frac{1}{2}\sum_{i=1}^{n}(x_iy_{i+1}-x_{i+1}y_i)+\frac{1}{2}(x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_2y_1-x_3y_2)\] \[=\frac{1}{2}((x_2y_1+x_3y_2+...+x_{n+1}y_n+x_1y_{n+1})-(x_1y_2+x_2y_3+...+x_ny_{n+1}+x_{n+1}y_1))=\boxed{\frac{1}{2}\sum_{i=1}^n(x_iy_{i+1}-x_{i+1}y_i)}\]

As claimed.

~ShreyJ

Proof 2

Let $\Omega$ be the set of points belonging to the polygon. We have that \[A=\int_{\Omega}\alpha,\] where $\alpha=dx\wedge dy$. The volume form $\alpha$ is an exact form since $d\omega=\alpha$, where \[\omega=\frac{x\,dy}{2}-\frac{y\,dx}{2}.\label{omega}\] Using this substitution, we have \[\int_{\Omega}\alpha=\int_{\Omega}d\omega.\] Next, we use the Theorem of Stokes to obtain \[\int_{\Omega}d\omega=\int_{\partial\Omega}\omega.\] We can write $\partial \Omega=\bigcup A(i)$, where $A(i)$ is the line segment from $(x_i,y_i)$ to $(x_{i+1},y_{i+1})$. With this notation, we may write \[\int_{\partial\Omega}\omega=\sum_{i=1}^n\int_{A(i)}\omega.\] If we substitute for $\omega$, we obtain \[\sum_{i=1}^n\int_{A(i)}\omega=\frac{1}{2}\sum_{i=1}^n\int_{A(i)}{x\,dy}-{y\,dx}.\] If we parameterize, we get \[\frac{1}{2}\sum_{i=1}^n\int_0^1{(x_i+(x_{i+1}-x_i)t)(y_{i+1}-y_i)}-{(y_i+(y_{i+1}-y_i)t)(x_{i+1}-x_i)\,dt}.\] Performing the integration, we get \[\frac{1}{2}\sum_{i=1}^n\frac{1}{2}[(x_i+x_{i+1})(y_{i+1}-y_i)- (y_{i}+y_{i+1})(x_{i+1}-x_i)].\] More algebra yields the result \[\frac{1}{2}\sum_{i=1}^n(x_iy_{i+1}-x_{i+1}y_i).\]

Proof 3

This is a very nice approach that directly helps in understanding the sum as terms which are areas of trapezoids.

See page 281 in this book (in the Polygon Area section.) https://cses.fi/book/book.pdf

(The only thing that needs to be modified in this proof is that one must shift the entire polygon up by k, until all the y coordinates are positive, but this term gets canceled in the resulting sum.)

Problems

Introductory

In right triangle $ABC$, we have $\angle ACB=90^{\circ}$, $AC=2$, and $BC=3$. Medians $AD$ and $BE$ are drawn to sides $BC$ and $AC$, respectively. $AD$ and $BE$ intersect at point $F$. Find the area of $\triangle ABF$.

Exploratory

Observe that \[\frac12\left|\det\begin{pmatrix} x_1 & y_1\\ x_2 & y_2 \end{pmatrix}\right|\] is the area of a triangle with vertices $(x_1,y_1),(x_2,y_2),(0,0)$ and \[\frac16\left|\det\begin{pmatrix} x_1 & y_1 & z_1\\ x_2 & y_2 & z_2\\ x_3 & y_3 & z_3 \end{pmatrix}\right|\] is the volume of a tetrahedron with vertices $(x_1, y_1, z_1), (x_2, y_2, z_2),(x_3, y_3, z_3),(0,0,0)$. Does a similar formula hold for $n$Dimensional triangles for any $n$? If so how can we use this to derive the $n$D Shoelace Formula?

External Links

A good explanation and exploration into why the theorem works by James Tanton: [1]

Nice geometric approach and discussion for proving the 3D Shoelace Theorem by Nicholas Patrick and Nadya Pramita: [2]

Nice integral approach for proving the 3D Shoelace Theorem (ignoring sign of volume) by @george2079: [3] AOPS

Invalid username
Login to AoPS