P6.1.2The shoelace algorithm
The shoelace algorithm for calculating the area of a simple polygon (that is, one without holes or self-intersections) proceeds as follows: Write down the \((x,y)\) coordinates of the \(N\) vertices in an \(N \times 2\) array and then repeat the coordinates of the first vertex as the last row to make an \((N+1) \times 2\) array. Now (a) multiply each \(x\)-coordinate value in the first \(N\) rows by the \(y\)-coordinate value in the next row down and take the sum, \(S_1 = x_1y_2 + x_2y_3 + \cdots + x_Ny_1\). Then (b) multiply each \(y\)-coordinate value in the first \(N\) rows by the \(x\) coordinate in the next row down and take the sum, \(S_2 = y_1x_2 + y_2x_3 + \cdots + y_Nx_1\). The area of the polygon is then \(\frac{1}{2}|S_1-S_2|\).
Implement this algorithm as a function that takes a NumPy array of vertices as its argument and returns the area of the polygon. Do not use Python loops!
Show solution
This is a straightforward exercise in NumPy array slicing.
import numpy as np
def polygon_area(vertices):
"""
Return the area of the polygon enclosed by vertices using the shoelace
algorithm.
"""
a = np.vstack((vertices, vertices[0]))
S1 = sum(a[:-1, 0] * a[1:, 1])
S2 = sum(a[:-1, 1] * a[1:, 0])
return abs(S1 - S2) / 2
vertices = [(3, 4), (5, 11), (12, 8), (9, 5), (5, 6)]
print(polygon_area(vertices))
For the example polygon the area is reported as 30.0.