Mainly Tech projects on Python and Electronic Design Automation.

Sunday, July 16, 2017

Python investigation of the Shoelace Formula for polygonal area

Shoelace formula for polygonal area

Sawtooth generator

In [33]:
def sawtooth_wave(teeth, base=2, height=3):
    xy = [(0, 0)] # start
    for n in range(teeth):
        xy += [(base * (n + 1), height), (base * (n + 1), 0)]
    xy.append((0, 0))  # return to start
    return zip(*xy)   # x then y
In [34]:
from pprint import pprint as pp
from bokeh.plotting import figure, output_notebook, show
from bokeh.models import ColumnDataSource
from bokeh.charts import Scatter
output_notebook()
 BokehJS 0.12.5 successfully loaded.
In [35]:
teeth = 3
sawx, sawy = sawtooth_wave(teeth)
sawx, sawy = zip(*saw)
pl = figure(plot_width=400, plot_height=400, title=f'Sawtooth polygon with {teeth} right-angled triangle teeth')
#help(pl.line)
pl.line(sawx, sawy, line_width = 1, line_color="navy")
show(pl)

Calculate area by shoelace formula

In [36]:
def area_by_shoelace(x, y):
    "Assumes x,y points go around the polygon in one direction"
    return abs( sum(i * j for i, j in zip(x, y[1:])) + x[-1] * y[0]
               -sum(i * j for i, j in zip(x[1:], y)) - x[0] * y[-1]) / 2 
In [37]:
print(" Area is:", area_by_shoelace(sawx, sawy))
 Area is: 9.0
We know that the area of a right angled tringle is half base times height.
So each tooth of the saw has area 1/2 * 2 * 3 = 3 units and we have three teeth for a total area of 9.

Why Shoelace?

It's called the shoelace formula because of a visualization of the calculation.

Get the coordinates, in order.

list the x,y coordinates of each point of the polygon, going around the polygon in one direction, and going back to the starting point. (For more complex polygons, no line segments should cross).
Split the ordered points into two identically ordered lists of the x coordinates and the y coordinates.
Visualize the x coords as numbers beside one side of a row of eyelets of a shoe, and the y coords adjacent to the eyelets on the other side.

First "lacing":


lacing1 = sum(x[0]*y[1] + ... x[n]*y[n+1]) + x[N]*y[0]

Second "lacing"

lacing2 = sum(x[1]*y[0] + ... x[n+1]*y[n) + x[0]*y[N]

Complete formula

area = abs(lacing1 - lacing2) / 2
All tied up!

4 comments:

  1. Is there a proof of some kind?

    ReplyDelete
    Replies
    1. Yep: http://artofproblemsolving.com/wiki/index.php?title=Shoelace_Theorem

      Delete
  2. A bit shorter: abs( sum( (a * c - b * d) for a, b, c, d in zip(x, x[1:], y[1:],y)) + x[-1] * y[0] - x[0]* y[-1]) / 2

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive