The shoelace formula adds xᵢyᵢ₊₁ − xᵢ₊₁yᵢ over the edges of a closed polygon. The total is twice the signed area: the magnitude is what you wanted and the sign says which way round the vertices were typed. Keeping it doubled keeps it an integer on lattice input, so the page prints 2A and halves it only at the end. A second formula that multiplies entirely different pairs of coordinates runs beside it, and a degenerate polygon of zero area is an answer rather than an error.
Core ideas
The sum, what the sign is for, and why the value is kept doubled all the way to the last line.
The term xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ is orient(O, vᵢ, vᵢ₊₁) with O the origin: twice the signed area of the triangle from the origin to that edge. Summing over the edges adds up triangles that overlap and cancel, and what survives is twice the area of the polygon. So the shoelace formula is not a new idea; it is the same determinant as everything else on this course, summed.
A positive total means the vertices were listed counter-clockwise, a negative one clockwise. That is not an error to take an absolute value of: half the algorithms in computational geometry require a known orientation, and the cheapest way to get one is to compute the signed area and reverse the list if it came out negative. The lab's clockwise worked example has 2A = −50 and the page reports the orientation rather than hiding it.
The area of a lattice polygon can be a half-integer — a triangle of area 1/2 is the smallest nonzero one there is. Twice the area is always an integer, so the sum is exact in every intermediate step. The halving happens once, at the end, and the result is printed as an exact fraction with a decimal beside it rather than instead of it.
The material
Where the formula comes from, what its sign means, and the independent route the page runs beside it.
For a closed polygon with vertices v₁, …, vₙ in order, the doubled signed area is 2A = Σᵢ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ), with the index wrapping so that vₙ₊₁ is v₁. Its absolute value is twice the area enclosed; it is positive when the vertices are in counter-clockwise order, negative when clockwise, and zero when the polygon encloses no area.
For a simple polygon with vertices listed in order, Σᵢ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ) is twice the enclosed area, signed by the orientation of the listing.
Take the polygon to be counter-clockwise; the clockwise case follows by reversing the list, which negates every term. Triangulate it by fanning from v₁, which is possible for any simple polygon. The signed area of the triangle v₁ vᵢ vᵢ₊₁ is orient(v₁, vᵢ, vᵢ₊₁) / 2, and summing those over i from 2 to n − 1 gives the area, because the fan covers the polygon and the signed areas of any parts that fall outside cancel against parts counted twice.
Now orient(v₁, vᵢ, vᵢ₊₁) expands to (xᵢ − x₁)(yᵢ₊₁ − y₁) − (yᵢ − y₁)(xᵢ₊₁ − x₁), which is (xᵢ yᵢ₊₁ − xᵢ₊₁ yᵢ) plus terms in x₁ and y₁. Summing over the fan, the x₁ and y₁ terms telescope to zero, and the edges v₁v₂ and vₙv₁ contribute nothing of their own since they lie in the fan's apex. What remains is Σᵢ (xᵢ yᵢ₊₁ − xᵢ₊₁ yᵢ), doubled area.
□
The triangulation step is where simplicity is used. A self-intersecting polygon still has a shoelace sum, and it is still well defined; what it means is a signed count of how many times each region is enclosed, which is the winding number by another name. The page checks whether the polygon is simple before making claims that require it.
Type (0, 0), (5, 0), (5, 5), (0, 5) and the lab reports 2A = 50, area 25, counter-clockwise. Type (0, 0), (0, 5), (5, 5), (5, 0) — the same four corners in the opposite order — and it reports 2A = −50, area 25, clockwise. Nothing about the SHAPE changed; the sign is reporting the listing.
This is the lab's fourth worked example and it is there to make the sign concrete. A reader who has been taking absolute values without thinking will see a negative number, assume something has gone wrong, and be exactly wrong: the negative number is the answer to a question the absolute value throws away.
The trapezoid rule computes Σᵢ (xᵢ − xᵢ₊₁)(yᵢ + yᵢ₊₁), which is algebraically the same total. Arithmetically it is not: it multiplies differences of x by sums of y, where the shoelace multiplies coordinates directly. A transposed subscript in either gives a plausible number, and the only thing that catches it is a route that would have to be wrong in exactly the same way. The lab prints both and marks a disagreement in red.
The arithmetic checker behind this kit adds a third route, fanning triangles from the first vertex and summing orientation determinants, and requires all three to agree on every preset and on hundreds of random convex polygons. Three routes to one integer is more than is strictly needed and it is the reason a page can print an area without hedging.
Three collinear vertices give 2A = 0, and the lab's degenerate worked example is exactly that: (0, 0), (3, 3), (6, 6). The area is zero, there is no orientation to report, and there is no interior for a point to be inside. The page says all three of those things rather than dividing by zero or refusing the input. A degenerate case that still answers is what distinguishes a complete implementation from one that has never been given anything unusual.
It is worth noticing what does NOT break. The sum is still computed, still exactly, and still agrees between the two formulas. The orientation is the only field that has no value, and it says so in words instead of picking one. The next lesson's inside test also still answers on this polygon, and puts every point of the segment on the boundary.
Interactive
Two exact formulas for the area, and two definitions of inside
Method
Sum first, halve last, and keep the sign until you have used it.
The formula needs a cyclic order, and the final edge from the last vertex back to the first is a term like any other. Forgetting it is the single most common error and it produces a number that is wrong by one triangle — plausible, and not detectably so without a second route.
Each term is xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ, and on lattice input every one of them is an integer. Do not halve as you go: the running total can be odd, and halving an odd integer is where a decimal first enters a computation that did not need one.
Positive is counter-clockwise, negative is clockwise. If a later algorithm needs a known orientation — and most of them do — this is where you learn it, for free. Then take the magnitude for the area.
2A divided by 2 is exact as a rational number and generally not an integer. The page prints the fraction and puts a decimal beside it as a reading aid; the fraction is the value and the decimal is a convenience.
The vertices are (0, 0), (0, 5), (5, 5), (5, 0), in that order, which goes round clockwise.
Two of the four terms are zero, which is what happens when an edge passes through the origin's row or column: the term is the doubled area of a triangle with the origin, and that triangle is flat. The whole area comes from the two edges that do not touch the axes, and each contributes −25.
Move the entire square by adding (7, 3) to every vertex and recompute. Every individual term changes — none of them is zero any more — and the total is still −50. The determinant depends only on differences, and the shoelace sum inherits that: the fan from the origin is a computational device, not a geometric one.
For a faded rehearsal, compute 2A for the L-shaped polygon (0, 0), (6, 0), (6, 2), (2, 2), (2, 6), (0, 6) by hand. The supplied first move is that six vertices means six terms and the last one runs from (0, 6) back to (0, 0). Then check your answer against the area you get by cutting the L into two rectangles, and say why the shoelace sum handles the reflex corner without any special case.
You should be able to derive the formula from the fan of orientation determinants, explain what simplicity is used for in that derivation, predict what reversing or translating the vertex list does to the total, and say what a second formula over different products buys.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.