Determinants, Shoelace Formula

Shoelace Formula

Let s be an ordered set of points in the plane that defines a simple closed polygon. A segment joins the first point in s to the second, then another segment joins the second to the third, and so on, just like dot-to-dot. The shape is closed as a segment joins the last point to the first.

Write the x coordinates of the points in one row and the y coordinates in another. Or you can write them as two columns if you prefer. Then multiply each xi by yi+1, and each yi by xi+1. The former terms are added and the latter are subtracted. If you write down the coordinates in columns, and connect the items that are to be multiplied, the picture looks like shoelaces. The laces that slope down and to the right represent positive products and the laces that slope down and to the left represent negative products.

Let's illustrate using 4 points that form a square. Actually it looks like a baseball diamond, but that's still a square. Let's run the bases in order.

    x |  y
    1 |  0
    0 |  1
   -1 |  0
    0 | -1

Unlike most shoes, two extra laces connect the botom entries with the top, thus joining the last point in s with the first. In our example, the positive products add up to 2 and the negative products add up to -2. Subtract these to get 4. Then divide by 2 to get the area of the polygon, which is 2. This agrees with the area of our square, computed by traditional means. And now for the proof.

Add the constant c to all the x coordinates and you add cy2 to the total courtesy of x1y2, and you subtract cy2 from the total courtesy of y2x3. This holds for each yi, hence the total is unchanged. Slide the polygon to any x and y coordinate, and its area does not change; nor does our shoelace formula.

Start with a convex polygon. Shift the polygon so that the origin is inside. Draw two segments from the origin to two adjacent vertices in the polygon. These vectors form a triangle with the edge of the polygon. They also span a parallelogram whose area is twice the triangle. The area of the parallelogram is given by the determinant, which is one of our shoelace cross products. Half the sum of these cross products is the area of the triangles in the polygon, which gives the area of the polygon. The shoelace formula agrees with the area.

We need to watch our signs; determinants can be negative. Assume the points are labeled counter clockwise. For any triangle, apply a rigid rotation so that the base lies on the positive x axis. This does not change the area or determinant of the triangle. Moving counterclockwise, the point on the x axis is listed first, hence that vector is at the top of the 2×2 matrix. The determinant is always positive. This holds for all the triangles, so the formula is correct.

Next assume s is not convex. The polygon is bounded, so let v be the lowest vertex, the vertex with least y coordinate. If there are several such vertices, choose the rightmost. Draw a horizontal line through v and slowly pivot it about v, turning counterclockwise until the line hits another vertex w in s. Assume the segment v→w is not part of s. Thus the segment joining v and w is completely outside of s.

Translate the polygon so that the origin is midway between v and w. Cut the polygon at v and w. This gives two separate paths, one from v to w and one from w to v. Either can be joined with v→w to make a new polygon. Let p be the larger, outside polygon and let q be the smaller, inside polygon. Even with the new segment added, p and q have fewer edges than s. By induction on the number of edges, we can assume the shoelace formula works for p and q. And when this formula is applied, it doesn't matter whether v→w is included or not. The determinant of two antiparallel vectors, from the origin to v and from the origin to w, is 0.

The area of s is the area of p - the area of q. Rewrite this as the area of p + minus the area of q. The area of p is given by the shoelace formula on its vertices running counterclockwise, and minus the area of q is given by the shoelace formula on its vertices running clockwise. Now we see the value of negative volume, i.e. a negative determinant. Add the two shoelace formulas together by placing one shoe above the other. Again, it doesn't matter if v→w is removed from p and w→v is removed from q, since they contribute nothing. What remains are the points of s, in counterclockwise order. This is the shoelace formula for s, and it gives the difference in area between p and q, which happens to be the area of s.

Next assume v→w is already an edge in s. Pivot the line about w until you reach x. If w→x is not an edge in s, invoke the previous paragraph using w→x instead of v→w. If w → x is an edge in s, pivot about x until you run into y. Continue doing this until you encounter an edge that is not in s, whence you can invoke the previous paragraph. If you get all the way back to v then s is convex.

Binary Mathematics, Linear Algebra, Calculus, Statistics, and Discrete Mathematics in a Computer Science Masters Degree:
Types of Math Used in Computer Science | Computer Science Masters Degree | Math Courses Required for a MSCS Degree