Skip to content

Commit 2cd27a7

Browse files
Copilotsyoyo
Copilot
and
syoyo
committed
Add sweep-line and earcut Z-curve triangulation algorithms with benchmark
Implement two new triangulation algorithms in sandbox/triangulation/: - **Sweep-Line**: Monotone polygon decomposition via sweep-line event processing (vertex classification, status structure with helpers), recursive polygon splitting at diagonals, and stack-based monotone polygon triangulation. - **Earcut Z-Curve**: Enhanced ear clipping using Z-order curve (Morton code) spatial indexing. Doubly-linked circular list with Z-sorted auxiliary list for fast point-in-triangle rejection. Falls back to full scan when Z-filtered pass gets stuck. Also add: - benchmark.cc: Measures all 5 algorithms (fan, earclip, MWT, sweep-line, earcut-Z) across regular n-gons, random convex, and star-shaped concave polygons of 4 to 1024 vertices. - 14 new test cases for the two new algorithms. - Updated Makefile with `make bench` target. Co-authored-by: syoyo <18676+syoyo@users.noreply.github.com>
1 parent 4c91a3c commit 2cd27a7

File tree

5 files changed

+1327
-7
lines changed

5 files changed

+1327
-7
lines changed

‎.gitignore‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ build/
77
/tests/tester
88
/tests/tester.dSYM
99
/sandbox/triangulation/triangulation_test
10+
/sandbox/triangulation/benchmark
1011
/_codeql_build_dir/
1112
/_codeql_detected_source_root
1213
/python/_version.py

‎sandbox/triangulation/Makefile‎

Lines changed: 11 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,21 +3,29 @@
33
# Usage:
44
# make — build the test binary
55
# make test — build and run all tests
6+
# make benchmark — build and run the benchmark
67
# make clean — remove build artifacts
78

89
CXX ?= g++
910
CXXFLAGS ?= -std=c++11 -O2 -Wall -Wextra
1011
TARGET = triangulation_test
12+
BENCH = benchmark
1113

12-
.PHONY: all test clean
14+
.PHONY: all test bench clean
1315

14-
all: $(TARGET)
16+
all: $(TARGET) $(BENCH)
1517

1618
$(TARGET): main.cc triangulation.h
1719
$(CXX) $(CXXFLAGS) -o $@ main.cc
1820

21+
$(BENCH): benchmark.cc triangulation.h
22+
$(CXX) $(CXXFLAGS) -o $@ benchmark.cc
23+
1924
test: $(TARGET)
2025
./$(TARGET)
2126

27+
bench: $(BENCH)
28+
./$(BENCH) --quick
29+
2230
clean:
23-
rm -f $(TARGET)
31+
rm -f $(TARGET) $(BENCH)

‎sandbox/triangulation/benchmark.cc‎

Lines changed: 291 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,291 @@
1+
// benchmark.cc — Benchmark program for triangulation algorithms.
2+
//
3+
// Build: make benchmark
4+
// Run: ./benchmark
5+
//
6+
// Generates regular n-gons, random convex, and random concave (star)
7+
// polygons of various sizes, then measures each algorithm's throughput.
8+
9+
#define TRIANGULATION_IMPLEMENTATION
10+
#include "triangulation.h"
11+
12+
#include <chrono>
13+
#include <cmath>
14+
#include <cstdio>
15+
#include <cstdlib>
16+
#include <cstring>
17+
#include <string>
18+
#include <vector>
19+
20+
// ---------------------------------------------------------------------------
21+
// Polygon generators
22+
// ---------------------------------------------------------------------------
23+
24+
static const double kPi = 3.14159265358979323846;
25+
26+
// Regular n-gon with given number of vertices, radius 1.
27+
static void MakeRegularNgon(size_t n, std::vector<double> *vertices,
28+
std::vector<size_t> *indices) {
29+
vertices->resize(n * 3);
30+
indices->resize(n);
31+
for (size_t i = 0; i < n; i++) {
32+
double angle = 2.0 * kPi * static_cast<double>(i) / static_cast<double>(n);
33+
(*vertices)[i * 3 + 0] = std::cos(angle);
34+
(*vertices)[i * 3 + 1] = std::sin(angle);
35+
(*vertices)[i * 3 + 2] = 0.0;
36+
(*indices)[i] = i;
37+
}
38+
}
39+
40+
// Star-shaped concave polygon with n points (2*n vertices total).
41+
// Outer radius 1.0, inner radius 0.4.
42+
static void MakeStarPolygon(size_t n_points, std::vector<double> *vertices,
43+
std::vector<size_t> *indices) {
44+
size_t n = n_points * 2;
45+
vertices->resize(n * 3);
46+
indices->resize(n);
47+
double outer_r = 1.0;
48+
double inner_r = 0.4;
49+
for (size_t i = 0; i < n; i++) {
50+
double angle =
51+
2.0 * kPi * static_cast<double>(i) / static_cast<double>(n);
52+
double r = (i % 2 == 0) ? outer_r : inner_r;
53+
(*vertices)[i * 3 + 0] = r * std::cos(angle);
54+
(*vertices)[i * 3 + 1] = r * std::sin(angle);
55+
(*vertices)[i * 3 + 2] = 0.0;
56+
(*indices)[i] = i;
57+
}
58+
}
59+
60+
// Simple pseudo-random number generator (deterministic, no stdlib dependency).
61+
struct SimpleRNG {
62+
uint64_t state;
63+
explicit SimpleRNG(uint64_t seed = 12345) : state(seed) {}
64+
uint64_t next() {
65+
state ^= state << 13;
66+
state ^= state >> 7;
67+
state ^= state << 17;
68+
return state;
69+
}
70+
double uniform() {
71+
return static_cast<double>(next() % 1000000) / 1000000.0;
72+
}
73+
};
74+
75+
// Random convex polygon with n vertices (random angles, sorted, on unit circle).
76+
static void MakeRandomConvex(size_t n, std::vector<double> *vertices,
77+
std::vector<size_t> *indices, uint64_t seed) {
78+
SimpleRNG rng(seed);
79+
std::vector<double> angles(n);
80+
for (size_t i = 0; i < n; i++) {
81+
angles[i] = rng.uniform() * 2.0 * kPi;
82+
}
83+
std::sort(angles.begin(), angles.end());
84+
85+
vertices->resize(n * 3);
86+
indices->resize(n);
87+
for (size_t i = 0; i < n; i++) {
88+
double r = 0.8 + 0.2 * rng.uniform();
89+
(*vertices)[i * 3 + 0] = r * std::cos(angles[i]);
90+
(*vertices)[i * 3 + 1] = r * std::sin(angles[i]);
91+
(*vertices)[i * 3 + 2] = 0.0;
92+
(*indices)[i] = i;
93+
}
94+
}
95+
96+
// ---------------------------------------------------------------------------
97+
// Benchmark harness
98+
// ---------------------------------------------------------------------------
99+
100+
typedef size_t (*TriFunc)(const std::vector<size_t> &,
101+
const std::vector<double> &,
102+
std::vector<size_t> *);
103+
104+
static size_t TriangulateMWTWrapper(const std::vector<size_t> &poly,
105+
const std::vector<double> &verts,
106+
std::vector<size_t> *out) {
107+
return triangulation::TriangulateMWT(poly, verts, out, nullptr);
108+
}
109+
110+
struct Algorithm {
111+
const char *name;
112+
TriFunc func;
113+
};
114+
115+
static Algorithm g_algorithms[] = {
116+
{"Fan", triangulation::TriangulateFan},
117+
{"Earclip", triangulation::TriangulateEarclip},
118+
{"MWT", TriangulateMWTWrapper},
119+
{"SweepLine", triangulation::TriangulateSweepLine},
120+
{"EarcutZ", triangulation::TriangulateEarcutZCurve},
121+
};
122+
static const size_t g_num_algorithms =
123+
sizeof(g_algorithms) / sizeof(g_algorithms[0]);
124+
125+
struct BenchResult {
126+
double us_per_call; // microseconds per triangulation call
127+
size_t num_triangles;
128+
bool valid;
129+
};
130+
131+
static BenchResult RunBenchmark(TriFunc func,
132+
const std::vector<size_t> &polygon,
133+
const std::vector<double> &vertices,
134+
size_t iterations) {
135+
BenchResult result;
136+
result.us_per_call = 0;
137+
result.num_triangles = 0;
138+
result.valid = true;
139+
140+
// Warm-up
141+
{
142+
std::vector<size_t> tris;
143+
result.num_triangles = func(polygon, vertices, &tris);
144+
if (tris.size() % 3 != 0 ||
145+
result.num_triangles != polygon.size() - 2) {
146+
result.valid = false;
147+
}
148+
// Validate all indices are in range
149+
for (size_t i = 0; i < tris.size(); i++) {
150+
if (tris[i] >= vertices.size() / 3) {
151+
result.valid = false;
152+
break;
153+
}
154+
}
155+
}
156+
157+
// Timed run
158+
auto start = std::chrono::high_resolution_clock::now();
159+
for (size_t iter = 0; iter < iterations; iter++) {
160+
std::vector<size_t> tris;
161+
func(polygon, vertices, &tris);
162+
}
163+
auto end = std::chrono::high_resolution_clock::now();
164+
165+
double elapsed_us =
166+
std::chrono::duration_cast<std::chrono::microseconds>(end - start)
167+
.count();
168+
result.us_per_call = elapsed_us / static_cast<double>(iterations);
169+
return result;
170+
}
171+
172+
// ---------------------------------------------------------------------------
173+
// Main
174+
// ---------------------------------------------------------------------------
175+
176+
static void PrintSeparator(size_t width) {
177+
for (size_t i = 0; i < width; i++) putchar('-');
178+
putchar('\n');
179+
}
180+
181+
int main(int argc, char **argv) {
182+
// Parse optional --quick flag for shorter runs
183+
bool quick = false;
184+
for (int i = 1; i < argc; i++) {
185+
if (strcmp(argv[i], "--quick") == 0) quick = true;
186+
}
187+
188+
printf("=== Triangulation Benchmark ===\n\n");
189+
190+
// Polygon sizes to test
191+
size_t convex_sizes[] = {4, 8, 16, 32, 64, 128, 256, 512, 1024};
192+
size_t num_convex_sizes = sizeof(convex_sizes) / sizeof(convex_sizes[0]);
193+
194+
size_t star_points[] = {4, 8, 16, 32, 64, 128, 256};
195+
size_t num_star_sizes = sizeof(star_points) / sizeof(star_points[0]);
196+
197+
// ---- Regular convex n-gons ----
198+
printf("Regular convex n-gons (time in microseconds per call):\n\n");
199+
printf("%-10s", "N");
200+
for (size_t a = 0; a < g_num_algorithms; a++) {
201+
printf(" %12s", g_algorithms[a].name);
202+
}
203+
printf("\n");
204+
PrintSeparator(10 + g_num_algorithms * 14);
205+
206+
for (size_t si = 0; si < num_convex_sizes; si++) {
207+
size_t nv = convex_sizes[si];
208+
std::vector<double> verts;
209+
std::vector<size_t> poly;
210+
MakeRegularNgon(nv, &verts, &poly);
211+
212+
size_t iters = quick ? 100 : std::max(static_cast<size_t>(10),
213+
static_cast<size_t>(100000 / nv));
214+
215+
printf("%-10zu", nv);
216+
for (size_t a = 0; a < g_num_algorithms; a++) {
217+
BenchResult r = RunBenchmark(g_algorithms[a].func, poly, verts, iters);
218+
if (r.valid) {
219+
printf(" %10.2f ", r.us_per_call);
220+
} else {
221+
printf(" %10s ", "INVALID");
222+
}
223+
}
224+
printf("\n");
225+
}
226+
227+
// ---- Random convex polygons ----
228+
printf("\nRandom convex polygons (time in microseconds per call):\n\n");
229+
printf("%-10s", "N");
230+
for (size_t a = 0; a < g_num_algorithms; a++) {
231+
printf(" %12s", g_algorithms[a].name);
232+
}
233+
printf("\n");
234+
PrintSeparator(10 + g_num_algorithms * 14);
235+
236+
for (size_t si = 0; si < num_convex_sizes; si++) {
237+
size_t nv = convex_sizes[si];
238+
std::vector<double> verts;
239+
std::vector<size_t> poly;
240+
MakeRandomConvex(nv, &verts, &poly, 42 + nv);
241+
242+
size_t iters = quick ? 100 : std::max(static_cast<size_t>(10),
243+
static_cast<size_t>(100000 / nv));
244+
245+
printf("%-10zu", nv);
246+
for (size_t a = 0; a < g_num_algorithms; a++) {
247+
BenchResult r = RunBenchmark(g_algorithms[a].func, poly, verts, iters);
248+
if (r.valid) {
249+
printf(" %10.2f ", r.us_per_call);
250+
} else {
251+
printf(" %10s ", "INVALID");
252+
}
253+
}
254+
printf("\n");
255+
}
256+
257+
// ---- Star-shaped concave polygons ----
258+
printf("\nStar-shaped concave polygons (time in microseconds per call):\n");
259+
printf("(N = total vertices = 2 * star_points)\n\n");
260+
printf("%-10s", "N");
261+
for (size_t a = 0; a < g_num_algorithms; a++) {
262+
printf(" %12s", g_algorithms[a].name);
263+
}
264+
printf("\n");
265+
PrintSeparator(10 + g_num_algorithms * 14);
266+
267+
for (size_t si = 0; si < num_star_sizes; si++) {
268+
size_t np = star_points[si];
269+
size_t nv = np * 2;
270+
std::vector<double> verts;
271+
std::vector<size_t> poly;
272+
MakeStarPolygon(np, &verts, &poly);
273+
274+
size_t iters = quick ? 100 : std::max(static_cast<size_t>(10),
275+
static_cast<size_t>(100000 / nv));
276+
277+
printf("%-10zu", nv);
278+
for (size_t a = 0; a < g_num_algorithms; a++) {
279+
BenchResult r = RunBenchmark(g_algorithms[a].func, poly, verts, iters);
280+
if (r.valid) {
281+
printf(" %10.2f ", r.us_per_call);
282+
} else {
283+
printf(" %10s ", "INVALID");
284+
}
285+
}
286+
printf("\n");
287+
}
288+
289+
printf("\nDone.\n");
290+
return 0;
291+
}

0 commit comments

Comments
 (0)