Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
geom_algorithms_test.cc
Go to the documentation of this file.
1#include <gtest/gtest.h>
2#include <geom_algorithms.H>
3
4class GeomAlgorithmsTest : public ::testing::Test
5{
6protected:
7 void SetUp() override {}
8 void TearDown() override {}
9};
10
11// Basic triangulation tests
25
26TEST_F(GeomAlgorithmsTest, TriangulateSquare)
27{
28 Polygon p;
29 p.add_vertex(Point(0, 0));
30 p.add_vertex(Point(4, 0));
31 p.add_vertex(Point(4, 4));
32 p.add_vertex(Point(0, 4));
33 p.close();
34
35 CuttingEarsTriangulation triangulator;
36 auto triangles = triangulator(p);
37
38 EXPECT_EQ(triangles.size(), 2u);
39}
40
41TEST_F(GeomAlgorithmsTest, TriangulatePentagon)
42{
43 Polygon p;
44 p.add_vertex(Point(2, 0));
45 p.add_vertex(Point(4, 1.5));
46 p.add_vertex(Point(3, 4));
47 p.add_vertex(Point(1, 4));
48 p.add_vertex(Point(0, 1.5));
49 p.close();
50
51 CuttingEarsTriangulation triangulator;
52 auto triangles = triangulator(p);
53
54 EXPECT_EQ(triangles.size(), 3u);
55}
56
57// Convex hull tests
58TEST_F(GeomAlgorithmsTest, QuickHullTriangle)
59{
60 DynList<Point> points;
61 points.append(Point(0, 0));
62 points.append(Point(6, 0));
63 points.append(Point(3, 5));
64
65 QuickHull qh;
66 Polygon hull = qh(points);
67
68 EXPECT_EQ(hull.size(), 3u);
69}
70
71TEST_F(GeomAlgorithmsTest, QuickHullSquare)
72{
73 DynList<Point> points;
74 points.append(Point(0, 0));
75 points.append(Point(5, 0));
76 points.append(Point(5, 5));
77 points.append(Point(0, 5));
78
79 QuickHull qh;
80 Polygon hull = qh(points);
81
82 EXPECT_EQ(hull.size(), 4u);
83}
84
85TEST_F(GeomAlgorithmsTest, QuickHullWithInterior)
86{
87 DynList<Point> points;
88 points.append(Point(0, 0));
89 points.append(Point(10, 0));
90 points.append(Point(10, 10));
91 points.append(Point(0, 10));
92 points.append(Point(5, 5)); // Interior
93
94 QuickHull qh;
95 Polygon hull = qh(points);
96
97 EXPECT_EQ(hull.size(), 4u);
98}
99
100TEST_F(GeomAlgorithmsTest, GiftWrappingSquare)
101{
102 DynList<Point> points;
103 points.append(Point(0, 0));
104 points.append(Point(4, 0));
105 points.append(Point(4, 4));
106 points.append(Point(0, 4));
107
108 GiftWrappingConvexHull gw;
109 Polygon hull = gw(points);
110
111 EXPECT_EQ(hull.size(), 4u);
112}
113
114TEST_F(GeomAlgorithmsTest, BruteForceHullTriangle)
115{
116 DynList<Point> points;
117 points.append(Point(0, 0));
118 points.append(Point(4, 0));
119 points.append(Point(2, 3));
120
121 BruteForceConvexHull bf;
122 Polygon hull = bf(points);
123
124 EXPECT_EQ(hull.size(), 3u);
125}
126
127TEST_F(GeomAlgorithmsTest, ThreePointsHull)
128{
129 DynList<Point> points;
130 points.append(Point(0, 0));
131 points.append(Point(2, 0));
132 points.append(Point(1, 2));
133
134 QuickHull qh;
135 Polygon hull = qh(points);
136
137 EXPECT_EQ(hull.size(), 3u);
138}
139
140TEST_F(GeomAlgorithmsTest, TriangulateHexagon)
141{
142 Polygon p;
143 p.add_vertex(Point(1, 0));
144 p.add_vertex(Point(2, 0));
145 p.add_vertex(Point(3, 1));
146 p.add_vertex(Point(2, 2));
147 p.add_vertex(Point(1, 2));
148 p.add_vertex(Point(0, 1));
149 p.close();
150
151 CuttingEarsTriangulation triangulator;
152 auto triangles = triangulator(p);
153
154 EXPECT_EQ(triangles.size(), 4u);
155}
Aleph::BruteForceConvexHull
Brute force convex hull algorithm.
Definition geom_algorithms.H:348
Aleph::CuttingEarsTriangulation
Polygon triangulation using the ear-cutting algorithm.
Definition geom_algorithms.H:169
Aleph::DynList
Dynamic singly linked list with functional programming support.
Definition htlist.H:1423
Aleph::DynList::append
T & append(const T &item)
Append a new item by copy.
Definition htlist.H:1562
Aleph::GiftWrappingConvexHull
Gift wrapping (Jarvis march) convex hull algorithm.
Definition geom_algorithms.H:482
Aleph::HTList::size
size_t size() const noexcept
Count the number of elements of the list.
Definition htlist.H:1319
Aleph::QuickHull
QuickHull convex hull algorithm.
Definition geom_algorithms.H:587
Point
Rectangular point in the plane.
Definition point.H:156
Polygon
A general (irregular) 2D polygon defined by a sequence of vertices.
Definition polygon.H:233
Polygon::close
void close()
Close the polygon.
Definition polygon.H:710
Polygon::add_vertex
void add_vertex(const Point &point)
Add a vertex to the polygon.
Definition polygon.H:610
geom_algorithms.H
Computational geometry algorithms.
TEST_F
TEST_F(GeomAlgorithmsTest, TriangulateTriangle)
Definition geom_algorithms_test.cc:12
Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693