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.
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.
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:
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.
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.
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:
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.
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.
Close the walk: the corner after
p[i]isp[(i + 1) % n], which isp[0]for the last corner.Add signed triangles:
s += cross(p[i], p[j])for every side.Read the direction:
s > 0means counterclockwise,s < 0clockwise.Drop the sign:
s = llabs(s).Halve at the end: print
s / 2, followed by.5ifsis odd and.0otherwise.
For Pick's theorem, two more steps:
Count boundary points:
b += gcd(|dx|, |dy|)for every side.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.
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
llabsfirst.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
gcdnon-negative numbers:__gcdwith a negative argument can return a negative number, whilestd::gcddoesn'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
Very easy · Geometry
Very easy · Geometry
Very easy · Geometry
Very easy · Geometry
Very easy · Geometry
Easy · Geometry
Very easy · Geometry