Difference between revisions of "Shoelace Theorem"

(External Links)
m (Other Forms)
(14 intermediate revisions by 5 users not shown)
Line 2: Line 2:
  
 
==Theorem==
 
==Theorem==
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 of <math>P</math> 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>
  
 
You can also go counterclockwise order, as long as you find the absolute value of the answer.
 
You can also go counterclockwise order, as long as you find the absolute value of the answer.
Line 16: Line 16:
 
(a_1 &, b_1) \\
 
(a_1 &, b_1) \\
 
\end{align*}</cmath>
 
\end{align*}</cmath>
and marks the pairs of coordinates to be multiplied, the resulting image looks like laced-up shoes.
+
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 <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. Note here that <math>x_{n+1} = x_1</math> and <math>y_{n+1} = y_1</math>.
 +
 
 +
The formula may also be considered a 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==
 
==Proof 1==
Line 60: Line 101:
 
\int_{\Omega}\alpha=\int_{\Omega}d\omega.
 
\int_{\Omega}\alpha=\int_{\Omega}d\omega.
 
</cmath>
 
</cmath>
Next, we use the theorem of Stokes to obtain
+
Next, we use the Theorem of Stokes to obtain
 
<cmath>
 
<cmath>
 
\int_{\Omega}d\omega=\int_{\partial\Omega}\omega.
 
\int_{\Omega}d\omega=\int_{\partial\Omega}\omega.
Line 91: Line 132:
 
This is a very nice approach that directly helps in understanding the sum as terms which are areas of trapezoids.
 
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.)
+
See page 271 in this book (in the Polygon Area section.)
 
https://cses.fi/book/book.pdf
 
https://cses.fi/book/book.pdf
  
Line 99: Line 140:
 
=== Introductory ===
 
=== 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>.
 
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==
 
== External Links==
 
A good explanation and exploration into why the theorem works by James Tanton:
 
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]
 
[http://www.jamestanton.com/wp-content/uploads/2012/03/Cool-Math-Essay_June-2014_SHOELACE-FORMULA.pdf]
64rygjn
+
 
 +
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]
 +
 
  
  

Revision as of 12:43, 5 July 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. Note here that $x_{n+1} = x_1$ and $y_{n+1} = y_1$.

The formula may also be considered a 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 271 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