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 326 of file EarClippingTriangulation.cpp.

327{
328 auto next = _vertex_list.begin();
329 auto prev = next;
330 ++next;
331 if (next == _vertex_list.end())
332 {
333 return;
334 }
335 auto it = next;
336 ++next;
337 if (next == _vertex_list.end())
338 {
339 return;
340 }
341
342 if (getOrientation(*_pnts[*prev], *_pnts[*it], *_pnts[*next]) ==
343 GeoLib::CCW)
344 {
345 _triangles.emplace_back(_pnts, *prev, *it, *next);
346 }
347 else
348 {
349 _triangles.emplace_back(_pnts, *prev, *next, *it);
350 }
351}
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 197 of file EarClippingTriangulation.cpp.

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