⚙️AlgorithmIntermediate

Polygon Area and Centroid

Key Points

  • •
    The signed area of a simple polygon can be computed in O(n) using the shoelace formula, which sums cross products of consecutive vertices.
  • •
    The sign of the area reveals orientation: positive for counterclockwise order and negative for clockwise order (under the standard right-handed coordinate system).
  • •
    The centroid (geometric center) of a uniform-density polygon is a weighted sum of edge midpoints where weights are the same cross products used in the shoelace formula.
  • •
    You can compute centroid coordinates directly in O(n) with formulas that divide by 6 times the signed area.
  • •
    Be careful with integer overflow; use 128-bit integers for 2×area or long double for safety with large coordinates.
  • •
    If the signed area is near zero, the polygon is degenerate (collinear or a point), and the standard centroid formula is not valid.
  • •
    For many geometry algorithms, it is helpful to enforce counterclockwise orientation by reversing vertices when the signed area is negative.
  • •
    These formulas work for simple (non-self-intersecting) polygons; self-intersections produce algebraic areas and a misleading centroid.

Prerequisites

  • →Vectors and the 2D cross product — The shoelace formula and orientation tests use the 2D cross product extensively.
  • →Summations and modular indexing — Area and centroid are computed by summing over edges with wraparound from the last to the first vertex.
  • →Floating-point precision and epsilon comparisons — Robust implementations need to detect near-zero areas and avoid unstable divisions.
  • →Integer overflow and wide integers — Large coordinates require 128-bit intermediates to avoid overflow when summing cross products.
  • →Polygon basics (simple vs self-intersecting) — Formulas assume a simple polygon; self-intersection changes the meaning of the signed area.

Detailed Explanation

Tap terms for definitions

01Overview

Polygon area and centroid are foundational tools in computational geometry. For a simple (non-self-intersecting) polygon whose vertices are listed in order around the boundary, the area can be computed using the shoelace formula: a single pass that sums the cross products of consecutive vertices. The result is a signed area: its magnitude equals the polygon’s area, and its sign indicates whether the vertex order is counterclockwise (positive) or clockwise (negative). This is extremely useful because orientation matters in many algorithms (e.g., computing normals, clipping, or consistent winding rules). The centroid—also known as the geometric center or center of mass for uniform density—is the balance point of the polygon. Instead of triangulating explicitly, you can compute it directly via formulas that reuse the cross products from the shoelace sum, making the implementation short, efficient, and numerically consistent. Both computations run in O(n) time and O(1) extra space, where n is the number of vertices. In competitive programming and practical applications, this method is reliable for convex and concave simple polygons, easy to implement, and fast. Care must be taken with numerical precision and degenerate cases (zero or near-zero area). When coordinates are large integers, using 128-bit intermediates or long double prevents overflow and preserves accuracy.

02Intuition & Analogies

Imagine walking a fence line around a field while holding a wheel that measures how much you turn and how far you go. When you complete the loop, the wheel’s readings can tell you the area you enclosed—this is the spirit behind the shoelace formula. Another way to picture it: for each edge of the polygon, you draw a skinny parallelogram to the origin; the signed area of that parallelogram is the cross product of the edge’s endpoints viewed as vectors. Adding up these signed slices gives the total area, with clockwise edges subtracting and counterclockwise edges adding, hence a signed result. The sign reflects the direction you traversed the vertices: CCW adds positive slices, CW subtracts them. For the centroid, think of the polygon as a sheet of uniform cardboard. If you cut it out, there’s a single point where you could balance it on a pin—that’s the centroid. A practical way to find it is to slice the polygon into triangles that share a fixed point (like the origin or the first vertex). Each triangle’s centroid is just the average of its three corners, and its influence on the total centroid is proportional to its signed area. When you sum all triangle centroids weighted by their signed areas, cancellations occur for the parts that should not contribute (due to orientation), and what remains is the exact centroid of the whole shape. The nice surprise is that this sum simplifies beautifully into a compact edge-based formula that mirrors the shoelace area computation. So you can find both the area and the balance point with one coordinated pass through the vertices.

03Formal Definition

Let a simple polygon P be given by ordered vertices = (, ), = (, ), , = (, ), where indices wrap modulo n so that . Define the 2D cross product of vectors a = (, ) and b = (, ) as a - . The signed double area of P is ( - ) = . Then the signed area is A(P) = . Under the standard orientation (x to the right, y up), A(P) > 0 when the vertices are counterclockwise and A(P) < 0 when clockwise. For the centroid C = (, ) of a uniform-density polygon, the closed-form expressions are = ( + ) ( - ), = ( + ) ( - ). These follow from decomposing P into triangles, summing the triangle centroids weighted by their signed areas, and simplifying. The formulas require a nonzero signed area (i.e., P is not degenerate). When only the magnitude of area is needed, use ; when orientation is important, use the signed area directly.

04When to Use

Use the shoelace formula whenever you need the area of a simple polygon quickly and robustly: computing farmland sizes on a grid, measuring the footprint of a building outline, or verifying the area of a convex hull. In competitive programming, these formulas are standard in problems that ask for polygon area, polygon centroid, determining orientation, or normalizing a polygon’s winding (e.g., ensuring counterclockwise order for clipping, triangulation, or computing Minkowski sums). The centroid formula is ideal when you need the balance point of a uniform-density shape: physics simulations (center of mass), placing labels in GIS mapping, or computing rigid body properties. Because both area and centroid are computed in a single O(n) pass and share the same cross-product terms, you can calculate them together with minimal overhead. Use signed area to detect and fix orientation: if A < 0, reverse the vertex list to make it CCW for downstream algorithms. Avoid applying these formulas directly to self-intersecting polygons (figure-eights) unless you specifically want algebraic area and an algebraic centroid; otherwise, first convert to a non-self-intersecting representation or decompose into simple components.

⚠️Common Mistakes

Common pitfalls include forgetting to close the polygon in code (not handling the last-to-first edge). A safe pattern is to always access the next index as (i + 1) % n. Another frequent mistake is ignoring orientation: using |A| everywhere hides whether the input is clockwise or counterclockwise, which can break later steps that assume CCW order. Developers also often mix integer and floating-point types in ways that cause overflow or precision loss: summing cross products in 32-bit integers will overflow quickly; prefer 64-bit integers with 128-bit intermediates or long double. When computing the centroid, a classic bug is dividing by 2A instead of 6A, or summing (x_i + x_{i+1}) without multiplying by the cross product. Degenerate polygons (nearly collinear points) can cause numerical instability: if |A| is very small, the centroid formulas divide by a tiny number and amplify error; detect this and handle separately (e.g., return the average of vertices or the midpoint of the longest segment). Finally, be careful with repeated vertices (including repeating the first vertex at the end): if your loop already wraps modulo n, an explicit repeated last point will double-count one edge unless you remove it.

Key Formulas

Shoelace (Signed Area)

Explanation: Compute the polygon's signed area by summing cross products of consecutive vertices. Positive means CCW order; negative means CW.

Double Area

Explanation: This is twice the signed area and is an integer if all coordinates are integers. It is useful to avoid floating-point until the final division by 2.

Centroid X

Explanation: The x-coordinate of the centroid is a weighted sum of edge endpoint averages, with weights equal to the same cross products used in the shoelace formula.

Centroid Y

Explanation: Analogous to Cx, this gives the y-coordinate of the centroid using the same weights and division by 6A.

2D Cross Product

Explanation: The scalar cross product gives the signed area of the parallelogram spanned by vectors a and b. It is the core primitive behind the shoelace sum.

Orientation from Area

Explanation: The sign of the signed area encodes orientation: positive is CCW, negative is CW, zero means degenerate.

Triangulation Area

Explanation: Area equals the sum of signed areas of fan triangles from P0. This identity underlies the centroid derivation.

Centroid via Weighted Triangles

Explanation: The polygon centroid is the weighted average of triangle centroids using signed triangle areas as weights. It simplifies to the closed-form edge-based centroid formulas.

Triangle Centroid

Explanation: The centroid of a triangle is the arithmetic mean of its vertices. This is used when deriving the polygon centroid from triangulation.

Unsigned Area

Explanation: When you only need magnitude, take the absolute value of the signed sum. This is the usual geometric area regardless of orientation.

Complexity Analysis

Both the polygon area (shoelace) and centroid computations run in linear time with respect to the number of vertices n. Each requires a single pass over the vertex list, performing O(1) arithmetic per edge: one cross product and a few additions/multiplications. Therefore, the time complexity is O(n). The constants are very small—just a handful of floating-point or integer operations per vertex—so these routines are extremely fast in practice and suitable for tight time limits on competitive programming platforms. Space complexity is O(1) additional memory beyond the input polygon, as the formulas accumulate running sums (for double area, and for centroid numerators). You do not need auxiliary arrays or recursion. This also makes the method cache-friendly and amenable to streaming: vertices can be processed as they are read if you also store the first vertex for the wraparound term. In terms of numerical behavior, accumulating in double or long double is usually stable for moderate n (up to 1e6) and coordinate magnitudes (up to around 1e9 to 1e12). If coordinates are 64-bit integers and can be large, summing 2×area in a 128-bit integer (__int128) avoids overflow exactly; you can convert to long double at the end to divide by 2 and by 6A for the centroid. The centroid calculation shares the same asymptotic cost as the area but includes extra multiplications by coordinate sums; the overall complexity remains O(n) with constant additional work.

Code Examples

Compute signed area and centroid; normalize to CCW if needed
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Point {
5    long double x, y;
6};
7
8// 2D cross product of vectors a and b treated from origin
9static inline long double cross(const Point &a, const Point &b) {
10    return a.x * b.y - a.y * b.x;
11}
12
13// Remove a repeated last vertex equal to the first, if present
14void dedupeClosingVertex(vector<Point> &P) {
15    if (P.size() >= 2u) {
16        if (fabsl(P.front().x - P.back().x) < 1e-18L && fabsl(P.front().y - P.back().y) < 1e-18L) {
17            P.pop_back();
18        }
19    }
20}
21
22// Signed area via shoelace; positive for CCW, negative for CW
23long double polygonSignedArea(const vector<Point> &P) {
24    int n = (int)P.size();
25    long double s = 0;
26    for (int i = 0; i < n; ++i) {
27        int j = (i + 1) % n;
28        s += cross(P[i], P[j]);
29    }
30    return 0.5L * s;
31}
32
33// Centroid using edge-based formula; works with signed area (nonzero)
34Point polygonCentroid(const vector<Point> &P) {
35    int n = (int)P.size();
36    long double A2 = 0;       // 2 * signed area
37    long double Cx_num = 0;   // numerator for Cx: sum (xi + xj) * cross
38    long double Cy_num = 0;   // numerator for Cy: sum (yi + yj) * cross
39    for (int i = 0; i < n; ++i) {
40        int j = (i + 1) % n;
41        long double cr = cross(P[i], P[j]);
42        A2 += cr;
43        Cx_num += (P[i].x + P[j].x) * cr;
44        Cy_num += (P[i].y + P[j].y) * cr;
45    }
46    long double A = 0.5L * A2; // signed area
47    // Handle degeneracy: if area is nearly zero, fallback to average of vertices
48    if (fabsl(A) < 1e-18L) {
49        long double sx = 0, sy = 0;
50        for (auto &p : P) { sx += p.x; sy += p.y; }
51        return { sx / (long double)P.size(), sy / (long double)P.size() };
52    }
53    long double Cx = Cx_num / (3.0L * A2); // since Cx = (1 / (6A)) * sum(...), and A2 = 2A
54    long double Cy = Cy_num / (3.0L * A2);
55    return { Cx, Cy };
56}
57
58int main() {
59    ios::sync_with_stdio(false);
60    cin.tie(nullptr);
61
62    int n;
63    if (!(cin >> n)) return 0;
64    vector<Point> P(n);
65    for (int i = 0; i < n; ++i) cin >> P[i].x >> P[i].y;
66
67    dedupeClosingVertex(P);
68    if ((int)P.size() < 3) {
69        cout << fixed << setprecision(10);
70        if (P.empty()) { cout << 0 << "\n" << 0 << " " << 0 << "\n"; }
71        else if ((int)P.size() == 1) { cout << 0 << "\n" << P[0].x << " " << P[0].y << "\n"; }
72        else { // 2 points: area 0, centroid = midpoint
73            long double cx = (P[0].x + P[1].x) / 2.0L;
74            long double cy = (P[0].y + P[1].y) / 2.0L;
75            cout << 0 << "\n" << cx << " " << cy << "\n";
76        }
77        return 0;
78    }
79
80    long double A_signed = polygonSignedArea(P);
81    // Normalize to CCW for downstream algorithms, if desired
82    if (A_signed < 0) {
83        reverse(P.begin(), P.end());
84        A_signed = -A_signed; // now positive
85    }
86
87    Point C = polygonCentroid(P); // now computed on CCW order
88
89    cout << fixed << setprecision(10);
90    cout << "area=" << (double)A_signed << "\n";
91    cout << "centroid=" << (double)C.x << " " << (double)C.y << "\n";
92    return 0;
93}
94

Reads a polygon, removes a duplicate last equals-first vertex, computes the signed area, enforces CCW orientation by reversing if needed, and computes the centroid using the edge-based formulas. Degenerate polygons fall back to an average of vertices to avoid division by a near-zero area.

Time: O(n)Space: O(1)
Overflow-safe double area with __int128 and centroid in long double
1#include <bits/stdc++.h>
2using namespace std;
3
4struct IPoint { long long x, y; };
5
6// Print __int128 for debugging/inspection
7string to_string_int128(__int128 v) {
8    if (v == 0) return "0";
9    bool neg = v < 0; if (neg) v = -v;
10    string s;
11    while (v) { int d = (int)(v % 10); s.push_back(char('0' + d)); v /= 10; }
12    if (neg) s.push_back('-');
13    reverse(s.begin(), s.end());
14    return s;
15}
16
17// Compute 2*area in 128-bit exactly
18__int128 doubleArea128(const vector<IPoint> &P) {
19    int n = (int)P.size();
20    __int128 s = 0;
21    for (int i = 0; i < n; ++i) {
22        int j = (i + 1) % n;
23        __int128 xi = P[i].x, yi = P[i].y, xj = P[j].x, yj = P[j].y;
24        s += xi * yj - xj * yi;
25    }
26    return s; // may be negative (CW)
27}
28
29// Centroid using long double accumulators, but cross computed from 128-bit then cast
30pair<long double,long double> centroidLD(const vector<IPoint> &P) {
31    int n = (int)P.size();
32    __int128 A2_128 = 0;
33    long double Cx_num = 0.0L, Cy_num = 0.0L;
34    for (int i = 0; i < n; ++i) {
35        int j = (i + 1) % n;
36        __int128 cr128 = (__int128)P[i].x * P[j].y - (__int128)P[j].x * P[i].y;
37        long double cr = (long double)cr128; // exact up to 63-bit cr; still robust for many cases
38        A2_128 += cr128;
39        Cx_num += ( (long double)P[i].x + (long double)P[j].x ) * cr;
40        Cy_num += ( (long double)P[i].y + (long double)P[j].y ) * cr;
41    }
42    long double A2 = (long double)A2_128;
43    if (fabsl(A2) < 1e-18L) {
44        // Degenerate: average of vertices
45        long double sx = 0, sy = 0;
46        for (auto &p : P) { sx += (long double)p.x; sy += (long double)p.y; }
47        return { sx / (long double)P.size(), sy / (long double)P.size() };
48    }
49    long double Cx = Cx_num / (3.0L * A2);
50    long double Cy = Cy_num / (3.0L * A2);
51    return {Cx, Cy};
52}
53
54int main(){
55    ios::sync_with_stdio(false);
56    cin.tie(nullptr);
57
58    int n; cin >> n;
59    vector<IPoint> P(n);
60    for (int i = 0; i < n; ++i) cin >> P[i].x >> P[i].y;
61
62    // Optional: remove repeated closing point if present
63    if (n >= 2 && P.front().x == P.back().x && P.front().y == P.back().y) {
64        P.pop_back(); n--;
65    }
66
67    __int128 A2 = doubleArea128(P);
68    long double area = fabsl((long double)A2) / 2.0L;
69    auto C = centroidLD(P);
70
71    cout << fixed << setprecision(10);
72    cout << "signed_double_area=" << to_string_int128(A2) << "\n";
73    cout << "area=" << (double)area << "\n";
74    cout << "centroid=" << (double)C.first << " " << (double)C.second << "\n";
75}
76

Accumulates 2×area exactly in 128-bit integers to avoid overflow with large 64-bit coordinates. The centroid is computed with long double using cross products sourced from 128-bit intermediates, reducing both overflow and rounding error.

Time: O(n)Space: O(1)
Centroid via triangulation (fan) and verification against edge formula
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Pt { long double x, y; };
5
6static inline Pt operator-(const Pt &a, const Pt &b) { return {a.x - b.x, a.y - b.y}; }
7static inline long double cross(const Pt &a, const Pt &b) { return a.x*b.y - a.y*b.x; }
8
9// Direct edge-based centroid
10pair<long double,long double> centroidEdge(const vector<Pt> &P) {
11    int n = (int)P.size();
12    long double A2 = 0, Cx_num = 0, Cy_num = 0;
13    for (int i = 0; i < n; ++i) {
14        int j = (i + 1) % n;
15        long double cr = cross(P[i], P[j]);
16        A2 += cr;
17        Cx_num += (P[i].x + P[j].x) * cr;
18        Cy_num += (P[i].y + P[j].y) * cr;
19    }
20    if (fabsl(A2) < 1e-18L) return {NAN, NAN};
21    return { Cx_num / (3.0L * A2), Cy_num / (3.0L * A2) };
22}
23
24// Triangulation-based centroid: fan from P0
25pair<long double,long double> centroidTriangulate(const vector<Pt> &P) {
26    int n = (int)P.size();
27    Pt O = P[0];
28    long double A_sum = 0.0L; // signed area sum
29    long double Cx_sum = 0.0L, Cy_sum = 0.0L;
30    for (int i = 1; i + 1 < n; ++i) {
31        Pt a = P[i] - O;
32        Pt b = P[i+1] - O;
33        long double A_tri = 0.5L * cross(a, b); // signed area of triangle O, P[i], P[i+1]
34        // Centroid of triangle O, P[i], P[i+1]
35        long double cx = (O.x + P[i].x + P[i+1].x) / 3.0L;
36        long double cy = (O.y + P[i].y + P[i+1].y) / 3.0L;
37        A_sum += A_tri;
38        Cx_sum += A_tri * cx;
39        Cy_sum += A_tri * cy;
40    }
41    if (fabsl(A_sum) < 1e-18L) return {NAN, NAN};
42    return { Cx_sum / A_sum, Cy_sum / A_sum };
43}
44
45int main(){
46    ios::sync_with_stdio(false);
47    cin.tie(nullptr);
48
49    // Example: a concave pentagon
50    vector<Pt> P = {
51        {0,0}, {4,0}, {4,3}, {2,1}, {0,3}
52    };
53
54    auto C1 = centroidEdge(P);
55    auto C2 = centroidTriangulate(P);
56
57    cout << fixed << setprecision(10);
58    cout << "centroid_edge=" << (double)C1.first << " " << (double)C1.second << "\n";
59    cout << "centroid_triangulate=" << (double)C2.first << " " << (double)C2.second << "\n";
60    // Verify closeness
61    long double dx = C1.first - C2.first;
62    long double dy = C1.second - C2.second;
63    cout << "delta=" << (double)fabsl(dx) << " " << (double)fabsl(dy) << "\n";
64    return 0;
65}
66

Computes the centroid in two ways: the direct edge-based formula and a sum over fan-triangulated triangles. The outputs match up to numerical error, illustrating the equivalence of the two methods.

Time: O(n)Space: O(1)