Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
geom_algorithms_test_triangulation_hulls_delaunay.cc
Go to the documentation of this file.
1#include "geom_algorithms_test_common.h"
2#include <random>
3#include <cmath>
4
5TEST_F(GeomAlgorithmsTest, TriangulateTriangle)
6{
7 Polygon p;
8 p.add_vertex(Point(0, 0));
9 p.add_vertex(Point(4, 0));
10 p.add_vertex(Point(2, 3));
11 p.close();
12
13 CuttingEarsTriangulation triangulator;
14 auto triangles = triangulator(p);
15
16 EXPECT_EQ(triangles.size(), 1u);
17}
18
19
20TEST_F(GeomAlgorithmsTest, TriangulateSquare)
21{
22 Polygon p;
23 p.add_vertex(Point(0, 0));
24 p.add_vertex(Point(4, 0));
25 p.add_vertex(Point(4, 4));
26 p.add_vertex(Point(0, 4));
27 p.close();
28
29 CuttingEarsTriangulation triangulator;
30 auto triangles = triangulator(p);
31
32 EXPECT_EQ(triangles.size(), 2u);
33}
34
35
36TEST_F(GeomAlgorithmsTest, TriangulateSquareClockwise)
37{
38 Polygon p;
39 p.add_vertex(Point(0, 0));
40 p.add_vertex(Point(0, 4));
41 p.add_vertex(Point(4, 4));
42 p.add_vertex(Point(4, 0));
43 p.close();
44
45 CuttingEarsTriangulation triangulator;
46 auto triangles = triangulator(p);
47
48 EXPECT_EQ(triangles.size(), 2u);
49}
50
51
52TEST_F(GeomAlgorithmsTest, TriangulatePentagon)
53{
54 Polygon p;
55 p.add_vertex(Point(2, 0));
56 p.add_vertex(Point(4, 1.5));
57 p.add_vertex(Point(3, 4));
58 p.add_vertex(Point(1, 4));
59 p.add_vertex(Point(0, 1.5));
60 p.close();
61
62 CuttingEarsTriangulation triangulator;
63 auto triangles = triangulator(p);
64
65 EXPECT_EQ(triangles.size(), 3u);
66}
67
68
69TEST_F(GeomAlgorithmsTest, TriangulateOpenPolygonThrows)
70{
71 Polygon p;
72 p.add_vertex(Point(0, 0));
73 p.add_vertex(Point(4, 0));
74 p.add_vertex(Point(2, 3));
75 // intentionally open
76
77 CuttingEarsTriangulation triangulator;
78 EXPECT_THROW((void) triangulator(p), std::domain_error);
79}
80
81
82TEST_F(GeomAlgorithmsTest, TriangulateDegenerateCollinearPolygonThrows)
83{
84 // Degenerate (collinear) polygon should throw - either at close() time
85 // if vertices are reduced, or at triangulation time for zero area
86 EXPECT_THROW(
87 {
88 Polygon p;
89 p.add_vertex(Point(0, 0));
90 p.add_vertex(Point(1, 0));
91 p.add_vertex(Point(2, 0));
92 p.close();
93 CuttingEarsTriangulation triangulator;
94 (void) triangulator(p);
95 },
96 std::domain_error);
97}
98
99
100TEST_F(GeomAlgorithmsTest, TriangulateSelfIntersectingPolygonRejectedByPolygonValidation)
101{
102 Polygon p;
103 p.add_vertex(Point(0, 0));
104 p.add_vertex(Point(2, 0));
105 p.add_vertex(Point(0, 2));
106 p.add_vertex(Point(2, 2));
107
108 // Closing this polyline would create a self-intersection.
109 EXPECT_THROW((void) p.close(), std::domain_error);
110}
111
112
113// Convex hull tests
114TEST_F(GeomAlgorithmsTest, QuickHullTriangle)
115{
116 DynList<Point> points;
117 points.append(Point(0, 0));
118 points.append(Point(6, 0));
119 points.append(Point(3, 5));
120
121 QuickHull qh;
122 Polygon hull = qh(points);
123
124 EXPECT_EQ(hull.size(), 3u);
125}
126
127
128TEST_F(GeomAlgorithmsTest, QuickHullSquare)
129{
130 DynList<Point> points;
131 points.append(Point(0, 0));
132 points.append(Point(5, 0));
133 points.append(Point(5, 5));
134 points.append(Point(0, 5));
135
136 QuickHull qh;
137 Polygon hull = qh(points);
138
139 EXPECT_EQ(hull.size(), 4u);
140}
141
142
143TEST_F(GeomAlgorithmsTest, QuickHullWithInterior)
144{
145 DynList<Point> points;
146 points.append(Point(0, 0));
147 points.append(Point(10, 0));
148 points.append(Point(10, 10));
149 points.append(Point(0, 10));
150 points.append(Point(5, 5)); // Interior
151
152 QuickHull qh;
153 Polygon hull = qh(points);
154
155 EXPECT_EQ(hull.size(), 4u);
156}
157
158
159TEST_F(GeomAlgorithmsTest, GiftWrappingSquare)
160{
161 DynList<Point> points;
162 points.append(Point(0, 0));
163 points.append(Point(4, 0));
164 points.append(Point(4, 4));
165 points.append(Point(0, 4));
166
167 GiftWrappingConvexHull gw;
168 Polygon hull = gw(points);
169
170 EXPECT_EQ(hull.size(), 4u);
171}
172
173
174TEST_F(GeomAlgorithmsTest, BruteForceHullTriangle)
175{
176 DynList<Point> points;
177 points.append(Point(0, 0));
178 points.append(Point(4, 0));
179 points.append(Point(2, 3));
180
181 BruteForceConvexHull bf;
182 Polygon hull = bf(points);
183
184 EXPECT_EQ(hull.size(), 3u);
185}
186
187
188TEST_F(GeomAlgorithmsTest, ThreePointsHull)
189{
190 DynList<Point> points;
191 points.append(Point(0, 0));
192 points.append(Point(2, 0));
193 points.append(Point(1, 2));
194
195 QuickHull qh;
196 Polygon hull = qh(points);
197
198 EXPECT_EQ(hull.size(), 3u);
199}
200
201
202TEST_F(GeomAlgorithmsTest, LegacyHullsEmptyInput)
203{
204 DynList<Point> points;
205
206 QuickHull qh;
207 GiftWrappingConvexHull gw;
208 BruteForceConvexHull bf;
209
210 EXPECT_EQ(qh(points).size(), 0u);
211 EXPECT_EQ(gw(points).size(), 0u);
212 EXPECT_EQ(bf(points).size(), 0u);
213}
214
215
236
237
238TEST_F(GeomAlgorithmsTest, LegacyHullsAllDuplicatePoints)
239{
240 DynList<Point> points;
241 points.append(Point(3, 3));
242 points.append(Point(3, 3));
243 points.append(Point(3, 3));
244
245 QuickHull qh;
246 GiftWrappingConvexHull gw;
247 BruteForceConvexHull bf;
248
249 EXPECT_EQ(qh(points).size(), 1u);
250 EXPECT_EQ(gw(points).size(), 1u);
251 EXPECT_EQ(bf(points).size(), 1u);
252}
253
254
255TEST_F(GeomAlgorithmsTest, AndrewMonotonicChainSquareWithInteriorAndDuplicates)
256{
257 DynList<Point> points;
258 points.append(Point(0, 0));
259 points.append(Point(5, 0));
260 points.append(Point(5, 5));
261 points.append(Point(0, 5));
262 points.append(Point(2, 2)); // Interior
263 points.append(Point(5, 5)); // Duplicate hull point
264 points.append(Point(2, 2)); // Duplicate interior point
265
266 AndrewMonotonicChainConvexHull andrew;
267 Polygon hull = andrew(points);
268
269 EXPECT_EQ(hull.size(), 4u);
270 EXPECT_TRUE(polygon_contains_vertex(hull, Point(0, 0)));
271 EXPECT_TRUE(polygon_contains_vertex(hull, Point(5, 0)));
272 EXPECT_TRUE(polygon_contains_vertex(hull, Point(5, 5)));
273 EXPECT_TRUE(polygon_contains_vertex(hull, Point(0, 5)));
274 EXPECT_FALSE(polygon_contains_vertex(hull, Point(2, 2)));
275}
276
277
278TEST_F(GeomAlgorithmsTest, AndrewMonotonicChainCollinearKeepsEndpoints)
279{
280 DynList<Point> points;
281 points.append(Point(3, 0));
282 points.append(Point(1, 0));
283 points.append(Point(4, 0));
284 points.append(Point(2, 0));
285 points.append(Point(0, 0));
286 points.append(Point(4, 0)); // Duplicate
287
288 AndrewMonotonicChainConvexHull andrew;
289 Polygon hull = andrew(points);
290
291 Aleph::TestVisual::SvgScene scene;
292 for (DynList<Point>::Iterator it(points); it.has_curr(); it.next_ne())
293 scene.points.append(it.get_curr());
294 scene.polygons.append(hull);
295 Aleph::TestVisual::add_polygon_vertices(scene, hull, true);
296 (void) Aleph::TestVisual::emit_case_svg(
297 "case_andrew_collinear_endpoints", scene,
298 "Andrew monotonic chain / collinear input");
299
300 // Degenerate 2-point hull cannot be closed (requires >= 3 vertices)
301 EXPECT_EQ(hull.size(), 2u);
302 EXPECT_FALSE(hull.is_closed());
303 EXPECT_TRUE(polygon_contains_vertex(hull, Point(0, 0)));
304 EXPECT_TRUE(polygon_contains_vertex(hull, Point(4, 0)));
305 EXPECT_FALSE(polygon_contains_vertex(hull, Point(2, 0)));
306}
307
308
309TEST_F(GeomAlgorithmsTest, GrahamScanSquareWithInteriorAndDuplicates)
310{
311 DynList<Point> points;
312 points.append(Point(0, 0));
313 points.append(Point(5, 0));
314 points.append(Point(5, 5));
315 points.append(Point(0, 5));
316 points.append(Point(2, 2)); // Interior
317 points.append(Point(0, 0)); // Duplicate hull point
318 points.append(Point(2, 2)); // Duplicate interior point
319
320 GrahamScanConvexHull graham;
321 Polygon hull = graham(points);
322
323 EXPECT_EQ(hull.size(), 4u);
324 EXPECT_TRUE(polygon_contains_vertex(hull, Point(0, 0)));
325 EXPECT_TRUE(polygon_contains_vertex(hull, Point(5, 0)));
326 EXPECT_TRUE(polygon_contains_vertex(hull, Point(5, 5)));
327 EXPECT_TRUE(polygon_contains_vertex(hull, Point(0, 5)));
328 EXPECT_FALSE(polygon_contains_vertex(hull, Point(2, 2)));
329}
330
331
332TEST_F(GeomAlgorithmsTest, GrahamScanCollinearKeepsEndpoints)
333{
334 DynList<Point> points;
335 points.append(Point(1, 1));
336 points.append(Point(2, 2));
337 points.append(Point(3, 3));
338 points.append(Point(4, 4));
339 points.append(Point(0, 0));
340 points.append(Point(4, 4)); // Duplicate
341
342 GrahamScanConvexHull graham;
343 Polygon hull = graham(points);
344
345 Aleph::TestVisual::SvgScene scene;
346 for (DynList<Point>::Iterator it(points); it.has_curr(); it.next_ne())
347 scene.points.append(it.get_curr());
348 scene.polygons.append(hull);
349 Aleph::TestVisual::add_polygon_vertices(scene, hull, true);
350 (void) Aleph::TestVisual::emit_case_svg(
351 "case_graham_collinear_endpoints", scene,
352 "Graham scan / collinear input");
353
354 // Degenerate 2-point hull cannot be closed (requires >= 3 vertices)
355 EXPECT_EQ(hull.size(), 2u);
356 EXPECT_FALSE(hull.is_closed());
357 EXPECT_TRUE(polygon_contains_vertex(hull, Point(0, 0)));
358 EXPECT_TRUE(polygon_contains_vertex(hull, Point(4, 4)));
359 EXPECT_FALSE(polygon_contains_vertex(hull, Point(2, 2)));
360}
361
362
363TEST_F(GeomAlgorithmsTest, ClosestPairTwoPoints)
364{
365 DynList<Point> points;
366 points.append(Point(1, 2));
367 points.append(Point(4, 6));
368
369 ClosestPairDivideAndConquer cp;
370 ClosestPairDivideAndConquer::Result res = cp(points);
371
372 EXPECT_EQ(res.distance_squared, 25);
373 EXPECT_TRUE(matches_unordered_pair(res.first, res.second,
374 Point(1, 2), Point(4, 6)));
375}
376
377
378TEST_F(GeomAlgorithmsTest, ClosestPairUniqueMinimum)
379{
380 DynList<Point> points;
381 points.append(Point(0, 0));
382 points.append(Point(10, 10));
383 points.append(Point(2, 1));
384 points.append(Point(6, 6));
385 points.append(Point(3, 5));
386
387 ClosestPairDivideAndConquer cp;
388 ClosestPairDivideAndConquer::Result res = cp(points);
389
390 EXPECT_EQ(res.distance_squared, 5);
391 EXPECT_TRUE(matches_unordered_pair(res.first, res.second,
392 Point(0, 0), Point(2, 1)));
393}
394
395
396TEST_F(GeomAlgorithmsTest, ClosestPairDuplicatePointsDistanceZero)
397{
398 DynList<Point> points;
399 points.append(Point(8, 1));
400 points.append(Point(5, 5));
401 points.append(Point(2, 9));
402 points.append(Point(5, 5));
403
404 ClosestPairDivideAndConquer cp;
405 ClosestPairDivideAndConquer::Result res = cp(points);
406
407 Aleph::TestVisual::SvgScene scene;
408 for (DynList<Point>::Iterator it(points); it.has_curr(); it.next_ne())
409 scene.points.append(it.get_curr());
410 scene.segments.append(Segment(res.first, res.second));
411 scene.highlighted_points.append(res.first);
412 scene.highlighted_points.append(res.second);
413 (void) Aleph::TestVisual::emit_case_svg(
414 "case_closest_pair_duplicate_zero", scene,
415 "Closest pair / duplicate points");
416
417 EXPECT_EQ(res.distance_squared, 0);
418 EXPECT_EQ(res.first, res.second);
419 EXPECT_EQ(res.first, Point(5, 5));
420}
421
422
423TEST_F(GeomAlgorithmsTest, ClosestPairCollinear)
424{
425 DynList<Point> points;
426 points.append(Point(0, 0));
427 points.append(Point(5, 0));
428 points.append(Point(2, 0));
429 points.append(Point(9, 0));
430
431 ClosestPairDivideAndConquer cp;
432 ClosestPairDivideAndConquer::Result res = cp(points);
433
434 EXPECT_EQ(res.distance_squared, 4);
435 EXPECT_TRUE(matches_unordered_pair(res.first, res.second,
436 Point(0, 0), Point(2, 0)));
437
438 Segment s = cp.closest_segment(points);
439 EXPECT_TRUE(matches_unordered_pair(s.get_src_point(), s.get_tgt_point(),
440 Point(0, 0), Point(2, 0)));
441}
442
443
444TEST_F(GeomAlgorithmsTest, ClosestPairRequiresAtLeastTwoPoints)
445{
446 DynList<Point> points;
447 points.append(Point(1, 1));
448
449 ClosestPairDivideAndConquer cp;
450 EXPECT_THROW((void) cp(points), std::domain_error);
451}
452
453
454TEST_F(GeomAlgorithmsTest, RotatingCalipersSquare)
455{
456 Polygon square;
457 square.add_vertex(Point(0, 0));
458 square.add_vertex(Point(4, 0));
459 square.add_vertex(Point(4, 4));
460 square.add_vertex(Point(0, 4));
461 square.close();
462
463 RotatingCalipersConvexPolygon calipers;
464 auto d = calipers.diameter(square);
465 EXPECT_EQ(d.distance_squared, 32);
466 EXPECT_TRUE(matches_unordered_pair(d.first, d.second,
467 Point(0, 0), Point(4, 4)) or
468 matches_unordered_pair(d.first, d.second,
469 Point(4, 0), Point(0, 4)));
470}
471
472
473TEST_F(GeomAlgorithmsTest, RotatingCalipersSquareMinimumWidth)
474{
475 Polygon square;
476 square.add_vertex(Point(0, 0));
477 square.add_vertex(Point(4, 0));
478 square.add_vertex(Point(4, 4));
479 square.add_vertex(Point(0, 4));
480 square.close();
481
482 RotatingCalipersConvexPolygon calipers;
483 auto w = calipers.minimum_width(square);
484 EXPECT_EQ(w.width_squared, 16);
485}
486
487
488TEST_F(GeomAlgorithmsTest, RotatingCalipersRectangle)
489{
490 Polygon rect;
491 rect.add_vertex(Point(0, 0));
492 rect.add_vertex(Point(5, 0));
493 rect.add_vertex(Point(5, 2));
494 rect.add_vertex(Point(0, 2));
495 rect.close();
496
497 RotatingCalipersConvexPolygon calipers;
498 auto d = calipers.diameter(rect);
499 EXPECT_EQ(d.distance_squared, 29);
500
501 auto w = calipers.minimum_width(rect);
502 EXPECT_EQ(w.width_squared, 4);
503}
504
505
506TEST_F(GeomAlgorithmsTest, RotatingCalipersTwoPointDegenerate)
507{
508 // A polygon with only 2 vertices cannot be closed (requires >= 3)
509 EXPECT_THROW(
510 {
511 Polygon p;
512 p.add_vertex(Point(1, 1));
513 p.add_vertex(Point(4, 5));
514 p.close();
515 },
516 std::domain_error);
517}
518
519
520TEST_F(GeomAlgorithmsTest, RotatingCalipersNonConvexThrows)
521{
522 Polygon concave;
523 concave.add_vertex(Point(0, 0));
524 concave.add_vertex(Point(4, 0));
525 concave.add_vertex(Point(2, 1));
526 concave.add_vertex(Point(4, 4));
527 concave.add_vertex(Point(0, 4));
528 concave.close();
529
530 RotatingCalipersConvexPolygon calipers;
531 EXPECT_THROW((void) calipers.diameter(concave), std::domain_error);
532 EXPECT_THROW((void) calipers.minimum_width(concave), std::domain_error);
533}
534
535
536TEST_F(GeomAlgorithmsTest, RotatingCalipersOpenPolygonThrows)
537{
538 Polygon open;
539 open.add_vertex(Point(0, 0));
540 open.add_vertex(Point(4, 0));
541 open.add_vertex(Point(4, 4));
542 open.add_vertex(Point(0, 4));
543
544 RotatingCalipersConvexPolygon calipers;
545 EXPECT_THROW((void) calipers.diameter(open), std::domain_error);
546 EXPECT_THROW((void) calipers.minimum_width(open), std::domain_error);
547}
548
549
550TEST_F(GeomAlgorithmsTest, PointInPolygonConvexClassification)
551{
552 Polygon square;
553 square.add_vertex(Point(0, 0));
554 square.add_vertex(Point(4, 0));
555 square.add_vertex(Point(4, 4));
556 square.add_vertex(Point(0, 4));
557 square.close();
558
559 PointInPolygonWinding pip;
560 EXPECT_EQ(pip.locate(square, Point(2, 2)),
561 PointInPolygonWinding::Location::Inside);
562 EXPECT_EQ(pip.locate(square, Point(4, 1)),
563 PointInPolygonWinding::Location::Boundary);
564 EXPECT_EQ(pip.locate(square, Point(5, 5)),
565 PointInPolygonWinding::Location::Outside);
566
567 EXPECT_TRUE(pip.contains(square, Point(4, 1)));
568 EXPECT_FALSE(pip.strictly_contains(square, Point(4, 1)));
569 EXPECT_TRUE(pip.strictly_contains(square, Point(2, 2)));
570}
571
572
573TEST_F(GeomAlgorithmsTest, PointInPolygonConcaveClassification)
574{
575 Polygon concave;
576 concave.add_vertex(Point(0, 0));
577 concave.add_vertex(Point(4, 0));
578 concave.add_vertex(Point(4, 4));
579 concave.add_vertex(Point(2, 2));
580 concave.add_vertex(Point(0, 4));
581 concave.close();
582
583 PointInPolygonWinding pip;
584 EXPECT_EQ(pip.locate(concave, Point(1, 1)),
585 PointInPolygonWinding::Location::Inside);
586 EXPECT_EQ(pip.locate(concave, Point(2, 3)),
587 PointInPolygonWinding::Location::Outside);
588 EXPECT_EQ(pip.locate(concave, Point(3, 3)),
589 PointInPolygonWinding::Location::Boundary);
590}
591
592
593TEST_F(GeomAlgorithmsTest, PointInPolygonRequiresClosedPolygon)
594{
595 Polygon open;
596 open.add_vertex(Point(0, 0));
597 open.add_vertex(Point(3, 0));
598 open.add_vertex(Point(0, 3));
599
600 PointInPolygonWinding pip;
601 EXPECT_THROW((void) pip.locate(open, Point(1, 1)), std::domain_error);
602}
603
604
605TEST_F(GeomAlgorithmsTest, ConvexPolygonIntersectionOverlapArea)
606{
607 Polygon a;
608 a.add_vertex(Point(0, 0));
609 a.add_vertex(Point(4, 0));
610 a.add_vertex(Point(4, 4));
611 a.add_vertex(Point(0, 4));
612 a.close();
613
614 Polygon b;
615 b.add_vertex(Point(2, 2));
616 b.add_vertex(Point(6, 2));
617 b.add_vertex(Point(6, 6));
618 b.add_vertex(Point(2, 6));
619 b.close();
620
621 ConvexPolygonIntersectionBasic inter;
622 Polygon r = inter(a, b);
623
624 EXPECT_EQ(r.size(), 4u);
625 EXPECT_TRUE(r.is_closed());
626 EXPECT_TRUE(polygon_contains_vertex(r, Point(2, 2)));
627 EXPECT_TRUE(polygon_contains_vertex(r, Point(4, 2)));
628 EXPECT_TRUE(polygon_contains_vertex(r, Point(4, 4)));
629 EXPECT_TRUE(polygon_contains_vertex(r, Point(2, 4)));
630}
631
632
633TEST_F(GeomAlgorithmsTest, ConvexPolygonIntersectionContained)
634{
635 Polygon outer;
636 outer.add_vertex(Point(0, 0));
637 outer.add_vertex(Point(10, 0));
638 outer.add_vertex(Point(10, 10));
639 outer.add_vertex(Point(0, 10));
640 outer.close();
641
642 Polygon inner;
643 inner.add_vertex(Point(2, 2));
644 inner.add_vertex(Point(4, 2));
645 inner.add_vertex(Point(4, 4));
646 inner.add_vertex(Point(2, 4));
647 inner.close();
648
649 ConvexPolygonIntersectionBasic inter;
650 Polygon r = inter(outer, inner);
651
652 EXPECT_EQ(r.size(), 4u);
653 EXPECT_TRUE(polygon_contains_vertex(r, Point(2, 2)));
654 EXPECT_TRUE(polygon_contains_vertex(r, Point(4, 2)));
655 EXPECT_TRUE(polygon_contains_vertex(r, Point(4, 4)));
656 EXPECT_TRUE(polygon_contains_vertex(r, Point(2, 4)));
657}
658
659
660TEST_F(GeomAlgorithmsTest, ConvexPolygonIntersectionDisjoint)
661{
662 Polygon a;
663 a.add_vertex(Point(0, 0));
664 a.add_vertex(Point(1, 0));
665 a.add_vertex(Point(1, 1));
666 a.add_vertex(Point(0, 1));
667 a.close();
668
669 Polygon b;
670 b.add_vertex(Point(3, 3));
671 b.add_vertex(Point(4, 3));
672 b.add_vertex(Point(4, 4));
673 b.add_vertex(Point(3, 4));
674 b.close();
675
676 ConvexPolygonIntersectionBasic inter;
677 Polygon r = inter(a, b);
678
679 EXPECT_EQ(r.size(), 0u);
680}
681
682
683TEST_F(GeomAlgorithmsTest, ConvexPolygonIntersectionTouchingEdge)
684{
685 Polygon a;
686 a.add_vertex(Point(0, 0));
687 a.add_vertex(Point(2, 0));
688 a.add_vertex(Point(2, 2));
689 a.add_vertex(Point(0, 2));
690 a.close();
691
692 Polygon b;
693 b.add_vertex(Point(2, 0));
694 b.add_vertex(Point(4, 0));
695 b.add_vertex(Point(4, 2));
696 b.add_vertex(Point(2, 2));
697 b.close();
698
699 ConvexPolygonIntersectionBasic inter;
700 Polygon r = inter(a, b);
701
702 Aleph::TestVisual::SvgScene scene;
703 scene.polygons.append(a);
704 scene.polygons.append(b);
705 scene.polygons.append(r);
706 Aleph::TestVisual::add_polygon_vertices(scene, r, true);
707 (void) Aleph::TestVisual::emit_case_svg(
708 "case_convex_polygon_intersection_touching_edge", scene,
709 "Convex intersection / touching edge");
710
711 // Degenerate 2-vertex intersection cannot be closed (requires >= 3 vertices)
712 EXPECT_EQ(r.size(), 2u);
713 EXPECT_FALSE(r.is_closed());
714 EXPECT_TRUE(polygon_contains_vertex(r, Point(2, 0)));
715 EXPECT_TRUE(polygon_contains_vertex(r, Point(2, 2)));
716}
717
718
719TEST_F(GeomAlgorithmsTest, ConvexPolygonIntersectionRequiresConvex)
720{
721 Polygon concave;
722 concave.add_vertex(Point(0, 0));
723 concave.add_vertex(Point(4, 0));
724 concave.add_vertex(Point(2, 1));
725 concave.add_vertex(Point(4, 4));
726 concave.add_vertex(Point(0, 4));
727 concave.close();
728
729 Polygon square;
730 square.add_vertex(Point(0, 0));
731 square.add_vertex(Point(3, 0));
732 square.add_vertex(Point(3, 3));
733 square.add_vertex(Point(0, 3));
734 square.close();
735
736 ConvexPolygonIntersectionBasic inter;
737 EXPECT_THROW((void) inter(concave, square), std::domain_error);
738 EXPECT_THROW((void) inter(square, concave), std::domain_error);
739}
740
741
742TEST_F(GeomAlgorithmsTest, ConvexPolygonIntersectionRequiresClosed)
743{
744 Polygon open;
745 open.add_vertex(Point(0, 0));
746 open.add_vertex(Point(2, 0));
747 open.add_vertex(Point(2, 2));
748
749 Polygon square;
750 square.add_vertex(Point(0, 0));
751 square.add_vertex(Point(3, 0));
752 square.add_vertex(Point(3, 3));
753 square.add_vertex(Point(0, 3));
754 square.close();
755
756 ConvexPolygonIntersectionBasic inter;
757 EXPECT_THROW((void) inter(open, square), std::domain_error);
758 EXPECT_THROW((void) inter(square, open), std::domain_error);
759}
760
761
783
784
806
807
839
840
841TEST_F(GeomAlgorithmsTest, HalfPlaneIntersectionInconsistent)
842{
843 HalfPlaneIntersection hpi;
844 Array<HalfPlaneIntersection::HalfPlane> hs;
845 hs.append(HalfPlaneIntersection::HalfPlane(Point(2, 1), Point(2, 0))); // x >= 2
846 hs.append(HalfPlaneIntersection::HalfPlane(Point(1, 0), Point(1, 1))); // x <= 1
847 hs.append(HalfPlaneIntersection::HalfPlane(Point(0, 0), Point(1, 0))); // y >= 0
848 hs.append(HalfPlaneIntersection::HalfPlane(Point(1, 1), Point(0, 1))); // y <= 1
849
850 Polygon r = hpi(hs);
851
852 Aleph::TestVisual::SvgScene scene;
853 for (size_t i = 0; i < hs.size(); ++i)
854 scene.segments.append(Segment(hs(i).p, hs(i).q));
855 scene.polygons.append(r);
856 (void) Aleph::TestVisual::emit_case_svg(
857 "case_halfplane_inconsistent_empty", scene,
858 "Half-plane intersection / inconsistent constraints");
859
860 EXPECT_EQ(r.size(), 0u);
861}
862
863
875
876
877TEST_F(GeomAlgorithmsTest, DelaunayTriangle)
878{
879 DelaunayTriangulationBowyerWatson delaunay;
880 auto r = delaunay({Point(0, 0), Point(6, 0), Point(2, 4)});
881
882 ASSERT_EQ(r.sites.size(), 3u);
883 ASSERT_EQ(r.triangles.size(), 1u);
884
885 const auto & t = r.triangles(0);
886 EXPECT_EQ(orientation(r.sites(t.i), r.sites(t.j), r.sites(t.k)),
887 Orientation::CCW);
888}
889
890
891TEST_F(GeomAlgorithmsTest, DelaunaySquareProducesTwoTriangles)
892{
893 DelaunayTriangulationBowyerWatson delaunay;
894 auto r = delaunay({Point(0, 0), Point(4, 0), Point(4, 4), Point(0, 4)});
895
896 ASSERT_EQ(r.sites.size(), 4u);
897 ASSERT_EQ(r.triangles.size(), 2u);
898
899 for (size_t i = 0; i < r.triangles.size(); ++i)
900 {
901 const auto & t = r.triangles(i);
902 EXPECT_LT(t.i, r.sites.size());
903 EXPECT_LT(t.j, r.sites.size());
904 EXPECT_LT(t.k, r.sites.size());
905 EXPECT_NE(orientation(r.sites(t.i), r.sites(t.j), r.sites(t.k)),
906 Orientation::COLLINEAR);
907 }
908}
909
910
911TEST_F(GeomAlgorithmsTest, DelaunayRemovesDuplicates)
912{
913 DelaunayTriangulationBowyerWatson delaunay;
914 auto r = delaunay({Point(0, 0), Point(4, 0), Point(4, 4), Point(0, 4),
915 Point(0, 0), Point(4, 4)});
916
917 EXPECT_EQ(r.sites.size(), 4u);
918 EXPECT_EQ(r.triangles.size(), 2u);
919}
920
921
922TEST_F(GeomAlgorithmsTest, DelaunayCollinearReturnsEmpty)
923{
924 DelaunayTriangulationBowyerWatson delaunay;
925 auto r = delaunay({Point(0, 0), Point(2, 0), Point(4, 0), Point(6, 0)});
926
927 EXPECT_EQ(r.sites.size(), 4u);
928 EXPECT_EQ(r.triangles.size(), 0u);
929}
930
931
932TEST_F(GeomAlgorithmsTest, DelaunayCocircularDeterministicAcrossInputOrder)
933{
934 DelaunayTriangulationBowyerWatson delaunay;
935 auto r1 = delaunay({Point(0, 0), Point(1, 0), Point(1, 1), Point(0, 1)});
936
937 DynList<Point> shuffled;
938 shuffled.append(Point(1, 1));
939 shuffled.append(Point(0, 1));
940 shuffled.append(Point(0, 0));
941 shuffled.append(Point(1, 0));
942 auto r2 = delaunay(shuffled);
943
944 Aleph::TestVisual::SvgScene scene;
945 for (size_t i = 0; i < r1.sites.size(); ++i)
946 scene.points.append(r1.sites(i));
947 for (size_t i = 0; i < r1.triangles.size(); ++i)
948 {
949 const auto & t = r1.triangles(i);
950 scene.segments.append(Segment(r1.sites(t.i), r1.sites(t.j)));
951 scene.segments.append(Segment(r1.sites(t.j), r1.sites(t.k)));
952 scene.segments.append(Segment(r1.sites(t.k), r1.sites(t.i)));
953 }
954 (void) Aleph::TestVisual::emit_case_svg(
955 "case_delaunay_cocircular_deterministic", scene,
956 "Delaunay cocircular tie-break");
957
958 ASSERT_EQ(r1.sites.size(), r2.sites.size());
959 ASSERT_EQ(r1.triangles.size(), r2.triangles.size());
960
961 for (size_t i = 0; i < r1.sites.size(); ++i)
962 EXPECT_EQ(r1.sites(i), r2.sites(i));
963
964 const Array<TriKey> t1 = canonical_triangles(r1);
965 const Array<TriKey> t2 = canonical_triangles(r2);
966 ASSERT_EQ(t1.size(), t2.size());
967 for (size_t i = 0; i < t1.size(); ++i)
968 {
969 EXPECT_EQ(t1(i).a, t2(i).a);
970 EXPECT_EQ(t1(i).b, t2(i).b);
971 EXPECT_EQ(t1(i).c, t2(i).c);
972 }
973}
974
975
976TEST_F(GeomAlgorithmsTest, VoronoiFromTriangle)
977{
978 VoronoiDiagramFromDelaunay voronoi;
979 auto r = voronoi({Point(0, 0), Point(6, 0), Point(2, 4)});
980
981 EXPECT_EQ(r.sites.size(), 3u);
982 EXPECT_EQ(r.vertices.size(), 1u);
983 EXPECT_EQ(r.edges.size(), 3u);
984 EXPECT_EQ(r.cells.size(), 3u);
985
986 size_t unbounded = 0;
987 for (size_t i = 0; i < r.edges.size(); ++i)
988 if (r.edges(i).unbounded)
989 {
990 ++unbounded;
991 EXPECT_FALSE(r.edges(i).direction == Point(0, 0));
992 }
993 EXPECT_EQ(unbounded, 3u);
994
995 for (size_t i = 0; i < r.cells.size(); ++i)
996 {
997 EXPECT_FALSE(r.cells(i).bounded);
998 EXPECT_EQ(r.cells(i).vertices.size(), 1u);
999 }
1000}
1001
1002
1003TEST_F(GeomAlgorithmsTest, VoronoiFromQuadrilateralHasOneBoundedEdge)
1004{
1005 VoronoiDiagramFromDelaunay voronoi;
1006 auto r = voronoi({Point(0, 0), Point(5, 0), Point(6, 3), Point(0, 4)});
1007
1008 EXPECT_EQ(r.sites.size(), 4u);
1009 EXPECT_EQ(r.vertices.size(), 2u);
1010 EXPECT_EQ(r.cells.size(), 4u);
1011
1012 size_t bounded = 0;
1013 size_t unbounded = 0;
1014 for (size_t i = 0; i < r.edges.size(); ++i)
1015 if (r.edges(i).unbounded)
1016 ++unbounded;
1017 else
1018 ++bounded;
1019
1020 EXPECT_EQ(bounded, 1u);
1021 EXPECT_EQ(unbounded, 4u);
1022
1023 for (size_t i = 0; i < r.cells.size(); ++i)
1024 EXPECT_FALSE(r.cells(i).bounded);
1025}
1026
1027
1028TEST_F(GeomAlgorithmsTest, VoronoiBoundedEdgesMatchAdjacentTriangleCircumcenters)
1029{
1030 DelaunayTriangulationBowyerWatson delaunay;
1031 auto dt = delaunay({Point(0, 0), Point(5, 0), Point(6, 3), Point(0, 4),
1032 Point(2, 2)});
1033 ASSERT_GE(dt.triangles.size(), 2u);
1034
1035 VoronoiDiagramFromDelaunay voronoi;
1036 auto r = voronoi(dt);
1037
1038 size_t bounded_edges = 0;
1039 for (size_t e = 0; e < r.edges.size(); ++e)
1040 {
1041 const auto & edge = r.edges(e);
1042 if (edge.unbounded)
1043 continue;
1044
1045 ++bounded_edges;
1046
1047 Array<size_t> incident;
1048 incident.reserve(2);
1049 for (size_t t = 0; t < dt.triangles.size(); ++t)
1050 {
1051 const auto & tri = dt.triangles(t);
1052 const bool has_u = tri.i == edge.site_u or tri.j == edge.site_u or
1053 tri.k == edge.site_u;
1054 const bool has_v = tri.i == edge.site_v or tri.j == edge.site_v or
1055 tri.k == edge.site_v;
1056 if (has_u and has_v)
1057 incident.append(t);
1058 }
1059
1060 ASSERT_EQ(incident.size(), 2u);
1061
1062 const auto & t0 = dt.triangles(incident(0));
1063 const auto & t1 = dt.triangles(incident(1));
1064 ASSERT_NE(orientation(dt.sites(t0.i), dt.sites(t0.j), dt.sites(t0.k)),
1065 Orientation::COLLINEAR);
1066 ASSERT_NE(orientation(dt.sites(t1.i), dt.sites(t1.j), dt.sites(t1.k)),
1067 Orientation::COLLINEAR);
1068
1069 const Point c0 = circumcenter_of(dt.sites(t0.i), dt.sites(t0.j), dt.sites(t0.k));
1070 const Point c1 = circumcenter_of(dt.sites(t1.i), dt.sites(t1.j), dt.sites(t1.k));
1071 EXPECT_TRUE(matches_unordered_pair(edge.src, edge.tgt, c0, c1));
1072 }
1073
1074 EXPECT_GT(bounded_edges, 0u);
1075}
1076
1077
1078TEST_F(GeomAlgorithmsTest, VoronoiClippedCellsBoundedAndContainSites)
1079{
1080 VoronoiDiagramFromDelaunay voronoi;
1081 auto r = voronoi({Point(0, 0), Point(5, 0), Point(6, 3), Point(0, 4),
1082 Point(2, 2)});
1083
1084 Polygon box;
1085 box.add_vertex(Point(-10, -10));
1086 box.add_vertex(Point(10, -10));
1087 box.add_vertex(Point(10, 10));
1088 box.add_vertex(Point(-10, 10));
1089 box.close();
1090
1091 Array<Polygon> cells = voronoi.clipped_cells(r, box);
1092 ASSERT_EQ(cells.size(), r.sites.size());
1093
1094 PointInPolygonWinding pip;
1095 for (size_t i = 0; i < cells.size(); ++i)
1096 {
1097 EXPECT_TRUE(cells(i).is_closed());
1098 EXPECT_GE(cells(i).size(), 3u);
1099 EXPECT_TRUE(pip.contains(cells(i), r.sites(i)));
1100 }
1101}
1102
1103
1104TEST_F(GeomAlgorithmsTest, VoronoiClippedCellsBoundedAndContainSitesClockwiseClip)
1105{
1106 VoronoiDiagramFromDelaunay voronoi;
1107 auto r = voronoi({Point(0, 0), Point(5, 0), Point(6, 3), Point(0, 4),
1108 Point(2, 2)});
1109
1110 Polygon box_cw;
1111 box_cw.add_vertex(Point(-10, -10));
1112 box_cw.add_vertex(Point(-10, 10));
1113 box_cw.add_vertex(Point(10, 10));
1114 box_cw.add_vertex(Point(10, -10));
1115 box_cw.close();
1116
1117 Array<Polygon> cells = voronoi.clipped_cells(r, box_cw);
1118 ASSERT_EQ(cells.size(), r.sites.size());
1119
1120 PointInPolygonWinding pip;
1121 for (size_t i = 0; i < cells.size(); ++i)
1122 {
1123 EXPECT_TRUE(cells(i).is_closed());
1124 EXPECT_GE(cells(i).size(), 3u);
1125 EXPECT_TRUE(pip.contains(cells(i), r.sites(i)));
1126 }
1127}
1128
1129
1130TEST_F(GeomAlgorithmsTest, VoronoiClippedCellsRequiresConvexClip)
1131{
1132 VoronoiDiagramFromDelaunay voronoi;
1133 auto r = voronoi({Point(0, 0), Point(5, 0), Point(6, 3), Point(0, 4),
1134 Point(2, 2)});
1135
1136 Polygon concave;
1137 concave.add_vertex(Point(0, 0));
1138 concave.add_vertex(Point(6, 0));
1139 concave.add_vertex(Point(3, 2));
1140 concave.add_vertex(Point(6, 6));
1141 concave.add_vertex(Point(0, 6));
1142 concave.close();
1143
1144 EXPECT_THROW((void) voronoi.clipped_cells(r, concave), std::domain_error);
1145}
1146
1147
1148TEST_F(GeomAlgorithmsTest, VoronoiClippedCellsIndexedExposeSiteAndIndex)
1149{
1150 VoronoiDiagramFromDelaunay voronoi;
1151 auto r = voronoi({Point(0, 0), Point(5, 0), Point(6, 3), Point(0, 4),
1152 Point(2, 2)});
1153
1154 Polygon box;
1155 box.add_vertex(Point(-10, -10));
1156 box.add_vertex(Point(10, -10));
1157 box.add_vertex(Point(10, 10));
1158 box.add_vertex(Point(-10, 10));
1159 box.close();
1160
1161 Array<VoronoiDiagramFromDelaunay::ClippedCell> cells =
1162 voronoi.clipped_cells_indexed(r, box);
1163 ASSERT_EQ(cells.size(), r.sites.size());
1164
1165 PointInPolygonWinding pip;
1166 for (size_t i = 0; i < cells.size(); ++i)
1167 {
1168 EXPECT_EQ(cells(i).site_index, i);
1169 EXPECT_EQ(cells(i).site, r.sites(i));
1170 EXPECT_TRUE(cells(i).polygon.is_closed());
1171 EXPECT_GE(cells(i).polygon.size(), 3u);
1172 EXPECT_TRUE(pip.contains(cells(i).polygon, cells(i).site));
1173 }
1174}
1175
1176
1177TEST_F(GeomAlgorithmsTest, TriangulateHexagon)
1178{
1179 Polygon p;
1180 p.add_vertex(Point(1, 0));
1181 p.add_vertex(Point(2, 0));
1182 p.add_vertex(Point(3, 1));
1183 p.add_vertex(Point(2, 2));
1184 p.add_vertex(Point(1, 2));
1185 p.add_vertex(Point(0, 1));
1186 p.close();
1187
1188 CuttingEarsTriangulation triangulator;
1189 auto triangles = triangulator(p);
1190
1191 EXPECT_EQ(triangles.size(), 4u);
1192}
1193
1194
1195// ============================================================================
1196// Phase 4 — Performance & Robustness Tests
1197// ============================================================================
1198
1199// ---------- toggle_edge O(log n) via DynSetTree (Bowyer-Watson) ----------
1200
1201TEST_F(GeomAlgorithmsTest, DelaunayStressToggleEdgePerformance)
1202{
1203 // A large-ish random point set exercises the DynSetTree-based toggle_edge
1204 // heavily: each insertion creates a cavity whose boundary edges are
1205 // toggled. We verify correctness of the result, which implies
1206 // toggle_edge worked at every step.
1207 DynList<Point> points;
1208 const int N = 200;
1209 for (int i = 0; i < N; ++i)
1210 for (int j = 0; j < 3; ++j)
1211 points.append(Point(i * 7 + j * 3, j * 11 + i * 5));
1212
1213 DelaunayTriangulationBowyerWatson delaunay;
1214 auto r = delaunay(points);
1215
1216 EXPECT_GE(r.sites.size(), 3u);
1217 EXPECT_GE(r.triangles.size(), 1u);
1218
1219 // Delaunay property: no site lies strictly inside any triangle's circumcircle.
1220 for (size_t t = 0; t < r.triangles.size(); ++t)
1221 {
1222 const auto & tri = r.triangles(t);
1223 const Point cc = circumcenter_of(r.sites(tri.i), r.sites(tri.j),
1224 r.sites(tri.k));
1225 const Geom_Number cr2 = cc.distance_squared_to(r.sites(tri.i));
1226 for (size_t s = 0; s < r.sites.size(); ++s)
1227 {
1228 if (s == tri.i or s == tri.j or s == tri.k)
1229 continue;
1230 // No site should be strictly closer to circumcenter than the radius.
1231 EXPECT_GE(cc.distance_squared_to(r.sites(s)), cr2);
1232 }
1233 }
1234}
1235
1236
1237TEST_F(GeomAlgorithmsTest, DelaunayStressGridInput)
1238{
1239 // Grid input creates many cocircular quadruples, stressing the
1240 // deterministic tie-breaking and toggle_edge toggling.
1241 DynList<Point> points;
1242 for (int x = 0; x < 10; ++x)
1243 for (int y = 0; y < 10; ++y)
1244 points.append(Point(x, y));
1245
1246 DelaunayTriangulationBowyerWatson delaunay;
1247 auto r = delaunay(points);
1248
1249 EXPECT_EQ(r.sites.size(), 100u);
1250 // A grid of n=m*m points always yields 2*(m-1)^2 triangles.
1251 EXPECT_EQ(r.triangles.size(), 2u * 9u * 9u);
1252
1253 // All triangles are non-degenerate.
1254 for (size_t t = 0; t < r.triangles.size(); ++t)
1255 {
1256 const auto & tri = r.triangles(t);
1257 EXPECT_NE(orientation(r.sites(tri.i), r.sites(tri.j), r.sites(tri.k)),
1258 Orientation::COLLINEAR);
1259 }
1260}
1261
1262
1263// ---------- Voronoi: incidence index correctness ----------
1264
1265TEST_F(GeomAlgorithmsTest, VoronoiIncidenceIndexMatchesCircumcenters)
1266{
1267 // Each Voronoi cell's vertices should be exactly the circumcenters of the
1268 // Delaunay triangles incident to that site. This verifies the prebuilt
1269 // incidence index produces correct cells.
1270 DelaunayTriangulationBowyerWatson delaunay;
1271 auto dt = delaunay({Point(0, 0), Point(5, 0), Point(6, 3), Point(0, 4),
1272 Point(2, 2), Point(4, 5)});
1273 ASSERT_GE(dt.triangles.size(), 3u);
1274
1275 VoronoiDiagramFromDelaunay voronoi;
1276 auto r = voronoi(dt);
1277 ASSERT_EQ(r.cells.size(), r.sites.size());
1278
1279 for (size_t s = 0; s < r.cells.size(); ++s)
1280 {
1281 // Collect circumcenters of triangles incident to site s.
1282 Array<Point> expected;
1283 for (size_t t = 0; t < dt.triangles.size(); ++t)
1284 {
1285 const auto & tri = dt.triangles(t);
1286 if (tri.i == s or tri.j == s or tri.k == s)
1287 expected.append(circumcenter_of(dt.sites(tri.i),
1288 dt.sites(tri.j),
1289 dt.sites(tri.k)));
1290 }
1291
1292 // Every cell vertex must appear among the expected circumcenters.
1293 const auto & cell_verts = r.cells(s).vertices;
1294 EXPECT_EQ(cell_verts.size(), expected.size())
1295 << "Mismatch for site " << s;
1296
1297 for (size_t v = 0; v < cell_verts.size(); ++v)
1298 {
1299 bool found = false;
1300 for (size_t e = 0; e < expected.size(); ++e)
1301 if (cell_verts(v) == expected(e))
1302 {
1303 found = true;
1304 break;
1305 }
1306 EXPECT_TRUE(found) << "Cell " << s << " has unexpected vertex";
1307 }
1308 }
1309}
1310
1311
1312TEST_F(GeomAlgorithmsTest, VoronoiIncidenceIndexStress)
1313{
1314 // Larger set: the O(T) incidence build must match brute-force.
1315 DynList<Point> points;
1316 for (int i = 0; i < 8; ++i)
1317 for (int j = 0; j < 8; ++j)
1318 points.append(Point(i * 3 + (j % 2), j * 3 + (i % 2)));
1319
1320 DelaunayTriangulationBowyerWatson delaunay;
1321 auto dt = delaunay(points);
1322
1323 VoronoiDiagramFromDelaunay voronoi;
1324 auto r = voronoi(dt);
1325 ASSERT_EQ(r.cells.size(), r.sites.size());
1326
1327 // Bounded cells exist only for interior sites.
1328 size_t bounded_count = 0;
1329 for (size_t s = 0; s < r.cells.size(); ++s)
1330 {
1331 if (r.cells(s).bounded)
1332 ++bounded_count;
1333
1334 // Every cell must have at least one vertex.
1335 EXPECT_GE(r.cells(s).vertices.size(), 1u);
1336 }
1337 EXPECT_GT(bounded_count, 0u);
1338}
1339
1340
1341// ---------- CuttingEarsTriangulation: automatic CCW normalization ----------
1342
1343TEST_F(GeomAlgorithmsTest, TriangulatePentagonClockwise)
1344{
1345 // CW pentagon — must be normalized to CCW internally.
1346 Polygon p;
1347 p.add_vertex(Point(0, 1.5));
1348 p.add_vertex(Point(1, 4));
1349 p.add_vertex(Point(3, 4));
1350 p.add_vertex(Point(4, 1.5));
1351 p.add_vertex(Point(2, 0));
1352 p.close();
1353
1354 CuttingEarsTriangulation triangulator;
1355 auto triangles = triangulator(p);
1356
1357 EXPECT_EQ(triangles.size(), 3u);
1358}
1359
1360
1361TEST_F(GeomAlgorithmsTest, TriangulateHexagonClockwise)
1362{
1363 // CW hexagon
1364 Polygon p;
1365 p.add_vertex(Point(0, 1));
1366 p.add_vertex(Point(1, 2));
1367 p.add_vertex(Point(2, 2));
1368 p.add_vertex(Point(3, 1));
1369 p.add_vertex(Point(2, 0));
1370 p.add_vertex(Point(1, 0));
1371 p.close();
1372
1373 CuttingEarsTriangulation triangulator;
1374 auto triangles = triangulator(p);
1375
1376 EXPECT_EQ(triangles.size(), 4u);
1377}
1378
1379
1380TEST_F(GeomAlgorithmsTest, TriangulateTriangleClockwise)
1381{
1382 // Minimal CW input: 3 vertices.
1383 Polygon p;
1384 p.add_vertex(Point(0, 0));
1385 p.add_vertex(Point(2, 3));
1386 p.add_vertex(Point(4, 0));
1387 p.close();
1388
1389 CuttingEarsTriangulation triangulator;
1390 auto triangles = triangulator(p);
1391
1392 EXPECT_EQ(triangles.size(), 1u);
1393}
1394
1395
1396TEST_F(GeomAlgorithmsTest, TriangulateLShapeClockwise)
1397{
1398 // L-shaped concave polygon in CW order.
1399 Polygon p;
1400 p.add_vertex(Point(0, 0));
1401 p.add_vertex(Point(0, 4));
1402 p.add_vertex(Point(2, 4));
1403 p.add_vertex(Point(2, 2));
1404 p.add_vertex(Point(4, 2));
1405 p.add_vertex(Point(4, 0));
1406 p.close();
1407
1408 CuttingEarsTriangulation triangulator;
1409 auto triangles = triangulator(p);
1410
1411 // 6-vertex polygon yields 4 triangles.
1412 EXPECT_EQ(triangles.size(), 4u);
1413}
1414
1415
1416// ---------- HalfPlaneIntersection: CW polygon handling ----------
1417
1418TEST_F(GeomAlgorithmsTest, HalfPlaneFromConvexTriangleCW)
1419{
1420 // CW triangle — from_convex_polygon must flip edges so the interior is
1421 // on the left side of each half-plane.
1422 Polygon tri_cw;
1423 tri_cw.add_vertex(Point(0, 0));
1424 tri_cw.add_vertex(Point(0, 3));
1425 tri_cw.add_vertex(Point(4, 0));
1426 tri_cw.close();
1427
1428 HalfPlaneIntersection hpi;
1429 Array<HalfPlaneIntersection::HalfPlane> hs =
1430 HalfPlaneIntersection::from_convex_polygon(tri_cw);
1431
1432 Polygon r = hpi(hs);
1433 EXPECT_EQ(r.size(), 3u);
1434 EXPECT_TRUE(r.is_closed());
1435 EXPECT_TRUE(polygon_contains_vertex(r, Point(0, 0)));
1436 EXPECT_TRUE(polygon_contains_vertex(r, Point(0, 3)));
1437 EXPECT_TRUE(polygon_contains_vertex(r, Point(4, 0)));
1438}
1439
1440
1441TEST_F(GeomAlgorithmsTest, HalfPlaneFromConvexPentagonCW)
1442{
1443 // CW convex pentagon
1444 Polygon penta_cw;
1445 penta_cw.add_vertex(Point(2, 0));
1446 penta_cw.add_vertex(Point(0, 1.5));
1447 penta_cw.add_vertex(Point(1, 4));
1448 penta_cw.add_vertex(Point(3, 4));
1449 penta_cw.add_vertex(Point(4, 1.5));
1450 penta_cw.close();
1451
1452 HalfPlaneIntersection hpi;
1453 Array<HalfPlaneIntersection::HalfPlane> hs =
1454 HalfPlaneIntersection::from_convex_polygon(penta_cw);
1455
1456 Polygon r = hpi(hs);
1457 EXPECT_EQ(r.size(), 5u);
1458 EXPECT_TRUE(r.is_closed());
1459}
1460
1461
1462TEST_F(GeomAlgorithmsTest, HalfPlaneFromConvexPolygonDegenerateThrows)
1463{
1464 // Degenerate polygon (zero area) should throw - either at close() time
1465 // if vertices are reduced, or at algorithm time for zero area
1466 EXPECT_THROW(
1467 {
1468 Polygon degen;
1469 degen.add_vertex(Point(0, 0));
1470 degen.add_vertex(Point(1, 0));
1471 degen.add_vertex(Point(2, 0));
1472 degen.close();
1473 (void) HalfPlaneIntersection::from_convex_polygon(degen);
1474 },
1475 std::domain_error);
1476}
1477
1478
1479// ---------- Edge cases: Delaunay ----------
1480
1481TEST_F(GeomAlgorithmsTest, DelaunayEmptyInput)
1482{
1483 DelaunayTriangulationBowyerWatson delaunay;
1484 DynList<Point> empty;
1485 auto r = delaunay(empty);
1486
1487 EXPECT_EQ(r.sites.size(), 0u);
1488 EXPECT_EQ(r.triangles.size(), 0u);
1489}
1490
1491
1492TEST_F(GeomAlgorithmsTest, DelaunaySinglePoint)
1493{
1494 DelaunayTriangulationBowyerWatson delaunay;
1495 auto r = delaunay({Point(5, 5)});
1496
1497 EXPECT_EQ(r.sites.size(), 1u);
1498 EXPECT_EQ(r.triangles.size(), 0u);
1499}
1500
1501
1502TEST_F(GeomAlgorithmsTest, DelaunayTwoPoints)
1503{
1504 DelaunayTriangulationBowyerWatson delaunay;
1505 auto r = delaunay({Point(0, 0), Point(1, 1)});
1506
1507 EXPECT_EQ(r.sites.size(), 2u);
1508 EXPECT_EQ(r.triangles.size(), 0u);
1509}
1510
1511
1512TEST_F(GeomAlgorithmsTest, DelaunayAllDuplicates)
1513{
1514 DelaunayTriangulationBowyerWatson delaunay;
1515 auto r = delaunay({Point(3, 3), Point(3, 3), Point(3, 3), Point(3, 3)});
1516
1517 EXPECT_EQ(r.sites.size(), 1u);
1518 EXPECT_EQ(r.triangles.size(), 0u);
1519}
1520
1521
1522TEST_F(GeomAlgorithmsTest, DelaunayTwoDistinctWithDuplicates)
1523{
1524 DelaunayTriangulationBowyerWatson delaunay;
1525 auto r = delaunay({Point(0, 0), Point(0, 0), Point(5, 5), Point(5, 5)});
1526
1527 EXPECT_EQ(r.sites.size(), 2u);
1528 EXPECT_EQ(r.triangles.size(), 0u);
1529}
1530
1531
1532// ---------- Edge cases: Voronoi ----------
1533
1534TEST_F(GeomAlgorithmsTest, VoronoiEmptyInput)
1535{
1536 VoronoiDiagramFromDelaunay voronoi;
1537 DynList<Point> empty;
1538 auto r = voronoi(empty);
1539
1540 EXPECT_EQ(r.sites.size(), 0u);
1541 EXPECT_EQ(r.vertices.size(), 0u);
1542 EXPECT_EQ(r.edges.size(), 0u);
1543 EXPECT_EQ(r.cells.size(), 0u);
1544}
1545
1546
1547TEST_F(GeomAlgorithmsTest, VoronoiSinglePoint)
1548{
1549 VoronoiDiagramFromDelaunay voronoi;
1550 auto r = voronoi({Point(5, 5)});
1551
1552 EXPECT_EQ(r.sites.size(), 1u);
1553 EXPECT_EQ(r.vertices.size(), 0u);
1554 EXPECT_EQ(r.edges.size(), 0u);
1555}
1556
1557
1558TEST_F(GeomAlgorithmsTest, VoronoiTwoPoints)
1559{
1560 VoronoiDiagramFromDelaunay voronoi;
1561 auto r = voronoi({Point(0, 0), Point(4, 0)});
1562
1563 EXPECT_EQ(r.sites.size(), 2u);
1564 EXPECT_EQ(r.edges.size(), 0u);
1565}
1566
1567
1568TEST_F(GeomAlgorithmsTest, VoronoiCollinearPoints)
1569{
1570 VoronoiDiagramFromDelaunay voronoi;
1571 auto r = voronoi({Point(0, 0), Point(1, 0), Point(2, 0), Point(3, 0)});
1572
1573 EXPECT_EQ(r.sites.size(), 4u);
1574 EXPECT_EQ(r.edges.size(), 0u); // Delaunay has 0 triangles for collinear.
1575}
1576
1577
1578// ---------- CuttingEarsTriangulation: new critical tests ----------
1579
1580TEST_F(GeomAlgorithmsTest, CuttingEarsCollinearEdges)
1581{
1582 // Rectangle with extra collinear points on the bottom edge.
1583 // (0,0)-(2,0)-(4,0)-(6,0)-(6,4)-(0,4) — 6 vertices, 3 collinear on bottom.
1584 // Note: the ear-cutting algorithm merges collinear vertices internally,
1585 // so the effective vertex count may be less than 6.
1586 Polygon p;
1587 p.add_vertex(Point(0, 0));
1588 p.add_vertex(Point(2, 0));
1589 p.add_vertex(Point(4, 0));
1590 p.add_vertex(Point(6, 0));
1591 p.add_vertex(Point(6, 4));
1592 p.add_vertex(Point(0, 4));
1593 p.close();
1594
1595 CuttingEarsTriangulation triangulator;
1596 auto triangles = triangulator(p);
1597
1598 // At least 1 triangle must be produced.
1599 EXPECT_GE(triangles.size(), 1u);
1600
1601 // Verify total area equals original polygon area (6*4 = 24).
1602 Geom_Number total_area = 0;
1603 for (auto it = triangles.get_it(); it.has_curr(); it.next_ne())
1604 total_area += triangle_area(it.get_curr());
1605
1606 EXPECT_EQ(total_area, Geom_Number(24));
1607}
1608
1609
1610TEST_F(GeomAlgorithmsTest, CuttingEarsManyVertices)
1611{
1612 // 200-vertex circle polygon.
1613 const size_t N = 200;
1614 Polygon p;
1615 for (size_t i = 0; i < N; ++i)
1616 {
1617 Geom_Number angle = Geom_Number(2) * Geom_Number(M_PI) * Geom_Number(i)
1618 / Geom_Number(N);
1619 Geom_Number x = Geom_Number(100) * Geom_Number(cos(angle.get_d()));
1620 Geom_Number y = Geom_Number(100) * Geom_Number(sin(angle.get_d()));
1621 p.add_vertex(Point(x, y));
1622 }
1623 p.close();
1624
1625 CuttingEarsTriangulation triangulator;
1626 auto triangles = triangulator(p);
1627
1628 // n-2 triangles.
1629 EXPECT_EQ(triangles.size(), N - 2);
1630
1631 // All triangles must have positive area.
1632 Geom_Number total_area = 0;
1633 for (auto it = triangles.get_it(); it.has_curr(); it.next_ne())
1634 {
1635 Geom_Number a = triangle_area(it.get_curr());
1636 EXPECT_GT(a, Geom_Number(0));
1637 total_area += a;
1638 }
1639
1640 // Triangulation area must exactly equal the polygon area.
1641 Geom_Number poly_area = polygon_area(p);
1642 EXPECT_EQ(total_area, poly_area)
1643 << "Triangulation area (" << total_area.get_d()
1644 << ") != polygon area (" << poly_area.get_d() << ")";
1645}
1646
1647
1648TEST_F(GeomAlgorithmsTest, CuttingEarsConsecutiveReflexVertices)
1649{
1650 // Star-shaped polygon with 5 consecutive reflex vertices.
1651 // Outer vertices at radius 10, inner (reflex) at radius 4.
1652 Polygon p;
1653 const size_t spikes = 5;
1654 for (size_t i = 0; i < spikes; ++i)
1655 {
1656 // Outer point.
1657 Geom_Number angle_out = Geom_Number(2) * Geom_Number(M_PI) * Geom_Number(i)
1658 / Geom_Number(spikes);
1659 p.add_vertex(Point(Geom_Number(10) * Geom_Number(cos(angle_out.get_d())),
1660 Geom_Number(10) * Geom_Number(sin(angle_out.get_d()))));
1661
1662 // Inner (reflex) point.
1663 Geom_Number angle_in = angle_out
1664 + Geom_Number(M_PI) / Geom_Number(spikes);
1665 p.add_vertex(Point(Geom_Number(4) * Geom_Number(cos(angle_in.get_d())),
1666 Geom_Number(4) * Geom_Number(sin(angle_in.get_d()))));
1667 }
1668 p.close();
1669
1670 const size_t n = 2 * spikes; // 10 vertices
1671 CuttingEarsTriangulation triangulator;
1672 auto triangles = triangulator(p);
1673
1674 EXPECT_EQ(triangles.size(), n - 2);
1675
1676 // Verify total area is positive and all triangles non-degenerate.
1677 Geom_Number total_area = 0;
1678 for (auto it = triangles.get_it(); it.has_curr(); it.next_ne())
1679 {
1680 Geom_Number a = triangle_area(it.get_curr());
1681 EXPECT_GT(a, Geom_Number(0));
1682 total_area += a;
1683 }
1684 EXPECT_GT(total_area, Geom_Number(0));
1685}
1686
1687
1688// ---------- Convex Hull: new critical tests ----------
1689
1690TEST_F(GeomAlgorithmsTest, ConvexHullPointsOnCircle)
1691{
1692 // 100 points on a circle — all should be on the hull.
1693 const size_t N = 100;
1694 DynList<Point> pts;
1695 for (size_t i = 0; i < N; ++i)
1696 {
1697 Geom_Number angle = Geom_Number(2) * Geom_Number(M_PI) * Geom_Number(i)
1698 / Geom_Number(N);
1699 pts.append(Point(Geom_Number(50) * Geom_Number(cos(angle.get_d())),
1700 Geom_Number(50) * Geom_Number(sin(angle.get_d()))));
1701 }
1702
1703 QuickHull qh;
1704 auto hull_qh = qh(pts);
1705
1706 AndrewMonotonicChainConvexHull andrew;
1707 auto hull_andrew = andrew(pts);
1708
1709 GrahamScanConvexHull graham;
1710 auto hull_graham = graham(pts);
1711
1712 // All algorithms should return all 100 points.
1713 EXPECT_EQ(hull_qh.size(), N);
1714 EXPECT_EQ(hull_andrew.size(), N);
1715 EXPECT_EQ(hull_graham.size(), N);
1716
1717 // Hulls must be convex.
1718 EXPECT_TRUE(polygon_is_convex(hull_qh));
1719 EXPECT_TRUE(polygon_is_convex(hull_andrew));
1720 EXPECT_TRUE(polygon_is_convex(hull_graham));
1721
1722 // Hulls must be in CCW orientation.
1723 EXPECT_TRUE(is_ccw(hull_qh)) << "QuickHull result not CCW";
1724 EXPECT_TRUE(is_ccw(hull_andrew)) << "Andrew result not CCW";
1725 EXPECT_TRUE(is_ccw(hull_graham)) << "Graham result not CCW";
1726}
1727
1728
1729TEST_F(GeomAlgorithmsTest, ConvexHullClusteredDistribution)
1730{
1731 // 10K points in 5 clusters.
1732 DynList<Point> pts;
1733 const Geom_Number centers[][2] = {
1734 {0, 0}, {100, 0}, {200, 0}, {50, 100}, {150, 100}
1735 };
1736
1737 std::mt19937 rng(42);
1738 std::uniform_real_distribution<double> offset(-5.0, 5.0);
1739
1740 for (size_t c = 0; c < 5; ++c)
1741 for (size_t i = 0; i < 2000; ++i)
1742 pts.append(Point(centers[c][0] + Geom_Number(offset(rng)),
1743 centers[c][1] + Geom_Number(offset(rng))));
1744
1745 QuickHull qh;
1746 auto hull_qh = qh(pts);
1747
1748 AndrewMonotonicChainConvexHull andrew;
1749 auto hull_andrew = andrew(pts);
1750
1751 // Both should produce convex hulls with consistent vertex count.
1752 EXPECT_TRUE(polygon_is_convex(hull_qh));
1753 EXPECT_TRUE(polygon_is_convex(hull_andrew));
1754 EXPECT_EQ(hull_qh.size(), hull_andrew.size());
1755
1756 // All original points should be inside or on the hull.
1757 EXPECT_TRUE(all_points_inside_or_on(pts, hull_qh));
1758}
1759
1760
1761TEST_F(GeomAlgorithmsTest, ConvexHullStress100K)
1762{
1763 // 100K random points. Run QuickHull + Andrew only.
1764 DynList<Point> pts;
1765 std::mt19937 rng(123);
1766 std::uniform_real_distribution<double> dist(-1000.0, 1000.0);
1767
1768 for (size_t i = 0; i < 100000; ++i)
1769 pts.append(Point(Geom_Number(dist(rng)), Geom_Number(dist(rng))));
1770
1771 QuickHull qh;
1772 auto hull_qh = qh(pts);
1773
1774 AndrewMonotonicChainConvexHull andrew;
1775 auto hull_andrew = andrew(pts);
1776
1777 // Both should produce convex results with same vertex count.
1778 EXPECT_TRUE(polygon_is_convex(hull_qh));
1779 EXPECT_TRUE(polygon_is_convex(hull_andrew));
1780 EXPECT_EQ(hull_qh.size(), hull_andrew.size());
1781 EXPECT_GE(hull_qh.size(), 3u);
1782}
1783
1784
1785// ---------- Delaunay: new critical tests ----------
1786
1787TEST_F(GeomAlgorithmsTest, DelaunayCocircularPoints)
1788{
1789 // 8 points on a circle. Delaunay must still produce valid triangulation.
1790 const size_t N = 8;
1791 DynList<Point> pts;
1792 for (size_t i = 0; i < N; ++i)
1793 {
1794 Geom_Number angle = Geom_Number(2) * Geom_Number(M_PI) * Geom_Number(i)
1795 / Geom_Number(N);
1796 pts.append(Point(Geom_Number(10) * Geom_Number(cos(angle.get_d())),
1797 Geom_Number(10) * Geom_Number(sin(angle.get_d()))));
1798 }
1799
1800 DelaunayTriangulationBowyerWatson del;
1801 auto r = del(pts);
1802
1803 EXPECT_EQ(r.sites.size(), N);
1804 EXPECT_GE(r.triangles.size(), 1u);
1805
1806 // All triangles must be non-degenerate.
1807 for (size_t t = 0; t < r.triangles.size(); ++t)
1808 {
1809 const auto & tri = r.triangles(t);
1810 EXPECT_NE(orientation(r.sites(tri.i), r.sites(tri.j), r.sites(tri.k)),
1811 Orientation::COLLINEAR);
1812 }
1813}
1814
1815
1816TEST_F(GeomAlgorithmsTest, DelaunayNearDegenerateTriangles)
1817{
1818 // Points forming very thin triangles.
1819 DynList<Point> pts;
1820 pts.append(Point(0, 0));
1821 pts.append(Point(1000, 0));
1822 pts.append(Point(500, 1)); // nearly collinear
1823 pts.append(Point(250, 0));
1824 pts.append(Point(750, 0));
1825
1826 DelaunayTriangulationBowyerWatson del;
1827 auto r = del(pts);
1828
1829 EXPECT_GE(r.triangles.size(), 1u);
1830
1831 // Verify Delaunay property: no point strictly inside circumcircle.
1832 // Using exact rational arithmetic (GMP), so no tolerance needed.
1833 for (size_t t = 0; t < r.triangles.size(); ++t)
1834 {
1835 const auto & tri = r.triangles(t);
1836 const Point & a = r.sites(tri.i);
1837 const Point & b = r.sites(tri.j);
1838 const Point & c = r.sites(tri.k);
1839
1840 if (orientation(a, b, c) == Orientation::COLLINEAR)
1841 continue;
1842
1843 Point cc = circumcenter_of(a, b, c);
1844 Geom_Number r2 = cc.distance_squared_to(a);
1845
1846 for (size_t s = 0; s < r.sites.size(); ++s)
1847 {
1848 if (s == tri.i or s == tri.j or s == tri.k)
1849 continue;
1850 Geom_Number d2 = cc.distance_squared_to(r.sites(s));
1851 // Exact: d2 must be >= r2 (on or outside circumcircle).
1852 EXPECT_GE(d2, r2)
1853 << "Site " << s << " is strictly inside circumcircle of triangle " << t;
1854 }
1855 }
1856}
1857
1858
1859TEST_F(GeomAlgorithmsTest, DelaunayLargeDataset)
1860{
1861 // 2K random points. Verify Delaunay empty-circumcircle property
1862 // for ALL triangles by checking against ALL sites.
1863 DynList<Point> pts;
1864 std::mt19937 rng(77);
1865 std::uniform_real_distribution<double> dist(-500.0, 500.0);
1866
1867 const size_t N = 2000;
1868 for (size_t i = 0; i < N; ++i)
1869 pts.append(Point(Geom_Number(dist(rng)), Geom_Number(dist(rng))));
1870
1871 DelaunayTriangulationBowyerWatson del;
1872 auto r = del(pts);
1873
1874 EXPECT_EQ(r.sites.size(), N);
1875 EXPECT_GE(r.triangles.size(), 1u);
1876
1877 // Verify Delaunay property for every triangle.
1878 size_t violations = 0;
1879 for (size_t t = 0; t < r.triangles.size(); ++t)
1880 {
1881 const auto & tri = r.triangles(t);
1882 const Point & a = r.sites(tri.i);
1883 const Point & b = r.sites(tri.j);
1884 const Point & c = r.sites(tri.k);
1885
1886 if (orientation(a, b, c) == Orientation::COLLINEAR)
1887 continue;
1888
1889 Point cc = circumcenter_of(a, b, c);
1890 Geom_Number r2 = cc.distance_squared_to(a);
1891
1892 for (size_t s = 0; s < r.sites.size(); ++s)
1893 {
1894 if (s == tri.i or s == tri.j or s == tri.k)
1895 continue;
1896 Geom_Number d2 = cc.distance_squared_to(r.sites(s));
1897 if (d2 < r2 - Geom_Number(1, 1000000))
1898 ++violations;
1899 }
1900 }
1901
1902 EXPECT_EQ(violations, 0u)
1903 << violations << " Delaunay circumcircle violations found";
1904}
1905
w
long double w
Definition btreepic.C:153
Aleph::AndrewMonotonicChainConvexHull
Andrew's monotonic chain convex hull algorithm.
Definition geom_algorithms.H:4742
Aleph::Array
Simple dynamic array with automatic resizing and functional operations.
Definition tpl_array.H:139
Aleph::Array::size
constexpr size_t size() const noexcept
Return the number of elements stored in the stack.
Definition tpl_array.H:351
Aleph::Array::append
T & append(const T &data)
Append a copy of data
Definition tpl_array.H:245
Aleph::Array::reserve
void reserve(size_t cap)
Reserves cap cells into the array.
Definition tpl_array.H:315
Aleph::BruteForceConvexHull
Brute force convex hull algorithm.
Definition geom_algorithms.H:5065
Aleph::ClosestPairDivideAndConquer
Closest pair of points via divide and conquer.
Definition geom_algorithms.H:844
Aleph::ConvexPolygonIntersectionBasic
Basic exact intersection for closed convex polygons.
Definition geom_algorithms.H:1577
Aleph::CuttingEarsTriangulation
Polygon triangulation using the ear-cutting algorithm.
Definition geom_algorithms.H:640
Aleph::DelaunayTriangulationBowyerWatson
Exact Delaunay triangulation using the Bowyer-Watson incremental algorithm.
Definition geom_algorithms.H:2114
Aleph::DynList::Iterator
Iterator on the items of list.
Definition htlist.H:1420
Aleph::DynList
Dynamic singly linked list with functional programming support.
Definition htlist.H:1155
Aleph::DynList::append
T & append(const T &item)
Definition htlist.H:1271
Aleph::GiftWrappingConvexHull
Gift wrapping (Jarvis march) convex hull algorithm.
Definition geom_algorithms.H:5222
Aleph::GrahamScanConvexHull
Graham scan convex hull algorithm.
Definition geom_algorithms.H:4877
Aleph::HTList::Iterator::has_curr
bool has_curr() const noexcept
Definition htlist.H:930
Aleph::HalfPlaneIntersection
Exact bounded intersection of half-planes.
Definition geom_algorithms.H:1773
Aleph::HalfPlaneIntersection::from_convex_polygon
static Array< HalfPlane > from_convex_polygon(const Polygon &poly)
Build half-planes from the edges of a closed convex polygon.
Definition geom_algorithms.H:1916
Aleph::PointInPolygonWinding
Exact point-in-polygon classification via winding number.
Definition geom_algorithms.H:1490
Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229
Aleph::Polygon
A general (irregular) 2D polygon defined by a sequence of vertices.
Definition polygon.H:246
Aleph::Polygon::append
void append(const Point &point)
Append a vertex (Aleph container protocol).
Definition polygon.H:764
Aleph::Polygon::add_vertex
void add_vertex(const Point &point)
Add a vertex to the polygon.
Definition polygon.H:677
Aleph::Polygon::close
void close()
Close the polygon.
Definition polygon.H:840
Aleph::QuickHull
QuickHull convex hull algorithm.
Definition geom_algorithms.H:5332
Aleph::RotatingCalipersConvexPolygon
Rotating calipers metrics for convex polygons.
Definition geom_algorithms.H:1275
Aleph::RotatingCalipersConvexPolygon::diameter
static DiameterResult diameter(const Polygon &poly)
Compute convex polygon diameter (farthest vertex pair).
Definition geom_algorithms.H:1339
Aleph::RotatingCalipersConvexPolygon::minimum_width
static WidthResult minimum_width(const Polygon &poly)
Compute the minimum width of a closed convex polygon.
Definition geom_algorithms.H:1394
Aleph::Segment
Represents a line segment between two points.
Definition point.H:827
Aleph::Segment::get_tgt_point
const Point & get_tgt_point() const noexcept
Gets the target point of the segment.
Definition point.H:921
Aleph::Segment::get_src_point
const Point & get_src_point() const noexcept
Gets the source point of the segment.
Definition point.H:915
Aleph::VoronoiDiagramFromDelaunay
Voronoi diagram derived as the dual of a Delaunay triangulation.
Definition geom_algorithms.H:3682
__gmp_expr< mpq_t, mpq_t >
Definition gmpfrxx.h:2041
__gmp_expr< mpq_t, mpq_t >::get_d
double get_d() const
Definition gmpfrxx.h:2199
rng
static mt19937 rng
Definition disjoint_sparse_table_test.cc:148
N
#define N
Definition fib.C:294
geom_algorithms_test_common.h
TEST_F
TEST_F(GeomAlgorithmsTest, TriangulateTriangle)
Definition geom_algorithms_test_triangulation_hulls_delaunay.cc:5
triangle_area
double triangle_area(const Triangle &t)
Calculate area of a triangle using cross product.
Definition geom_example.C:216
cos
__gmp_expr< T, __gmp_unary_expr< __gmp_expr< T, U >, __gmp_cos_function > > cos(const __gmp_expr< T, U > &expr)
Definition gmpfrxx.h:4069
sin
__gmp_expr< T, __gmp_unary_expr< __gmp_expr< T, U >, __gmp_sin_function > > sin(const __gmp_expr< T, U > &expr)
Definition gmpfrxx.h:4070
offset
const long double offset[]
Offset values indexed by symbol string length (bounded by MAX_OFFSET_INDEX)
Definition huffman_btreepic.H:188
y
static mpfr_t y
Definition mpfr_mul_d.c:3
Aleph::TestVisual::add_polygon_vertices
void add_polygon_vertices(SvgScene &scene, const ::Polygon &poly, const bool as_highlight=false)
Definition geometry_visual_golden.h:100
Aleph::TestVisual::emit_case_svg
std::filesystem::path emit_case_svg(const std::string &case_id, const SvgScene &scene, const std::string &note="")
Definition geometry_visual_golden.h:137
Aleph::and
and
Check uniqueness with explicit hash + equality functors.
Definition ahFunctional.H:2594
Aleph::size
size_t size(Node *root) noexcept
Definition tpl_binNodeUtils.H:491
Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133
Aleph::orientation
Orientation orientation(const Point &a, const Point &b, const Point &c)
Return the orientation of the triple (a, b, c).
Definition point.H:2821
Aleph::Geom_Number
mpq_class Geom_Number
Numeric type used by the geometry module.
Definition point.H:115
polygon_area
static Geom_Number polygon_area(const Polygon &poly)
Definition polygon_intersection_example.cc:60
poly_area
static Geom_Number poly_area(const Polygon &p)
Definition polygon_offset_example.cc:41
r
gsl_rng * r
Definition test_sort_lists.C:40