The Shoelace Formula and the Winding Number

3. The shoelace formula and the winding number This is the last of our three lectures on areas of polygons. We introduce a formula for the area of a polygon, in terms of the coordinates of its vertices. Then, we subject this formula to destructive testing: • we look at increasingly complicated examples, and finally try cases that are outside the domain of applicability of the formula, because they aren’t polygons (they have self-intersections); • that will lead to the notion of winding number: our first topological invariant. (3a) Some coordinate geometry. The length of a vector v = (x, y) ∈ R2 is p (3.1) ∥v∥ = x2 + y 2 . Given v1 = (x1 , y1 ) and v2 = (x2 , y2 ), their scalar product and cross product are the numbers (3.2) v1 · v2 = x1 x2 + y1 y2 , (3.3) v1 × v2 = x1 y2 − y1 x2 = det  x1 y1  x2 . y2 You may be familiar with the cross product in three-dimensional space (where the outcome is again a vector). The two-dimensional version (which produces a number) is not common notation, but we find it convenient here. Both products are linear in each entry (satisfy the distributive law): (3.4) (v1 + v2 ) · v3 = v1 · v3 + v2 · v3 , v1 · (v2 + v3 ) = v1 · v2 + v1 · v3 , (3.5) (v1 + v2 ) × v3 = v1 × v3 + v2 × v3 , v1 × (v2 + v3 ) = v1 × v2 + v1 × v3 . They are also (anti)symmetric: (3.6) v1 · v2 = v2 · v1 , (3.7) v1 × v2 = −(v2 × v1 ). Geometrically, if ∢(v1 , v2 ) is the angle formed by the vectors, (3.8) v1 · v2 = ∥v1 ∥ ∥v2 ∥ cos(∢(v1 , v2 )), (3.9) v1 × v2 = ∥v1 ∥ ∥v2 ∥ sin(∢(v1 , v2 )). If one of the vectors is zero, both products are zero, so we don’t have to think about what we mean by angle. For two nonzero vectors, the sign of ∢(v1 , v2 ) is important for the second formula: turning from v1 to v2 in anticlockwise direction is measured by a positive angle, while turning clockwise is measured by a negative angle. Two vectors are linearly dependent exactly when v1 × v2 is zero. A basis (v1 , v2 ), consisting of two linearly independent vectors, is called positively oriented if v1 × v2 > 0 (meaning that one goes from v1 to v2 by an anticlockwise turn with angle between 0 and π), and negatively oriented if v1 × v2 < 0. v2 v1 (3.10) v2 v1 (v1 , v2 ) positively oriented (v1 , v2 ) negatively oriented (3b) The shoelace formula. Take a polygon P with n vertices, having coordinates (3.11) v0 = (x0 , y0 ), v1 = (x1 , y1 ), . . . , vn−1 = (xn−1 , yn−1 ), vn = (xn , yn ) = (x0 , y0 ) = v0 . We repeat one vertex (index 0 and index n are the same), since that is convenient for writing down formulae. The shoelace formula is (3.12) area(P ) = 1 2 v0 × v1 + v1 × v2 + · · · + vn−1 × vn . This formula is easiest to understand if P is convex and the origin o = (0, 0) lies in its interior. If we assume that the ordering of the vertices is anticlockwise, then each 12 (vk−1 × vk ) is positive, and equals the area of the triangle with vertices (o, vk−1 , vk ). Adding up those numbers yields the area of P . If the ordering of the vertices is clockwise, the same holds with the opposite signs (in the end, taking the absolute value will cancel out that overall sign change). Example 3.1. The following polygon has area 14 (three triangles of area 3, and two of area 5/2): (−1, 2) (2, 2) (3, 0) (3.13)  area  = 12 (−1, 2) × (−2, −1) = 5/2 (−2, −1) (1, −2) We’ll now start analyzing what the formula does in more general situations. First of all, it’s not necessary that the origin should lie in the interior of P , because the entire expression is unchanged under translation by any vector w: (v0 + w) × (v1 + w) + (v1 + w) × (v2 + w) + · · · + (vn−1 + w) × (vn + w) (3.14) = (v0 × v1 + v0 × w + w × v1 ) + (v1 × v2 + v1 × w + w × v2 ) + · · · = (v0 × v1 + v1 × v2 + · · · + vn−1 × vn ) + (v0 + · · · + vn−1 ) × w + w × (v1 + · · · + vn ) = v0 × v1 + v1 × v2 + · · · + vn−1 × vn . It is also not necessary that P should be convex: the shoelace formula still applies, because the terms partially cancel. Example 3.2. In the following case, one can see how two of the triangles have pieces lying outside P , but those contribute with opposite signs, which provides the required partial cancellation. There is a part of P (shaded more darkly) that lies in 3 triangles, but again, cancellation means that it is effectively only counted once. (2, 1) (2, 2) 1 2 (3, 0) × (2, 2) = 3 1 2 (2, 2) × (2, 1) = −1 1 2 (2, 1) × (−2, 1) = 2 (−2, 1) (3.15) (3, 0) (1, −2) Next, let’s look at situations which are not polygons, just polygonal loops. By that, we mean that we are given points (3.11) where the coordinates are arbitrary: points can repeat, the edges may intersect or overlap, and so on. To make that clear, we change the notation, and write p for polygonal loops (as opposed to P for polygons). A polygonal loop doesn’t really have an “inside”, so while we can plug the coordinates into the shoelace formula, it’s not obvious what the output means! Example 3.3. Working through the example below triangle-by-triangle, we see that the shoelace formula (omitting the absolute value, for simplicity) yields: the area of the light gray shaded region, plus twice the area of the dark gray shaded region, minus the area of the black region. This is easiest to see for the black region, which is part of only one of the triangles, yielding a negative contribution. (3.16) (−5, 2) (−5, 1) 1 2 (−5, 1) × (−5, 2) = −5/2 The outcome we’ve been looking for is this (without the absolute value, which is more of a hindrance than a help): Theorem 3.4. Take a polygonal loop p, with vertices (v0 , v1 , . . . , vn = v0 ). Then
X 1 (3.17) area(R) wind(p, some point in R). 2 v0 × v1 + v1 × v2 + · · · + vn−1 × vn = R Here, the sum is over all regions R into which p divides the plane, and wind(p, ·) are the winding numbers of p. (Formally, we include the outermost “unbounded region” R, but that won’t matter since its winding number is zero.) (3c) Winding numbers. The formula (3.17) involves a new notion, that of winding number (3.18) wind(p, q) ∈ Z, for p a polygonal loop, and q a point not lying on p. The name describes the intuition correctly: we stand at the point q, and turn our heads to watch a train moving once around p. The winding number is how many full turns we have done at the end, with counterclockwise turns counting as +1 and clockwise ones as −1. Example 3.3 had winding numbers 1 (light gray shaded part), 2 (dark gray), and −1 (black). Example 3.5. The star 1 1 (3.19) 1 2 1 1 0 has winding number 2 on the innermost pentagon region, winding number 1 on the triangle regions, and of course 0 for the unbounded region. Example 3.6. The winding numbers of the following loop take values from −2 to 2. Note the existence of a bounded region with winding number 0: 0 (3.20) -1 -2 2 0 1 Let’s return to the initial situation of a polygon P . There, the absolute value of (3.17) computes the area of (the inside of) the polygon. That happens because ( ±1 if q lies inside P , (3.21) wind(P, q) = 0 if q lies outside P . Let’s take a step back. Since the beginning of this course, we have used the fact that a polygon divides the plane into two regions, the inside and outside. The formula (3.21) gives us a way to check which of those two regions a point belongs to. Turning this on its head, we can use that idea to give a rigorous proof of the fact that the inside and outside are distinct regions. A similar observation concerns the sign in (3.21). When we think of a polygon as given by a list of numbered vertices, we choose one way of going around it (clockwise or anticlockwise). Clockwise yields a sign of −1, and anticlockwise yields +1. Again, one can use this as a mathematical definition of “clockwise” and “anticlockwise”.