Triangulating a Polygon: Ear Clipping
Cut any simple polygon into n - 2 triangles with exact ear clipping, check the result without trusting it, and place art gallery guards by 3-coloring.
Why cut a polygon into triangles
A GPU draws triangles, not polygons. To fill the outline of a country on a map or a glyph in a font, a renderer first cuts the outline into triangles. A finite element solver needs its domain as a mesh of triangles before it can set up a single equation. A physics engine that only handles convex shapes can treat a concave obstacle as a set of triangles. Even computing an area, or picking a uniformly random point inside a polygon, is easiest on triangles.
Cutting a polygon into triangles whose corners are the polygon's own vertices is called triangulating it. The cuts are diagonals: segments between two vertices that lie inside the polygon and touch its boundary only at their ends. For a convex polygon this is trivial, because every segment between two vertices is a diagonal and a fan from vertex 0 does the job. For a concave polygon, most segments between vertices leave the polygon, and a fan produces triangles that stick out of it.
This lesson builds ear clipping, the algorithm most hand-written triangulators use, with the exact predicates from lesson 1 and the polygon conventions from lesson 5: a std::vector<Point>, counter-clockwise, no repeated closing vertex, integer coordinates. Then it checks the output independently, measures the cost, and uses the triangulation to solve a classic problem: how many guards does an art gallery need?
Two facts that make ear clipping work
Two theorems about simple polygons (polygons whose edges meet only at shared vertices) carry the whole algorithm.
Every simple polygon with n vertices can be triangulated, and every triangulation has exactly n - 2 triangles (using n - 3 diagonals). The count follows from angles. The interior angles of a simple polygon add up to (n - 2) * 180 degrees. In a triangulation, the triangles' corners are exactly the polygon's corners, split up, so the triangles' angles add up to the same total, and each triangle contributes 180 degrees. So there are n - 2 of them, whatever the shape.
An ear is a vertex b, with neighbors a before it and c after it, such that ac is a diagonal. Cutting off the triangle abc leaves a simple polygon with one vertex fewer. The two ears theorem says that every simple polygon with more than three vertices has at least two ears that do not overlap. It is usually cited from G. H. Meisters' 1975 paper "Polygons have ears", which introduced the word; the result was proved earlier by Max Dehn. A short argument: take any triangulation, and connect two triangles when they share a diagonal. The result is a tree (cutting a polygon along one diagonal splits it in two), and a tree with at least two nodes has at least two leaves. A leaf triangle has two polygon edges and one diagonal, which makes it an ear.
Together they give the algorithm: find an ear, cut it off, repeat on the smaller polygon. The theorem guarantees that an ear always exists, so on a simple polygon the loop cannot get stuck.
The ear test, exactly
Whether b is an ear comes down to two orientation questions.
bmust be a strictly convex corner:cross(a, b, c) > 0. A reflex corner (a right turn on a counter-clockwise polygon) has its triangle outside the polygon. A straight corner (cross == 0) has a triangle of zero area.- No other vertex may lie in the closed triangle
abc, including its edges. If any vertex were strictly inside, the polygon's boundary would pass through the triangle andacwould not be a diagonal. If a vertex lies exactly on the segmentac, cutting alongacwould run through that vertex and leave a polygon with a zero-width pinch.
For a simple polygon these two conditions are enough. If b is convex and the closed triangle contains no other vertex, no edge can enter the triangle: it could not cross ab or bc (the polygon is simple), and it has no endpoint inside to end at. So the triangle is part of the polygon, and ac is a diagonal. Both tests are signs of cross products of integers, so they are exact, and "on the edge" means exactly on the edge.
Try it by hand on the polygon from lesson 5, (0,0), (8,0), (8,2), (6,4), (4,2), (2,2), (0,4), numbered 0 to 6.
- Vertex 0 at
(0,0)is convex, but its triangle(0,4), (0,0), (8,0)contains vertex 5 at(2,2): the edge from(8,0)to(0,4)passes above it at height 3. Not an ear. - Vertex 1 at
(8,0)is convex, and its triangle(0,0), (8,0), (8,2)contains no other vertex. It is an ear. - Vertex 4 at
(4,2)turns right (it is the bottom of the valley). Not an ear. - Vertex 5 at
(2,2)sits between(4,2)and(0,4), and turns right too.
Ear clipping in code
The remaining polygon is kept as a circular doubly linked list in two arrays, prev and next, so cutting off an ear is two assignments. Each vertex's ear status is computed once at the start and cached. Cutting off b changes the triangle of only its two neighbors, so only those two are re-tested.
The function returns std::expected: a list of triangles, or a reason it could not finish. A simple counter-clockwise polygon always succeeds. A clockwise or self-intersecting one may run out of ears, and that is reported instead of looping forever.
#include <array>
#include <expected>
#include <print>
#include <string>
#include <vector>
struct Point { long long x, y; };
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
using Triangle = std::array<int, 3>; // vertex indices, counter-clockwise
// p in the closed triangle abc (abc counter-clockwise): on or left of every edge.
bool inClosedTriangle(Point a, Point b, Point c, Point p) {
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}
// Ear clipping for a simple, counter-clockwise polygon. O(n^2) worst case.
std::expected<std::vector<Triangle>, std::string>
triangulate(const std::vector<Point>& poly) {
const int n = int(poly.size());
if (n < 3) return std::unexpected("fewer than 3 vertices");
std::vector<int> prev(n), next(n); // the remaining polygon as a circular list
for (int i = 0; i < n; ++i) { prev[i] = (i + n - 1) % n; next[i] = (i + 1) % n; }
auto isEar = [&](int b) {
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // reflex or straight
for (int v = next[c]; v != a; v = next[v]) // all other vertices
if (inClosedTriangle(poly[a], poly[b], poly[c], poly[v])) return false;
return true;
};
std::vector<char> ear(n);
for (int i = 0; i < n; ++i) ear[i] = isEar(i);
std::vector<Triangle> result;
int b = 0;
for (int remaining = n; remaining > 3; --remaining) {
for (int start = b; !ear[b];) {
b = next[b];
if (b == start) return std::unexpected("no ear: not simple or not CCW");
}
int a = prev[b], c = next[b];
result.push_back({a, b, c});
next[a] = c; prev[c] = a; // unlink b
ear[a] = isEar(a); ear[c] = isEar(c); // only the neighbors can change
b = c;
}
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0)
return std::unexpected("last triangle is degenerate: not simple or not CCW");
result.push_back({a, b, c});
return result;
}
int main() {
// The polygon from the previous lesson: counter-clockwise, with two reflex
// vertices at (4, 2) and (2, 2).
std::vector<Point> poly{{0, 0}, {8, 0}, {8, 2}, {6, 4}, {4, 2}, {2, 2}, {0, 4}};
auto triangles = triangulate(poly);
if (!triangles) {
std::println("failed: {}", triangles.error());
return 1;
}
long long polygonArea = 0, sum = 0;
for (std::size_t i = 0; i < poly.size(); ++i)
polygonArea += cross({0, 0}, poly[i], poly[(i + 1) % poly.size()]);
for (auto [a, b, c] : *triangles) {
long long twice = cross(poly[a], poly[b], poly[c]);
sum += twice;
std::println("triangle ({}, {}, {}) twice area {}", a, b, c, twice);
}
std::println("{} vertices, {} triangles", poly.size(), triangles->size());
std::println("twice area: polygon {}, sum of triangles {}", polygonArea, sum);
}Press Run to compile and run this example.
triangle (0, 1, 2) twice area 16
triangle (2, 3, 4) twice area 8
triangle (5, 6, 0) twice area 8
triangle (0, 2, 4) twice area 8
triangle (0, 4, 5) twice area 4
7 vertices, 5 triangles
twice area: polygon 44, sum of triangles 44The first ear is vertex 1, as found by hand. Seven vertices give five triangles, and their areas add up to the polygon's area exactly. Vertex 5, a reflex corner, is never an ear itself, but it ends up as a corner of two triangles: a vertex that cannot be cut off still gets used, as a corner of the ears around it.
Cost. Each ear test scans the remaining vertices, so it is O(n). There are n tests at the start and two after each of the n - 3 cuts. Finding the next ear walks the list, at most n steps per cut. The total is O(n^2) in the worst case.
Seeing the triangulation
A spiral-shaped polygon with four reflex corners, drawn with its triangles in blue. The program uses the course's Svg helper, which takes y-up coordinates and flips them for the picture.
#include <array>
#include <expected>
#include <format>
#include <print>
#include <string>
#include <vector>
struct Point { long long x, y; };
class Svg {
public:
Svg(double width, double height) : w_(width), h_(height) {}
void line(Point a, Point b, const char* color = "#1f2937", double width = 1.5) {
add("<line x1=\"{}\" y1=\"{}\" x2=\"{}\" y2=\"{}\" stroke=\"{}\" stroke-width=\"{}\"/>",
a.x, fy(a.y), b.x, fy(b.y), color, width);
}
void dot(Point p, const char* color = "#1f2937", double r = 3) {
add("<circle cx=\"{}\" cy=\"{}\" r=\"{}\" fill=\"{}\"/>", p.x, fy(p.y), r, color);
}
void polygon(const std::vector<Point>& pts, const char* stroke = "#1f2937",
const char* fill = "none") {
std::string list;
for (Point p : pts) list += std::format("{},{} ", p.x, fy(p.y));
add("<polygon points=\"{}\" stroke=\"{}\" fill=\"{}\" stroke-width=\"1.5\"/>", list, stroke, fill);
}
void text(Point p, const std::string& s, double size = 8) {
add("<text x=\"{}\" y=\"{}\" font-size=\"{}\">{}</text>", p.x, fy(p.y), size, s);
}
void print() const {
std::println("<svg viewBox=\"0 0 {} {}\">", w_, h_);
std::print("{}", body_);
std::println("</svg>");
}
private:
double fy(double y) const { return h_ - y; } // SVG's y axis points down
template <class... Args>
void add(std::format_string<Args...> fmt, Args&&... args) {
body_ += std::format(fmt, std::forward<Args>(args)...);
body_ += '\n';
}
double w_, h_;
std::string body_;
};
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
using Triangle = std::array<int, 3>; // vertex indices, counter-clockwise
// p in the closed triangle abc (abc counter-clockwise): on or left of every edge.
bool inClosedTriangle(Point a, Point b, Point c, Point p) {
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}
// Ear clipping for a simple, counter-clockwise polygon. O(n^2) worst case.
std::expected<std::vector<Triangle>, std::string>
triangulate(const std::vector<Point>& poly) {
const int n = int(poly.size());
if (n < 3) return std::unexpected("fewer than 3 vertices");
std::vector<int> prev(n), next(n); // the remaining polygon as a circular list
for (int i = 0; i < n; ++i) { prev[i] = (i + n - 1) % n; next[i] = (i + 1) % n; }
auto isEar = [&](int b) {
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // reflex or straight
for (int v = next[c]; v != a; v = next[v]) // all other vertices
if (inClosedTriangle(poly[a], poly[b], poly[c], poly[v])) return false;
return true;
};
std::vector<char> ear(n);
for (int i = 0; i < n; ++i) ear[i] = isEar(i);
std::vector<Triangle> result;
int b = 0;
for (int remaining = n; remaining > 3; --remaining) {
for (int start = b; !ear[b];) {
b = next[b];
if (b == start) return std::unexpected("no ear: not simple or not CCW");
}
int a = prev[b], c = next[b];
result.push_back({a, b, c});
next[a] = c; prev[c] = a; // unlink b
ear[a] = isEar(a); ear[c] = isEar(c); // only the neighbors can change
b = c;
}
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0)
return std::unexpected("last triangle is degenerate: not simple or not CCW");
result.push_back({a, b, c});
return result;
}
int main() {
// A spiral-shaped polygon on a 10 by 10 grid, counter-clockwise.
std::vector<Point> poly{{0, 0}, {10, 0}, {10, 6}, {4, 6}, {4, 4}, {7, 4},
{7, 2}, {2, 2}, {2, 8}, {10, 8}, {10, 10}, {0, 10}};
auto triangles = triangulate(poly);
if (!triangles) return 1;
auto toSvg = [](Point p) { return Point{16 * p.x + 10, 16 * p.y + 10}; };
Svg svg(190, 180);
for (auto [a, b, c] : *triangles) // each triangle, thin and lightly filled
svg.polygon({toSvg(poly[a]), toSvg(poly[b]), toSvg(poly[c])}, "#2563eb",
"rgba(37,99,235,0.15)");
std::vector<Point> outline;
for (Point p : poly) outline.push_back(toSvg(p));
svg.polygon(outline); // the boundary on top, dark
for (std::size_t i = 0; i < poly.size(); ++i) {
svg.dot(toSvg(poly[i]));
svg.text({toSvg(poly[i]).x + 3, toSvg(poly[i]).y + 3}, std::to_string(i));
}
svg.print();
}Press Run to compile and run this example.
Twelve vertices, ten triangles. Some triangles are long and thin: ear clipping takes the first ear it finds, with no regard for shape. For rendering that does not matter. For a finite element mesh it does, because thin triangles hurt the accuracy of the solution, and that is the problem the next lesson solves for point sets.
How much work: counting containment tests
To see the O(n^2) rather than take it on trust, count how often the ear test checks a vertex against a triangle. The program triangulates two families at growing sizes: convex polygons with vertices on the parabola y = x^2, and combs with narrow teeth.
#include <array>
#include <expected>
#include <print>
#include <string>
#include <vector>
struct Point { long long x, y; };
long containmentTests = 0; // how often the ear test looks at a vertex
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
using Triangle = std::array<int, 3>; // vertex indices, counter-clockwise
// p in the closed triangle abc (abc counter-clockwise): on or left of every edge.
bool inClosedTriangle(Point a, Point b, Point c, Point p) {
++containmentTests;
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}
// Ear clipping for a simple, counter-clockwise polygon. O(n^2) worst case.
std::expected<std::vector<Triangle>, std::string>
triangulate(const std::vector<Point>& poly) {
const int n = int(poly.size());
if (n < 3) return std::unexpected("fewer than 3 vertices");
std::vector<int> prev(n), next(n); // the remaining polygon as a circular list
for (int i = 0; i < n; ++i) { prev[i] = (i + n - 1) % n; next[i] = (i + 1) % n; }
auto isEar = [&](int b) {
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // reflex or straight
for (int v = next[c]; v != a; v = next[v]) // all other vertices
if (inClosedTriangle(poly[a], poly[b], poly[c], poly[v])) return false;
return true;
};
std::vector<char> ear(n);
for (int i = 0; i < n; ++i) ear[i] = isEar(i);
std::vector<Triangle> result;
int b = 0;
for (int remaining = n; remaining > 3; --remaining) {
for (int start = b; !ear[b];) {
b = next[b];
if (b == start) return std::unexpected("no ear: not simple or not CCW");
}
int a = prev[b], c = next[b];
result.push_back({a, b, c});
next[a] = c; prev[c] = a; // unlink b
ear[a] = isEar(a); ear[c] = isEar(c); // only the neighbors can change
b = c;
}
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0)
return std::unexpected("last triangle is degenerate: not simple or not CCW");
result.push_back({a, b, c});
return result;
}
// n vertices on the parabola y = x^2: convex, counter-clockwise.
std::vector<Point> convexPolygon(int n) {
std::vector<Point> poly;
for (long long i = 0; i < n; ++i) poly.push_back({i, i * i});
return poly;
}
// A comb with k narrow teeth: 3k + 2 vertices, 2k of them reflex.
std::vector<Point> comb(int k) {
std::vector<Point> poly{{0, 0}, {4LL * k, 0}};
for (long long i = k - 1; i >= 0; --i) {
poly.push_back({4 * i + 3, 4}); // right foot of tooth i
poly.push_back({4 * i + 2, 12}); // tip
poly.push_back({4 * i + 1, 4}); // left foot
}
return poly;
}
int main() {
std::println("{:>6} {:>14} {:>9} {:>14} {:>9}", "n", "convex tests", "/ n^2",
"comb tests", "/ n^2");
for (int k : {16, 32, 64, 128, 256}) {
auto c = comb(k);
auto n = c.size();
containmentTests = 0;
auto ok1 = triangulate(convexPolygon(int(n))).has_value();
long convexTests = containmentTests;
containmentTests = 0;
auto ok2 = triangulate(c).has_value();
if (!ok1 || !ok2) return 1;
double n2 = double(n) * double(n);
std::println("{:>6} {:>14} {:>9.2f} {:>14} {:>9.2f}", n, convexTests,
convexTests / n2, containmentTests, containmentTests / n2);
}
}Press Run to compile and run this example.
n convex tests / n^2 comb tests / n^2
50 4512 1.80 1403 0.56
98 18240 1.90 5372 0.56
194 73344 1.95 20987 0.56
386 294144 1.97 82940 0.56
770 1178112 1.99 329723 0.56Doubling n multiplies the count by four, in both families, and the ratio to n^2 settles to a constant. The convex polygon is the more expensive one here: every vertex is a candidate ear, and each test has to scan every other vertex to confirm that the triangle is empty. Rejections can be cheaper than acceptances, because a test stops at the first vertex it finds inside.
Eberly's note on ear clipping (see Further reading) tests only reflex vertices against the candidate triangle, which brings the cost down when few vertices are reflex. The version here checks every vertex: slower, but it needs no extra argument about straight vertices or vertices lying exactly on the diagonal.
Checking a triangulation without trusting it
The program that produced a triangulation is the worst judge of it. A separate checker should verify properties that every correct triangulation has, using only the polygon and the triangles:
- there are exactly n - 2 triangles;
- every triangle is counter-clockwise with positive area (exact, with
cross); - the triangle areas add up to the polygon's shoelace area (exact);
- no two triangles overlap.
The last check uses the separating axis test: two convex shapes have disjoint interiors exactly when some edge of one of them has the whole other shape on its outer side. With counter-clockwise triangles that is three cross signs per edge.
The random polygons are generated as in lesson 5: random points on a small grid, sorted by angle around the lowest one. On a grid of side 2 to 8 they come with many collinear and straight vertices.
#include <algorithm>
#include <array>
#include <expected>
#include <print>
#include <string>
#include <vector>
struct Point { long long x, y; };
struct Lcg {
unsigned long long s;
unsigned next() { s = s * 6364136223846793005ULL + 1442695040888963407ULL; return unsigned(s >> 33); }
int range(int lo, int hi) { return lo + int(next() % unsigned(hi - lo + 1)); } // inclusive
};
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
using Triangle = std::array<int, 3>; // vertex indices, counter-clockwise
// p in the closed triangle abc (abc counter-clockwise): on or left of every edge.
bool inClosedTriangle(Point a, Point b, Point c, Point p) {
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}
// Ear clipping for a simple, counter-clockwise polygon. O(n^2) worst case.
std::expected<std::vector<Triangle>, std::string>
triangulate(const std::vector<Point>& poly) {
const int n = int(poly.size());
if (n < 3) return std::unexpected("fewer than 3 vertices");
std::vector<int> prev(n), next(n); // the remaining polygon as a circular list
for (int i = 0; i < n; ++i) { prev[i] = (i + n - 1) % n; next[i] = (i + 1) % n; }
auto isEar = [&](int b) {
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // reflex or straight
for (int v = next[c]; v != a; v = next[v]) // all other vertices
if (inClosedTriangle(poly[a], poly[b], poly[c], poly[v])) return false;
return true;
};
std::vector<char> ear(n);
for (int i = 0; i < n; ++i) ear[i] = isEar(i);
std::vector<Triangle> result;
int b = 0;
for (int remaining = n; remaining > 3; --remaining) {
for (int start = b; !ear[b];) {
b = next[b];
if (b == start) return std::unexpected("no ear: not simple or not CCW");
}
int a = prev[b], c = next[b];
result.push_back({a, b, c});
next[a] = c; prev[c] = a; // unlink b
ear[a] = isEar(a); ear[c] = isEar(c); // only the neighbors can change
b = c;
}
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0)
return std::unexpected("last triangle is degenerate: not simple or not CCW");
result.push_back({a, b, c});
return result;
}
long long twiceArea(const std::vector<Point>& poly) {
long long sum = 0;
for (std::size_t i = 0; i < poly.size(); ++i)
sum += cross({0, 0}, poly[i], poly[(i + 1) % poly.size()]);
return sum;
}
// Separating axis test: interiors are disjoint iff the other triangle lies
// entirely on the outer side of some edge (both triangles counter-clockwise).
bool interiorsDisjoint(std::array<Point, 3> t, std::array<Point, 3> u) {
for (int pass = 0; pass < 2; ++pass, std::swap(t, u))
for (int e = 0; e < 3; ++e)
if (std::ranges::all_of(u, [&](Point v) {
return cross(t[e], t[(e + 1) % 3], v) <= 0; }))
return true;
return false;
}
// What any triangulation must satisfy, checked without knowing how it was made.
bool valid(const std::vector<Point>& poly, const std::vector<Triangle>& tris) {
long long sum = 0;
std::vector<std::array<Point, 3>> pts;
for (auto [a, b, c] : tris) {
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // must be CCW
sum += cross(poly[a], poly[b], poly[c]);
pts.push_back({poly[a], poly[b], poly[c]});
}
for (std::size_t i = 0; i < pts.size(); ++i)
for (std::size_t j = i + 1; j < pts.size(); ++j)
if (!interiorsDisjoint(pts[i], pts[j])) return false;
return tris.size() == poly.size() - 2 && sum == twiceArea(poly);
}
// Random simple polygon: points sorted by angle around the lowest one.
std::vector<Point> randomPolygon(Lcg& rng, int n, int R) {
std::vector<Point> pts;
for (int i = 0; i < n; ++i) pts.push_back({rng.range(0, R), rng.range(0, R)});
std::ranges::sort(pts, {}, [](Point p) { return std::pair{p.y, p.x}; });
pts.erase(std::unique(pts.begin(), pts.end(), [](Point a, Point b) {
return a.x == b.x && a.y == b.y; }), pts.end());
Point o = pts[0];
auto dist = [o](Point p) {
return (p.x - o.x) * (p.x - o.x) + (p.y - o.y) * (p.y - o.y); };
std::sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) {
long long turn = cross(o, a, b);
return turn != 0 ? turn > 0 : dist(a) < dist(b);
});
auto last = pts.end() - 1; // the last ray must be walked inwards
while (last - 1 > pts.begin() && cross(o, *(last - 1), pts.back()) == 0) --last;
std::reverse(last, pts.end());
return pts;
}
int main() {
Lcg rng{7};
int tested = 0, passed = 0;
while (tested < 20000) {
auto poly = randomPolygon(rng, rng.range(3, 14), rng.range(2, 8));
if (twiceArea(poly) <= 0) continue; // all points collinear
auto tris = triangulate(poly);
++tested, passed += tris && valid(poly, *tris);
}
std::println("random polygons: {} of {} triangulated correctly", passed, tested);
}Press Run to compile and run this example.
random polygons: 20000 of 20000 triangulated correctlyEvery polygon passed. As an extra check outside the program, the triangulations of 29,469 more random polygons were sampled on a grid four times finer: every sample point strictly inside the polygon was covered by a triangle, and no point strictly outside was.
Now feed it polygons that are not simple. Ear clipping does not detect self-intersection; it only notices when it gets stuck.
#include <algorithm>
#include <array>
#include <expected>
#include <print>
#include <string>
#include <vector>
struct Point { long long x, y; };
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
using Triangle = std::array<int, 3>; // vertex indices, counter-clockwise
// p in the closed triangle abc (abc counter-clockwise): on or left of every edge.
bool inClosedTriangle(Point a, Point b, Point c, Point p) {
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}
// Ear clipping for a simple, counter-clockwise polygon. O(n^2) worst case.
std::expected<std::vector<Triangle>, std::string>
triangulate(const std::vector<Point>& poly) {
const int n = int(poly.size());
if (n < 3) return std::unexpected("fewer than 3 vertices");
std::vector<int> prev(n), next(n); // the remaining polygon as a circular list
for (int i = 0; i < n; ++i) { prev[i] = (i + n - 1) % n; next[i] = (i + 1) % n; }
auto isEar = [&](int b) {
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // reflex or straight
for (int v = next[c]; v != a; v = next[v]) // all other vertices
if (inClosedTriangle(poly[a], poly[b], poly[c], poly[v])) return false;
return true;
};
std::vector<char> ear(n);
for (int i = 0; i < n; ++i) ear[i] = isEar(i);
std::vector<Triangle> result;
int b = 0;
for (int remaining = n; remaining > 3; --remaining) {
for (int start = b; !ear[b];) {
b = next[b];
if (b == start) return std::unexpected("no ear: not simple or not CCW");
}
int a = prev[b], c = next[b];
result.push_back({a, b, c});
next[a] = c; prev[c] = a; // unlink b
ear[a] = isEar(a); ear[c] = isEar(c); // only the neighbors can change
b = c;
}
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0)
return std::unexpected("last triangle is degenerate: not simple or not CCW");
result.push_back({a, b, c});
return result;
}
long long twiceArea(const std::vector<Point>& poly) {
long long sum = 0;
for (std::size_t i = 0; i < poly.size(); ++i)
sum += cross({0, 0}, poly[i], poly[(i + 1) % poly.size()]);
return sum;
}
// Separating axis test: interiors are disjoint iff the other triangle lies
// entirely on the outer side of some edge (both triangles counter-clockwise).
bool interiorsDisjoint(std::array<Point, 3> t, std::array<Point, 3> u) {
for (int pass = 0; pass < 2; ++pass, std::swap(t, u))
for (int e = 0; e < 3; ++e)
if (std::ranges::all_of(u, [&](Point v) {
return cross(t[e], t[(e + 1) % 3], v) <= 0; }))
return true;
return false;
}
// What any triangulation must satisfy, checked without knowing how it was made.
bool valid(const std::vector<Point>& poly, const std::vector<Triangle>& tris) {
long long sum = 0;
std::vector<std::array<Point, 3>> pts;
for (auto [a, b, c] : tris) {
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // must be CCW
sum += cross(poly[a], poly[b], poly[c]);
pts.push_back({poly[a], poly[b], poly[c]});
}
for (std::size_t i = 0; i < pts.size(); ++i)
for (std::size_t j = i + 1; j < pts.size(); ++j)
if (!interiorsDisjoint(pts[i], pts[j])) return false;
return tris.size() == poly.size() - 2 && sum == twiceArea(poly);
}
int main() {
// Two polygons that are not simple: a pentagram, and a twisted pentagon.
std::vector<Point> star{{5, 10}, {2, 0}, {10, 6}, {0, 6}, {8, 0}};
std::vector<Point> twisted{{0, 4}, {10, 0}, {9, 5}, {0, 1}, {7, 4}};
for (const auto& poly : {star, twisted}) {
auto tris = triangulate(poly);
if (!tris) {
std::println("error: {}", tris.error());
continue;
}
long long sum = 0;
for (auto [a, b, c] : *tris) sum += cross(poly[a], poly[b], poly[c]);
std::println("{} triangles, area sum {}, shoelace {}, valid: {}", tris->size(),
sum, twiceArea(poly), valid(poly, *tris));
}
}Press Run to compile and run this example.
error: last triangle is degenerate: not simple or not CCW
3 triangles, area sum 40, shoelace 40, valid: falseThe pentagram fails loudly. The twisted pentagon is worse: the algorithm returns three counter-clockwise triangles whose areas add up to the shoelace sum, so the cheap checks pass, and only the overlap test reveals that the triangles overlap. For self-intersecting input, the shoelace sum counts regions by their winding number (lesson 5), and ear clipping happily reproduces that count. A triangulator cannot be expected to repair its input; check simplicity first.
Guarding an art gallery with three colors
A classic question that a triangulation answers in a few lines: an art gallery's floor plan is a simple polygon with n walls. A guard stands at a fixed point and can see everything along an unobstructed straight line. How many guards are always enough?
Chvátal's art gallery theorem (Václav Chvátal, 1975) answers: floor(n / 3) guards always suffice, and some polygons need that many. Steve Fisk's 1978 proof is a few lines long and runs as a program:
- Triangulate the polygon.
- Color the vertices with three colors so that every triangle has one vertex of each color. This is always possible: color the first triangle, then cross diagonals one at a time. Each new triangle shares two already-colored vertices with the previous one, and its third vertex takes the color that is left. Because the triangles form a tree, no vertex is ever reached two ways with conflicting colors.
- Pick the color used least often. It has at most
floor(n / 3)vertices, by the pigeonhole principle. Put a guard on each.
Every triangle has a vertex of that color, a triangle is convex, so a guard at its corner sees all of it, and the triangles cover the polygon.
#include <algorithm>
#include <array>
#include <expected>
#include <map>
#include <print>
#include <string>
#include <vector>
struct Point { long long x, y; };
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
using Triangle = std::array<int, 3>; // vertex indices, counter-clockwise
// p in the closed triangle abc (abc counter-clockwise): on or left of every edge.
bool inClosedTriangle(Point a, Point b, Point c, Point p) {
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}
// Ear clipping for a simple, counter-clockwise polygon. O(n^2) worst case.
std::expected<std::vector<Triangle>, std::string>
triangulate(const std::vector<Point>& poly) {
const int n = int(poly.size());
if (n < 3) return std::unexpected("fewer than 3 vertices");
std::vector<int> prev(n), next(n); // the remaining polygon as a circular list
for (int i = 0; i < n; ++i) { prev[i] = (i + n - 1) % n; next[i] = (i + 1) % n; }
auto isEar = [&](int b) {
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // reflex or straight
for (int v = next[c]; v != a; v = next[v]) // all other vertices
if (inClosedTriangle(poly[a], poly[b], poly[c], poly[v])) return false;
return true;
};
std::vector<char> ear(n);
for (int i = 0; i < n; ++i) ear[i] = isEar(i);
std::vector<Triangle> result;
int b = 0;
for (int remaining = n; remaining > 3; --remaining) {
for (int start = b; !ear[b];) {
b = next[b];
if (b == start) return std::unexpected("no ear: not simple or not CCW");
}
int a = prev[b], c = next[b];
result.push_back({a, b, c});
next[a] = c; prev[c] = a; // unlink b
ear[a] = isEar(a); ear[c] = isEar(c); // only the neighbors can change
b = c;
}
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0)
return std::unexpected("last triangle is degenerate: not simple or not CCW");
result.push_back({a, b, c});
return result;
}
// Fisk's argument as code: walk the triangles across shared diagonals; each new
// triangle has two colored vertices, and its third gets the remaining color.
std::vector<int> threeColor(int n, const std::vector<Triangle>& tris) {
std::map<std::pair<int, int>, std::vector<int>> byEdge; // diagonal -> triangles
for (int t = 0; t < int(tris.size()); ++t)
for (int e = 0; e < 3; ++e) {
int u = tris[t][e], v = tris[t][(e + 1) % 3];
byEdge[std::minmax(u, v)].push_back(t);
}
std::vector<int> color(n, -1);
std::vector<char> seen(tris.size());
std::vector<int> queue{0};
seen[0] = true;
for (int e = 0; e < 3; ++e) color[tris[0][e]] = e;
for (std::size_t q = 0; q < queue.size(); ++q) {
const Triangle& t = tris[queue[q]];
for (int e = 0; e < 3; ++e) {
int u = t[e], v = t[(e + 1) % 3];
for (int other : byEdge[std::minmax(u, v)]) {
if (seen[other]) continue;
seen[other] = true;
queue.push_back(other);
for (int w : tris[other])
if (w != u && w != v) color[w] = 3 - color[u] - color[v];
}
}
}
return color;
}
// A comb with k narrow teeth: 3k + 2 vertices, and each tooth tip needs its own guard.
std::vector<Point> comb(int k) {
std::vector<Point> poly{{0, 0}, {4LL * k, 0}};
for (long long i = k - 1; i >= 0; --i) {
poly.push_back({4 * i + 3, 4}); // right foot of tooth i
poly.push_back({4 * i + 2, 12}); // tip
poly.push_back({4 * i + 1, 4}); // left foot
}
return poly;
}
int main() {
std::vector<Point> spiral{{0, 0}, {10, 0}, {10, 6}, {4, 6}, {4, 4}, {7, 4},
{7, 2}, {2, 2}, {2, 8}, {10, 8}, {10, 10}, {0, 10}};
for (const auto& [name, poly] : {std::pair{"spiral", spiral},
std::pair{"comb, 4 teeth", comb(4)}}) {
auto tris = triangulate(poly);
if (!tris) return 1;
auto color = threeColor(int(poly.size()), *tris);
bool proper = std::ranges::all_of(*tris, [&](const Triangle& t) {
return color[t[0]] + color[t[1]] + color[t[2]] == 3
&& color[t[0]] != color[t[1]]; // all of 0, 1, 2
});
int count[3] = {};
for (int c : color) ++count[c];
int best = int(std::ranges::min_element(count) - count);
std::println("{}: n = {}, color classes {} {} {}, all triangles 3-colored: {}",
name, poly.size(), count[0], count[1], count[2], proper);
std::print(" {} guards (n/3 rounded down is {}):", count[best], poly.size() / 3);
for (std::size_t v = 0; v < poly.size(); ++v)
if (color[v] == best) std::print(" ({}, {})", poly[v].x, poly[v].y);
std::println("");
}
}Press Run to compile and run this example.
spiral: n = 12, color classes 4 4 4, all triangles 3-colored: true
4 guards (n/3 rounded down is 4): (10, 6) (2, 2) (10, 8) (0, 10)
comb, 4 teeth: n = 14, color classes 4 5 5, all triangles 3-colored: true
4 guards (n/3 rounded down is 4): (13, 4) (9, 4) (5, 4) (1, 4)The comb shows why the bound cannot be improved. Its four teeth are narrow, and the region from which a tooth's tip is visible is a thin wedge below that tooth's opening. The wedges of different teeth do not overlap, so no single point sees two tips, and four guards are necessary. Fisk's method places exactly four, one at the left foot of each tooth:
#include <algorithm>
#include <array>
#include <expected>
#include <format>
#include <map>
#include <print>
#include <string>
#include <vector>
struct Point { long long x, y; };
class Svg {
public:
Svg(double width, double height) : w_(width), h_(height) {}
void line(Point a, Point b, const char* color = "#1f2937", double width = 1.5) {
add("<line x1=\"{}\" y1=\"{}\" x2=\"{}\" y2=\"{}\" stroke=\"{}\" stroke-width=\"{}\"/>",
a.x, fy(a.y), b.x, fy(b.y), color, width);
}
void dot(Point p, const char* color = "#1f2937", double r = 3) {
add("<circle cx=\"{}\" cy=\"{}\" r=\"{}\" fill=\"{}\"/>", p.x, fy(p.y), r, color);
}
void polygon(const std::vector<Point>& pts, const char* stroke = "#1f2937",
const char* fill = "none") {
std::string list;
for (Point p : pts) list += std::format("{},{} ", p.x, fy(p.y));
add("<polygon points=\"{}\" stroke=\"{}\" fill=\"{}\" stroke-width=\"1.5\"/>", list, stroke, fill);
}
void text(Point p, const std::string& s, double size = 8) {
add("<text x=\"{}\" y=\"{}\" font-size=\"{}\">{}</text>", p.x, fy(p.y), size, s);
}
void print() const {
std::println("<svg viewBox=\"0 0 {} {}\">", w_, h_);
std::print("{}", body_);
std::println("</svg>");
}
private:
double fy(double y) const { return h_ - y; } // SVG's y axis points down
template <class... Args>
void add(std::format_string<Args...> fmt, Args&&... args) {
body_ += std::format(fmt, std::forward<Args>(args)...);
body_ += '\n';
}
double w_, h_;
std::string body_;
};
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
using Triangle = std::array<int, 3>; // vertex indices, counter-clockwise
// p in the closed triangle abc (abc counter-clockwise): on or left of every edge.
bool inClosedTriangle(Point a, Point b, Point c, Point p) {
return cross(a, b, p) >= 0 && cross(b, c, p) >= 0 && cross(c, a, p) >= 0;
}
// Ear clipping for a simple, counter-clockwise polygon. O(n^2) worst case.
std::expected<std::vector<Triangle>, std::string>
triangulate(const std::vector<Point>& poly) {
const int n = int(poly.size());
if (n < 3) return std::unexpected("fewer than 3 vertices");
std::vector<int> prev(n), next(n); // the remaining polygon as a circular list
for (int i = 0; i < n; ++i) { prev[i] = (i + n - 1) % n; next[i] = (i + 1) % n; }
auto isEar = [&](int b) {
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0) return false; // reflex or straight
for (int v = next[c]; v != a; v = next[v]) // all other vertices
if (inClosedTriangle(poly[a], poly[b], poly[c], poly[v])) return false;
return true;
};
std::vector<char> ear(n);
for (int i = 0; i < n; ++i) ear[i] = isEar(i);
std::vector<Triangle> result;
int b = 0;
for (int remaining = n; remaining > 3; --remaining) {
for (int start = b; !ear[b];) {
b = next[b];
if (b == start) return std::unexpected("no ear: not simple or not CCW");
}
int a = prev[b], c = next[b];
result.push_back({a, b, c});
next[a] = c; prev[c] = a; // unlink b
ear[a] = isEar(a); ear[c] = isEar(c); // only the neighbors can change
b = c;
}
int a = prev[b], c = next[b];
if (cross(poly[a], poly[b], poly[c]) <= 0)
return std::unexpected("last triangle is degenerate: not simple or not CCW");
result.push_back({a, b, c});
return result;
}
// Fisk's argument as code: walk the triangles across shared diagonals; each new
// triangle has two colored vertices, and its third gets the remaining color.
std::vector<int> threeColor(int n, const std::vector<Triangle>& tris) {
std::map<std::pair<int, int>, std::vector<int>> byEdge; // diagonal -> triangles
for (int t = 0; t < int(tris.size()); ++t)
for (int e = 0; e < 3; ++e) {
int u = tris[t][e], v = tris[t][(e + 1) % 3];
byEdge[std::minmax(u, v)].push_back(t);
}
std::vector<int> color(n, -1);
std::vector<char> seen(tris.size());
std::vector<int> queue{0};
seen[0] = true;
for (int e = 0; e < 3; ++e) color[tris[0][e]] = e;
for (std::size_t q = 0; q < queue.size(); ++q) {
const Triangle& t = tris[queue[q]];
for (int e = 0; e < 3; ++e) {
int u = t[e], v = t[(e + 1) % 3];
for (int other : byEdge[std::minmax(u, v)]) {
if (seen[other]) continue;
seen[other] = true;
queue.push_back(other);
for (int w : tris[other])
if (w != u && w != v) color[w] = 3 - color[u] - color[v];
}
}
}
return color;
}
// A comb with k narrow teeth: 3k + 2 vertices, and each tooth tip needs its own guard.
std::vector<Point> comb(int k) {
std::vector<Point> poly{{0, 0}, {4LL * k, 0}};
for (long long i = k - 1; i >= 0; --i) {
poly.push_back({4 * i + 3, 4}); // right foot of tooth i
poly.push_back({4 * i + 2, 12}); // tip
poly.push_back({4 * i + 1, 4}); // left foot
}
return poly;
}
int main() {
auto poly = comb(4);
auto tris = triangulate(poly);
if (!tris) return 1;
auto color = threeColor(int(poly.size()), *tris);
int count[3] = {};
for (int c : color) ++count[c];
int guards = int(std::ranges::min_element(count) - count);
auto toSvg = [](Point p) { return Point{12 * p.x + 8, 12 * p.y + 8}; };
Svg svg(208, 160);
for (auto [a, b, c] : *tris)
svg.polygon({toSvg(poly[a]), toSvg(poly[b]), toSvg(poly[c])}, "#93c5fd",
"rgba(37,99,235,0.15)");
std::vector<Point> outline;
for (Point p : poly) outline.push_back(toSvg(p));
svg.polygon(outline);
const char* palette[3] = {"#2563eb", "#16a34a", "#1f2937"};
for (std::size_t v = 0; v < poly.size(); ++v) {
if (color[v] == guards) svg.dot(toSvg(poly[v]), "#dc2626", 5); // a guard
svg.dot(toSvg(poly[v]), palette[color[v]], 2.5);
}
svg.print();
}Press Run to compile and run this example.
The guards are the red-ringed vertices. Note what the theorem does not promise: the coloring gives floor(n / 3) guards, not the minimum for a particular polygon. Finding the minimum number of guards for a given polygon is NP-hard (Lee and Lin, 1986).