OGS
GeoLib::EarClippingTriangulation Class Referencefinal

Detailed Description

Definition at line 16 of file EarClippingTriangulation.h.

#include <EarClippingTriangulation.h>

Public Member Functions

 EarClippingTriangulation (GeoLib::Polygon const &polygon, std::list< GeoLib::Triangle > &triangles, bool rot=true)
 ~EarClippingTriangulation ()

Private Member Functions

void copyPolygonPoints (GeoLib::Polygon const &polygon)
void ensureCWOrientation ()
bool isEar (std::size_t v0, std::size_t v1, std::size_t v2) const
void initVertexList ()
void initLists ()
void clipEars ()
void addLastTriangle ()

Private Attributes

std::vector< GeoLib::Point * > _pnts
std::list< std::size_t > _vertex_list
std::list< std::size_t > _convex_vertex_list
std::list< std::size_t > _ear_list
std::list< GeoLib::Triangle > _triangles
GeoLib::Orientation _original_orientation

Constructor & Destructor Documentation

◆ EarClippingTriangulation()

GeoLib::EarClippingTriangulation::EarClippingTriangulation ( GeoLib::Polygon const & polygon,
std::list< GeoLib::Triangle > & triangles,
bool rot = true )

Definition at line 16 of file EarClippingTriangulation.cpp.

19{
20 copyPolygonPoints(polygon);
21
22 if (rot)
23 {
24 rotatePointsToXY(_pnts);
25 ensureCWOrientation();
26 }
27
28 initVertexList();
29 initLists();
30 clipEars();
31 addLastTriangle();
32
33 std::vector<GeoLib::Point*> const& ref_pnts_vec(polygon.getPointsVec());
34 if (_original_orientation == GeoLib::CW)
35 {
36 for (auto const& t : _triangles)
37 {
38 const std::size_t i0(polygon.getPointID(t[0]));
39 const std::size_t i1(polygon.getPointID(t[1]));
40 const std::size_t i2(polygon.getPointID(t[2]));
41 triangles.emplace_back(ref_pnts_vec, i0, i1, i2);
42 }
43 }
44 else
45 {
46 std::size_t n_pnts(_pnts.size() - 1);
47 for (auto const& t : _triangles)
48 {
49 const std::size_t i0(polygon.getPointID(n_pnts - t[0]));
50 const std::size_t i1(polygon.getPointID(n_pnts - t[1]));
51 const std::size_t i2(polygon.getPointID(n_pnts - t[2]));
52 triangles.emplace_back(ref_pnts_vec, i0, i1, i2);
53 }
54 }
55}
GeoLib::EarClippingTriangulation::_pnts
std::vector< GeoLib::Point * > _pnts
Definition EarClippingTriangulation.h:41
GeoLib::EarClippingTriangulation::copyPolygonPoints
void copyPolygonPoints(GeoLib::Polygon const &polygon)
Definition EarClippingTriangulation.cpp:65
GeoLib::EarClippingTriangulation::_triangles
std::list< GeoLib::Triangle > _triangles
Definition EarClippingTriangulation.h:49
GeoLib::rotatePointsToXY
Eigen::Matrix3d rotatePointsToXY(InputIterator1 p_pnts_begin, InputIterator1 p_pnts_end, InputIterator2 r_pnts_begin, InputIterator2 r_pnts_end)
Definition AnalyticalGeometry-impl.h:80

References _original_orientation, _pnts, _triangles, addLastTriangle(), clipEars(), copyPolygonPoints(), GeoLib::CW, ensureCWOrientation(), GeoLib::Polyline::getPointID(), GeoLib::Polyline::getPointsVec(), initLists(), initVertexList(), and GeoLib::rotatePointsToXY().

◆ ~EarClippingTriangulation()

GeoLib::EarClippingTriangulation::~EarClippingTriangulation ( )

Definition at line 57 of file EarClippingTriangulation.cpp.

58{
59 for (auto p : _pnts)
60 {
61 delete p;
62 }
63}

References _pnts.

Member Function Documentation

◆ addLastTriangle()

void GeoLib::EarClippingTriangulation::addLastTriangle ( )
private

Definition at line 328 of file EarClippingTriangulation.cpp.

329{
330 auto next = _vertex_list.begin();
331 auto prev = next;
332 ++next;
333 if (next == _vertex_list.end())
334 {
335 return;
336 }
337 auto it = next;
338 ++next;
339 if (next == _vertex_list.end())
340 {
341 return;
342 }
343
344 if (getOrientation(*_pnts[*prev], *_pnts[*it], *_pnts[*next]) ==
345 GeoLib::CCW)
346 {
347 _triangles.emplace_back(_pnts, *prev, *it, *next);
348 }
349 else
350 {
351 _triangles.emplace_back(_pnts, *prev, *next, *it);
352 }
353}
GeoLib::getOrientation
Orientation getOrientation(MathLib::Point3d const &p0, MathLib::Point3d const &p1, MathLib::Point3d const &p2)
Definition AnalyticalGeometry.cpp:39

References _pnts, _triangles, _vertex_list, GeoLib::CCW, and GeoLib::getOrientation().

Referenced by EarClippingTriangulation().

◆ clipEars()

void GeoLib::EarClippingTriangulation::clipEars ( )
inlineprivate

Definition at line 199 of file EarClippingTriangulation.cpp.

200{
201 // *** clip an ear
202 while (_vertex_list.size() > 3)
203 {
204 // pop ear from list
205 std::size_t ear = _ear_list.front();
206 _ear_list.pop_front();
207 // remove ear tip from _convex_vertex_list
208 _convex_vertex_list.remove(ear);
209
210 // remove ear from vertex_list, apply changes to _ear_list,
211 // _convex_vertex_list
212 bool nfound(true);
213 auto it = _vertex_list.begin();
214 auto prev = _vertex_list.end();
215 --prev;
216 while (nfound && it != _vertex_list.end())
217 {
218 if (*it == ear)
219 {
220 nfound = false;
221 it = _vertex_list.erase(it); // remove ear tip
222 auto next = it;
223 if (next == _vertex_list.end())
224 {
225 next = _vertex_list.begin();
226 prev = _vertex_list.end();
227 --prev;
228 }
229 // add triangle
230 _triangles.emplace_back(_pnts, *prev, *next, ear);
231
232 // check the orientation of prevprev, prev, next
233 auto prevprev = prev;
234 if (prev == _vertex_list.begin())
235 {
236 prevprev = _vertex_list.end();
237 }
238 --prevprev;
239
240 // apply changes to _convex_vertex_list and _ear_list looking
241 // "backward"
242 GeoLib::Orientation orientation = GeoLib::getOrientation(
243 *_pnts[*prevprev], *_pnts[*prev], *_pnts[*next]);
244 if (orientation == GeoLib::CW)
245 {
246 BaseLib::uniquePushBack(_convex_vertex_list, *prev);
247 // prev is convex
248 if (isEar(*prevprev, *prev, *next))
249 {
250 // prev is an ear tip
251 BaseLib::uniquePushBack(_ear_list, *prev);
252 }
253 else
254 {
255 // if necessary remove prev
256 _ear_list.remove(*prev);
257 }
258 }
259 else
260 {
261 // prev is not convex => reflex or collinear
262 _convex_vertex_list.remove(*prev);
263 _ear_list.remove(*prev);
264 if (orientation == GeoLib::COLLINEAR)
265 {
266 prev = _vertex_list.erase(prev);
267 if (prev == _vertex_list.begin())
268 {
269 prev = _vertex_list.end();
270 --prev;
271 }
272 else
273 {
274 --prev;
275 }
276 }
277 }
278
279 // check the orientation of prev, next, nextnext
280 auto nextnext = next;
281 ++nextnext;
282 auto help_it = _vertex_list.end();
283 --help_it;
284 if (next == help_it)
285 {
286 nextnext = _vertex_list.begin();
287 }
288
289 // apply changes to _convex_vertex_list and _ear_list looking
290 // "forward"
291 orientation = getOrientation(*_pnts[*prev], *_pnts[*next],
292 *_pnts[*nextnext]);
293 if (orientation == GeoLib::CW)
294 {
295 BaseLib::uniquePushBack(_convex_vertex_list, *next);
296 // next is convex
297 if (isEar(*prev, *next, *nextnext))
298 {
299 // next is an ear tip
300 BaseLib::uniquePushBack(_ear_list, *next);
301 }
302 else
303 {
304 // if necessary remove *next
305 _ear_list.remove(*next);
306 }
307 }
308 else
309 {
310 // next is not convex => reflex or collinear
311 _convex_vertex_list.remove(*next);
312 _ear_list.remove(*next);
313 if (orientation == GeoLib::COLLINEAR)
314 {
315 _vertex_list.erase(next);
316 }
317 }
318 }
319 else
320 {
321 prev = it;
322 ++it;
323 }
324 }
325 }
326}
GeoLib::EarClippingTriangulation::isEar
bool isEar(std::size_t v0, std::size_t v1, std::size_t v2) const
Definition EarClippingTriangulation.cpp:128
GeoLib::EarClippingTriangulation::_convex_vertex_list
std::list< std::size_t > _convex_vertex_list
Definition EarClippingTriangulation.h:43
BaseLib::uniquePushBack
void uniquePushBack(Container &container, typename Container::value_type const &element)
Definition Algorithm.h:209

References _convex_vertex_list, _ear_list, _pnts, _triangles, _vertex_list, GeoLib::COLLINEAR, GeoLib::CW, GeoLib::getOrientation(), isEar(), and BaseLib::uniquePushBack().

Referenced by EarClippingTriangulation().

◆ copyPolygonPoints()

void GeoLib::EarClippingTriangulation::copyPolygonPoints ( GeoLib::Polygon const & polygon)
inlineprivate

copies the points of the polygon to the vector _pnts

Definition at line 65 of file EarClippingTriangulation.cpp.

66{
67 // copy points - last point is identical to the first
68 std::size_t n_pnts(polygon.getNumberOfPoints() - 1);
69 for (std::size_t k(0); k < n_pnts; k++)
70 {
71 _pnts.push_back(new GeoLib::Point(*(polygon.getPoint(k))));
72 }
73}

References _pnts, GeoLib::Polyline::getNumberOfPoints(), and GeoLib::Polyline::getPoint().

Referenced by EarClippingTriangulation().

◆ ensureCWOrientation()

void GeoLib::EarClippingTriangulation::ensureCWOrientation ( )
inlineprivate

Definition at line 75 of file EarClippingTriangulation.cpp.

76{
77 std::size_t n_pnts(_pnts.size());
78 // get the left most upper point
79 std::size_t min_x_max_y_idx(0); // for orientation check
80 for (std::size_t k(0); k < n_pnts; k++)
81 {
82 if ((*(_pnts[k]))[0] <= (*(_pnts[min_x_max_y_idx]))[0])
83 {
84 if ((*(_pnts[k]))[0] < (*(_pnts[min_x_max_y_idx]))[0])
85 {
86 min_x_max_y_idx = k;
87 }
88 else
89 {
90 if ((*(_pnts[k]))[1] > (*(_pnts[min_x_max_y_idx]))[1])
91 {
92 min_x_max_y_idx = k;
93 }
94 }
95 }
96 }
97 // determine orientation
98 if (0 < min_x_max_y_idx && min_x_max_y_idx < n_pnts - 1)
99 {
100 _original_orientation =
101 GeoLib::getOrientation(*_pnts[min_x_max_y_idx - 1],
102 *_pnts[min_x_max_y_idx],
103 *_pnts[min_x_max_y_idx + 1]);
104 }
105 else
106 {
107 if (0 == min_x_max_y_idx)
108 {
109 _original_orientation = GeoLib::getOrientation(
110 *_pnts[n_pnts - 1], *_pnts[0], *_pnts[1]);
111 }
112 else
113 {
114 _original_orientation = GeoLib::getOrientation(
115 *_pnts[n_pnts - 2], *_pnts[n_pnts - 1], *_pnts[0]);
116 }
117 }
118 if (_original_orientation == GeoLib::CCW)
119 {
120 // switch orientation
121 for (std::size_t k(0); k < n_pnts / 2; k++)
122 {
123 std::swap(_pnts[k], _pnts[n_pnts - 1 - k]);
124 }
125 }
126}

References _original_orientation, _pnts, GeoLib::CCW, and GeoLib::getOrientation().

Referenced by EarClippingTriangulation().

◆ initLists()

void GeoLib::EarClippingTriangulation::initLists ( )
inlineprivate

Definition at line 151 of file EarClippingTriangulation.cpp.

152{
153 // go through points checking ccw, cw or collinear order and identifying
154 // ears
155 auto it = _vertex_list.begin();
156 auto prev = _vertex_list.end();
157 --prev;
158 auto next = it;
159 ++next;
160 GeoLib::Orientation orientation;
161 bool first_run(
162 true); // saves special handling of the last case with identical code
163 while (_vertex_list.size() >= 3 && first_run)
164 {
165 if (next == _vertex_list.end())
166 {
167 first_run = false;
168 next = _vertex_list.begin();
169 }
170 orientation = getOrientation(*_pnts[*prev], *_pnts[*it], *_pnts[*next]);
171 if (orientation == GeoLib::COLLINEAR)
172 {
173 WARN(
174 "EarClippingTriangulation::initLists(): collinear points "
175 "({:f}, {:f}, {:f}), ({:f}, {:f}, {:f}), ({:f}, {:f}, {:f})",
176 (*_pnts[*prev])[0], (*_pnts[*prev])[1], (*_pnts[*prev])[2],
177 (*_pnts[*it])[0], (*_pnts[*it])[1], (*_pnts[*it])[2],
178 (*_pnts[*next])[0], (*_pnts[*next])[1], (*_pnts[*next])[2]);
179 it = _vertex_list.erase(it);
180 ++next;
181 }
182 else
183 {
184 if (orientation == GeoLib::CW)
185 {
186 _convex_vertex_list.push_back(*it);
187 if (isEar(*prev, *it, *next))
188 {
189 _ear_list.push_back(*it);
190 }
191 }
192 prev = it;
193 it = next;
194 ++next;
195 }
196 }
197}
WARN
void WARN(fmt::format_string< Args... > fmt, Args &&... args)
Definition Logging.h:34

References _convex_vertex_list, _ear_list, _pnts, _vertex_list, GeoLib::COLLINEAR, GeoLib::CW, GeoLib::getOrientation(), isEar(), and WARN().

Referenced by EarClippingTriangulation().

◆ initVertexList()

void GeoLib::EarClippingTriangulation::initVertexList ( )
inlineprivate

Definition at line 145 of file EarClippingTriangulation.cpp.

146{
147 _vertex_list.resize(_pnts.size());
148 std::iota(begin(_vertex_list), end(_vertex_list), 0);
149}

References _pnts, and _vertex_list.

Referenced by EarClippingTriangulation().

◆ isEar()

bool GeoLib::EarClippingTriangulation::isEar ( std::size_t v0,
std::size_t v1,
std::size_t v2 ) const
inlineprivate

Definition at line 128 of file EarClippingTriangulation.cpp.

130{
131 for (auto const& v : _vertex_list)
132 {
133 if (v != v0 && v != v1 && v != v2)
134 {
135 if (MathLib::isPointInTriangle(*_pnts[v], *_pnts[v0], *_pnts[v1],
136 *_pnts[v2]))
137 {
138 return false;
139 }
140 }
141 }
142 return true;
143}
MathLib::isPointInTriangle
bool isPointInTriangle(MathLib::Point3d const &p, MathLib::Point3d const &a, MathLib::Point3d const &b, MathLib::Point3d const &c, double eps_pnt_out_of_plane, double eps_pnt_out_of_tri, MathLib::TriangleTest algorithm)
Definition GeometricBasics.cpp:78

References _pnts, _vertex_list, and MathLib::isPointInTriangle().

Referenced by clipEars(), and initLists().

Member Data Documentation

◆ _convex_vertex_list

std::list<std::size_t> GeoLib::EarClippingTriangulation::_convex_vertex_list
private

Definition at line 43 of file EarClippingTriangulation.h.

Referenced by clipEars(), and initLists().

◆ _ear_list

std::list<std::size_t> GeoLib::EarClippingTriangulation::_ear_list
private

Definition at line 44 of file EarClippingTriangulation.h.

Referenced by clipEars(), and initLists().

◆ _original_orientation

GeoLib::Orientation GeoLib::EarClippingTriangulation::_original_orientation
private

Definition at line 51 of file EarClippingTriangulation.h.

Referenced by EarClippingTriangulation(), and ensureCWOrientation().

◆ _pnts

std::vector<GeoLib::Point*> GeoLib::EarClippingTriangulation::_pnts
private

a copy of the polygon points

Definition at line 41 of file EarClippingTriangulation.h.

Referenced by EarClippingTriangulation(), ~EarClippingTriangulation(), addLastTriangle(), clipEars(), copyPolygonPoints(), ensureCWOrientation(), initLists(), initVertexList(), and isEar().

◆ _triangles

std::list<GeoLib::Triangle> GeoLib::EarClippingTriangulation::_triangles
private

triangles of the triangulation (maybe in the wrong orientation)

Definition at line 49 of file EarClippingTriangulation.h.

Referenced by EarClippingTriangulation(), addLastTriangle(), and clipEars().

◆ _vertex_list

std::list<std::size_t> GeoLib::EarClippingTriangulation::_vertex_list
private

Definition at line 42 of file EarClippingTriangulation.h.

Referenced by addLastTriangle(), clipEars(), initLists(), initVertexList(), and isEar().

The documentation for this class was generated from the following files: