Polygon area

The shoelace formula finds the exact area of a polygon from its corners, listed in order around it, by adding one cross product per side. If the corners come as an unordered set of points, build the convex hull first.

Explanation

A plot of land has four corners on a grid: 1 (0, 0), 2 (4, 1), 3 (3, 4) and 4 (0, 3). The line from corner 1 to corner 3 cuts it into two triangles.

Grid: quadrilateral 1 (0, 0), 2 (4, 1), 3 (3, 4), 4 (0, 3) outlined, cut by a grey diagonal from corner 1 to corner 3 into triangle 1-2-3, shaded blue with area 6.5, and triangle 1-3-4 with area 4.5; a dashed blue parallelogram on sides 1-2 and 1-3 reaches the point (7, 5).

Fig. 1. The cross product of the steps from corner 1 to corners 2 and 3 is the area of the dashed parallelogram. The blue triangle is half of it.

In triangle 1-2-3, the step from corner 1 to corner 2 is (4, 1) and the step to corner 3 is (3, 4). Their cross product, 4 · 4 − 1 · 3 = 13, is the area of the parallelogram on these two steps, dashed in Fig. 1, so the triangle is half of it, 6.5. Triangle 1-3-4 has the steps (3, 4) and (0, 3), with cross product 3 · 3 − 4 · 0 = 9, so its area is 4.5. The plot has area 6.5 + 4.5 = 11.

A second plot has six corners: 1 (1, 1), 2 (9, 1), 3 (11, 4), 4 (9, 7), 5 (1, 7) and 6 (4, 4), listed counterclockwise. Corner 6 is pushed into the left side, making a dent.

A six-cornered plot with corners 1 to 6, corner 6 pushed in to make a dent, cut by lines from corner 1 into four triangles with areas 12, 18, 24 and 9; blue arrows walk 1 to 4 to 5, turning left, and red arrows walk 1 to 5 to 6, turning right, around the red triangle 1-5-6, which is the dent outside the plot.

Fig. 2. Cut from corner 1, the plot gives four triangles. The red one is the dent, outside the plot, and its walk turns right.

Cut it the same way, from corner 1: triangles 1-2-3, 1-3-4, 1-4-5 and 1-5-6. Now the line from corner 1 to corner 5 runs outside the plot, past the dent.

The cross products are 24, 36, 48 and −18. For triangle 1-5-6, the step from corner 1 to corner 5 is (0, 6), the step to corner 6 is (3, 3), and 0 · 3 − 6 · 3 = −18. An area can't be negative, so take each one as a positive number and halve it: 12 + 18 + 24 + 9 = 63. That can't be right, because the whole plot fits in the 10 by 6 rectangle from (1, 1) to (11, 7), which has area 60, and 63 is more than that.

The first three triangles together make the five-cornered piece 1-2-3-4-5. It covers the plot and the dent, and triangle 1-5-6 is exactly the dent. The dent has to be taken away, but adding it as a positive area counts it a second time. So the question is which triangles must be subtracted, and how to tell them without looking at the picture.

Look at the walk around each triangle. A cross product is positive when the second step turns left from the first, and negative when it turns right. Walking around triangles 1-2-3, 1-3-4 and 1-4-5 in the order of their corner numbers, you turn left, the same way as on the walk around the plot. Walking around triangle 1-5-6, you turn right, so its cross product is negative. The sign already marks the triangle to subtract, so keep it: 24 + 36 + 48 − 18 = 90, and half of that is 45.

A triangle counted with the sign of its cross product is a signed triangle. The signed triangles don't have to start at a corner: they can start at any point, with one triangle to every side of the plot. The cut from corner 1 is one such choice: the two sides at corner 1 give flat triangles with area 0. The simplest point is (0, 0). The steps from (0, 0) to two corners are just the corners' coordinates, so the side from corner 2 (9, 1) to corner 3 (11, 4) gives 9 · 4 − 1 · 11 = 25, with nothing to subtract first. The six sides give −8, 25, 41, 56, −24 and 0, and the sum is 90 again.

Parts of these triangles lie outside the plot, but there plus and minus triangles overlap and cancel. Fig. 3 follows one point outside the plot and one inside, and the correctness proof below shows why this always works.

This sum, one cross product of neighbouring corners for each side, is the shoelace formula. For a simple polygon, one whose sides meet only at neighbouring corners, with corners (x_1, y_1), \ldots, (x_n, y_n) in walking order, it gives twice the polygon's signed area, the area with a minus sign when the corners go clockwise:

x_1 y_2 - x_2 y_1 + x_2 y_3 - x_3 y_2 + \ldots + x_n y_1 - x_1 y_n,

The last term, for the side from corner back to corner 1, closes the walk. On the plot it is x_6 y_1 - x_1 y_6 = 4 \cdot 1 - 1 \cdot 4 = 0.

If the corners are listed clockwise, every triangle is walked the other way, every sign flips, and twice the signed area is −90. So the sign reads the direction: positive means counterclockwise, negative means clockwise. The area is the absolute value of this number, divided by 2. Every term is a product of whole numbers, so twice the signed area is whole too, and the area ends in .0 or .5: keep the whole number and halve at the end.

A six-cornered plot on a grid with the origin O at the bottom left; one by one, the triangle from O to each side is drawn, blue when its cross product is positive and red when negative, while the counts next to a point a outside the plot and a point b inside it end at 0 and 1; at the end the plot is filled green.

The plot with point a outside it and point b inside it. The number next to each point counts the signed triangles that cover it: +1 for a blue one, −1 for a red one. Both start at 0.

1/8

Fig. 3. Step through with the buttons or the arrow keys. Blue triangles add their cross product, red ones subtract it.

Lattice points: Pick's theorem

A lattice point is a point with integer coordinates. Some problems ask how many lattice points lie inside a polygon whose corners are lattice points. With coordinates up to 10^6, checking every point of the surrounding square would take about 4 \cdot 10^{12} checks. The area and the number of points on the boundary give the answer with one gcd per side.

The side from corner 5 (1, 7) to corner 6 (4, 4) goes 3 right and 3 down. The greatest common divisor of 3 and 3 is 3, so the side splits into 3 equal steps of 1 right and 1 down, and it passes through 4 lattice points: (1, 7), (2, 6), (3, 5) and (4, 4). In general a side passes through gcd(|dx|, |dy|) + 1 lattice points, counting both ends. Each corner is the end of two sides, so around the polygon count only the gcd for each side. For the six-cornered plot, the sides give 8, 1, 1, 8, 3 and 3: 24 points on the boundary.

Pick's theorem, which we use without proof, links the area of a polygon whose corners are all lattice points to the number of lattice points inside it and the number on its boundary:

A = I + \frac{B}{2} - 1.

On the four-cornered plot of Fig. 1 you can count 6 points on the boundary and 9 inside, and 9 + 3 − 1 = 11, the area found before.

With , twice the area, the theorem gives the inside points as I = (S - B + 2) / 2. For the six-cornered plot that is (90 − 24 + 2) / 2 = 34.

The six-cornered plot with a dent at corner 6 on a square grid: its 24 boundary lattice points are hollow circles and its 34 inside lattice points are small dots; side 5-6 is blue with its 4 points, and each side carries its gcd: 8, 1, 1, 8, 3, 3 for sides 1-2 to 6-1.

Fig. 4. The plot has 24 lattice points on its boundary and 34 inside.

Implementation

The corners are stored in a vector p of n points, in walking order. Point and cross are the ones from geometry basics. A point is also the vector from (0, 0) to it, so the signed triangle of the side from p[i] to the next corner p[j] is cross(p[i], p[j]), and s adds them up to twice the signed area.

  1. Close the walk: the corner after p[i] is p[(i + 1) % n], which is p[0] for the last corner.

  2. Add signed triangles: s += cross(p[i], p[j]) for every side.

  3. Read the direction: s > 0 means counterclockwise, s < 0 clockwise.

  4. Drop the sign: s = llabs(s).

  5. Halve at the end: print s / 2, followed by .5 if s is odd and .0 otherwise.

For Pick's theorem, two more steps:

  1. Count boundary points: b += gcd(|dx|, |dy|) for every side.

  2. Solve for inside points: in = (s - b + 2) / 2.

The input has n, then n lines x y: the corners in walking order, either direction, with 3 \le n \le 10^5 and |x|, |y| \le 10^6. The program prints the direction, then the area with one digit after the point, then the numbers of boundary and inside points. For the plot the input is:

6
1 1
9 1
11 4
9 7
1 7
4 4
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct Point { long long x, y; };

long long cross(Point u, Point v) { return u.x * v.y - u.y * v.x; }

int main() {
    int n;
    cin >> n;
    vector<Point> p(n);
    for (Point& q : p) cin >> q.x >> q.y;

    long long s = 0;
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;          // close the walk
        s += cross(p[i], p[j]);       // add signed triangles
    }

    // read the direction; remove this line if you don't need the direction
    cout << (s > 0 ? "counterclockwise" : "clockwise") << '\n';

    s = llabs(s);                     // drop the sign

    // halve at the end
    cout << s / 2 << (s % 2 ? ".5" : ".0") << '\n';

    // remove this block if you only need the area
    long long b = 0;
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        // count boundary points
        b += gcd(llabs(p[j].x - p[i].x), llabs(p[j].y - p[i].y));
    }
    long long in = (s - b + 2) / 2;   // solve for inside points
    cout << b << ' ' << in << '\n';
}

The program takes time, one cross product per side, and memory for the corners.

Correctness proof

Take the signed triangles from (0, 0) to every side, for a polygon walked counterclockwise. Pick any point that is not on a side or on a line through (0, 0) and a corner, and draw the ray from (0, 0) through . The triangle of a side contains exactly when that side crosses the ray beyond . The triangle counts plus when the side crosses the ray going counterclockwise around (0, 0), and minus when it crosses clockwise.

On a counterclockwise walk the polygon lies to the left of every side. So where a side crosses the ray counterclockwise, the polygon is on the side towards (0, 0), and the ray, going outwards, leaves the polygon; where a side crosses clockwise, the ray enters it. The ray goes off to infinity and ends outside. If is outside, the ray beyond it enters as many times as it leaves, and is counted 0 times. If is inside, it leaves once more than it enters, and is counted once. So the sum is the area. For a clockwise walk every sign flips, and the sum is minus the area.

A six-cornered plot with a dent on the left, its sides marked with arrows for a counterclockwise walk; two grey rays start at the origin, one through a red point in the dent that crosses the top side with a plus and the dented side with a minus, and one through a blue point inside that crosses the upper right side with a plus.

Fig. 5. A point outside is crossed once counterclockwise and once clockwise. A point inside is crossed once more counterclockwise.

The argument needs a simple polygon, one whose sides meet only at neighbouring corners, with the corners in walking order. If the walk crosses itself, the sum is the area of one loop minus the other.

Common mistakes

  • Forgetting the absolute value. The rectangle (0, 0), (0, 3), (4, 3), (4, 0) is listed clockwise, so twice its signed area is −24 and the "area" −12, and Pick's theorem then gives −18 inside points instead of 6. Apply llabs first.

  • Halving each triangle in whole numbers. For the four-cornered plot, 13 / 2 + 9 / 2 gives 6 + 4 = 10 instead of 11. Halve once, at the end.

  • Counting gcd + 1 points on each side. Every corner is then counted twice, and the triangle (0, 0), (6, 0), (0, 4) gets B = 15 instead of 12. Also pass gcd non-negative numbers: __gcd with a negative argument can return a negative number, while std::gcd doesn't.

  • Using Pick's theorem on a flat polygon. The corners (0, 0), (2, 0), (4, 0) lie on one line, so twice the area is 0, B = 8, and the formula gives −3 inside points. If twice the area is 0, the answer is 0.

  • Listing the corners out of walking order. With the square's corners in the order (0, 0), (2, 2), (2, 0), (0, 2), the walk crosses itself, and twice the signed area comes out 0 instead of 8.

Similar algorithms

  • Segment intersection also works with cross-product signs. It checks that no two sides of a polygon cross, which the shoelace formula assumes.

  • Point in polygon decides whether one given point is inside, by counting the sides that a ray from it crosses, as in the correctness proof.

  • Convex hull builds the smallest convex polygon around a set of points. When the corners come as a cloud of points rather than in order, build the hull first; its area is then this formula.

Practice

Was this page helpful?