The Shoelace Formula

Finding the center of a shape that doesn't want to be centered.

Slight disclaimer before reading: I don't have a math background. I pick up whatever I need when a project corners me into it.

I was building an index of real estate prices in Montenegro and needed to place a label at the visual center of each municipality.

Sounds simple to us humans, we can just eyeball it, but how do you tell the computer to find the center programmatically, without hardcoding it as a screen position. Especially as municipalities can have shapes which are very much so, irregular.

Let's take Budva as an example, its shape is a concave polygon, reflecting its coastal and mountainous borders.

The naive approaches either land the label outside the polygon entirely or somewhere misleading.

What does "center" even mean for an irregular, concave polygon? And how do you compute it?

BTW, I know: Turf.js, D3, or any GIS library can do this in one line. This was me wanting to understand what's actually happening under the hood.

For a rectangle, the center is obvious. Average the corners. For a triangle, same thing.

This is the vertex average: the arithmetic mean of all vertex coordinates.

cx = (x₀ + x₁ + x₂ + ... + xₙ) / n
cy = (y₀ + y₁ + y₂ + ... + yₙ) / n

This works. But it only works because these shapes are simple and, most importantly, convex. Convex being the opposite of concave, the opposite of "dented", you could say simply.

A convex polygon is one where every interior angle is less than 180 degrees. No dents. For any convex polygon (pentagon, hexagon, whatever), the vertex average lands inside the shape and looks reasonable.

So when does this break?

Let's say a polygon is convex but elongated, with lots of vertices clustered along a thin section that covers very little area.

All those vertices pile into the average and drag it toward the thin section, way off from where we'd eyeball the center. Not all vertices should be weighted equally. Let's fix that.

Instead of treating all vertices equally, decompose the polygon into triangles and weight each triangle's center by its area. This is fan triangulation. Pick one vertex, draw lines to all the others. You get a fan of triangles.

The formula is a weighted average of triangle centroids:

centroid = Σ(areaᵢ × centroidᵢ) / Σ(areaᵢ)

This accounts for how much space each part of the polygon actually occupies. For convex polygons with simple shapes, it gives almost the same answer as the vertex average.

For convex polygons with elongated sections, it pulls the center to where most of the "mass" is, better than vertex average.

But, the real test are concave shapes.

A concave polygon has at least one interior angle greater than 180 degrees. A dent. Fan triangulation treats every triangle's area as positive. So when a triangle covers space outside the polygon (which happens at the dent), that exterior area gets added to the total instead of subtracted. The centroid shifts toward area that isn't part of the shape.

We need an algorithm that is aware of the polygon's actual area distribution, the parts that are "missing" in concave shapes included.

It starts with the 2D cross product.
Two vectors u = (a, b) and v = (c, d) span a parallelogram with area |ad - bc|.
A triangle is half that parallelogram: ½|ad - bc|.

Two multiplications, one subtraction. No trig, no height measurements.

The Shoelace formula (Meister, 1769) applies this triangle trick to every edge of the polygon. Each edge, together with the origin, forms a triangular wedge. Walk the boundary edge by edge: wedges swept counter-clockwise contribute positive area, clockwise wedges contribute negative. The exterior wedges cancel out and you are left with only the polygon's true interior. Sometimes called the surveyor's walk.

The origin does not even need to be inside the polygon. The positive and negative wedges always cancel to the correct result regardless of where it sits. For concave polygons, some wedges subtract the "missing" regions.

The name comes from the multiplication pattern. Each term multiplies diagonally: xᵢ with yᵢ₊₁ going forward, xᵢ₊₁ with yᵢ going backward. It looks like lacing a shoe.

Signed area

The formula iterates through consecutive vertex pairs and computes a cross product for each edge:

cross = xᵢ · yᵢ₊₁ − xᵢ₊₁ · yᵢ

Sum all cross products, divide by 2. That gives the signed area. Positive if the vertices are counter-clockwise, negative if clockwise.

let area = 0;
for (let i = 0; i < n; i++) {
  const j = (i + 1) % n; // wraps last vertex back to first
  area += pts[i].x * pts[j].y - pts[j].x * pts[i].y;
}
area /= 2;

The % n (modulo) closes the polygon: when i reaches the last vertex (n - 1), j wraps to 0, pairing the last vertex with the first. Without it, we'd miss the closing edge.

Weighted centroid

Same loop, same cross products, but now each one also accumulates the coordinate sum of the edge's two endpoints. Divide by 6A at the end: 2 from the area formula, 3 because a triangle's centroid sits at one-third the sum of its vertices.

let cx = 0, cy = 0, area = 0;
for (let i = 0; i < n; i++) {
  const j = (i + 1) % n; // wraps last vertex back to first
  const cross = pts[i].x * pts[j].y - pts[j].x * pts[i].y;
  area += cross;
  cx += (pts[i].x + pts[j].x) * cross;
  cy += (pts[i].y + pts[j].y) * cross;
}
area /= 2;
const centroid = { x: cx / (6 * area), y: cy / (6 * area) };

Step through the algorithm on both a convex and concave shape. Cross products can be positive or negative depending on how each edge sweeps relative to the origin. On the convex shape, they all cancel out cleanly into the right area. On the concave shape, the void region gets subtracted out, which is why the Shoelace centroid lands inside the shape while a simple vertex average doesn't.

Back to the opening problem. Run all three methods on Budva's real 66-vertex coastline. Switch between tabs and watch each algorithm work step by step.

The difference is structural. Fan triangulation from a single vertex creates triangles that spill outside the polygon on concave shapes, and if you just sum those up, your centroid includes area that isn't part of the shape.

The Shoelace formula fans from the origin instead. Its cross products carry sign: counter-clockwise wedges add, clockwise wedges subtract. The exterior cancels itself out automatically.

The same formula shows up whenever you need the area or centroid of an arbitrary polygon: computational geometry, physics (center of mass), computer graphics (polygon fill), CAD.