Polygon Area (Shoelace)

For a simple polygon with vertices $p_0,\dots ,p_{n-1}$ in order:

$2A={\sum }_{i=0}^{n-1}(x_i{y}_{i+1}-x_{i+1}{y}_i)={\sum }_i\mathrm{cross}(p_i,p_{i+1}),$

with indices mod $n$. The signed value is positive for counter-clockwise order.

long long area2(const vector<P>& p) {                 // TWICE the signed area
    int n = p.size();
    long long s = 0;
    for (int i = 0; i < n; i++)
        s += cross(p[i], p[(i + 1) % n]);
    return s;                                         // > 0 means CCW
}
double area(const vector<P>& p) { return fabs((double)area2(p)) / 2.0; }

Keep twice the area

$2A$ is always an integer for integer coordinates. Work with it throughout, halve only when printing, and you never touch floating point.

Why it works

Sum the signed areas of the triangles $(O,p_i,p_{i+1})$ for any origin $O$. Triangles outside the polygon are traversed in the opposite direction and cancel exactly. That is why the formula is origin-independent and works for non-convex polygons.

What the sign gives you

• $2A>0$ → counter-clockwise; $2A<0$ → clockwise; $2A=0$ → degenerate.
• Normalise once at input: if (area2(p) < 0) reverse(p.begin(), p.end());

Many algorithms (point-in-polygon, hull merging, Minkowski sums) silently assume CCW.

Requirements

The polygon must be simple — no self-intersections. For a self-intersecting polygon the formula returns a signed sum with regions counted by winding number, which is occasionally what you want but usually is not.

Related quantities

Quantity	Formula
Perimeter	$\sum |p_{i+1}-p_i|$
Centroid	$\frac{1}{6A}\sum (p_i+p_{i+1})\mathrm{cross}(p_i,p_{i+1})$
Pick’s theorem	$A=I+\frac{B}{2}-1$ for a lattice polygon
Boundary lattice points	$\sum \gcd (|\Delta x_i|,|\Delta y_i|)$
Interior lattice points	$I=A-\frac{B}{2}+1$
Is it convex?	all orientations agree
Bounding box	min/max of the coordinates

The centroid formula is the area-weighted one (the centre of mass of the region), not the average of the vertices. The two differ for non-uniform vertex spacing, and problems usually mean the former.

Triangle area

$2A=|\mathrm{cross}(b-a,c-a)|.$

Also useful: Heron’s formula $A=\sqrt{s(s-a)(s-b)(s-c)}$ with $s$ the semiperimeter — but it is numerically unstable for thin triangles. Prefer the cross product.

Area of a union of shapes

Shapes	Method
Union of rectangles	sweep line + segment tree with counts, $O(n\log n)$
Union of circles	angular sweep on each circle’s boundary, $O(n^2\log n)$
Union of general polygons	polygon clipping (Weiler-Atherton, or a Boost/Clipper library)
Intersection of two convex polygons	$O(n+m)$ by simultaneous traversal, or half-plane intersection
Intersection of a convex polygon and a half-plane	Sutherland-Hodgman clipping, $O(n)$
Circle-polygon intersection area	sum the signed areas of circle-triangle pieces per edge

Sutherland-Hodgman clipping

vector<PD> clip(const vector<PD>& poly, P a, P b) {   // keep the left side of line ab
    vector<PD> res;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        PD cur = poly[i], nxt = poly[(i + 1) % n];
        bool in1 = orient(a, b, cur) >= 0, in2 = orient(a, b, nxt) >= 0;
        if (in1) res.push_back(cur);
        if (in1 != in2) res.push_back(lineInter(a, b, cur, nxt));
    }
    return res;
}

Twenty lines, and clipping a convex polygon by each of another’s edges gives their intersection in $O(nm)$ — enough for most problems.

See also: Pick’s Theorem · Cross Product · Point in Polygon