OGS
GeoLib::EarClippingTriangulation Class Referencefinal

Detailed Description

Definition at line 27 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 ()
 

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

30 {
31  copyPolygonPoints(polygon);
32 
33  if (rot)
34  {
37  }
38 
40  initLists();
41  clipEars();
42 
43  std::vector<GeoLib::Point*> const& ref_pnts_vec(polygon.getPointsVec());
45  {
46  for (auto const& t : _triangles)
47  {
48  const std::size_t i0(polygon.getPointID(t[0]));
49  const std::size_t i1(polygon.getPointID(t[1]));
50  const std::size_t i2(polygon.getPointID(t[2]));
51  triangles.emplace_back(ref_pnts_vec, i0, i1, i2);
52  }
53  }
54  else
55  {
56  std::size_t n_pnts(_pnts.size() - 1);
57  for (auto const& t : _triangles)
58  {
59  const std::size_t i0(polygon.getPointID(n_pnts - t[0]));
60  const std::size_t i1(polygon.getPointID(n_pnts - t[1]));
61  const std::size_t i2(polygon.getPointID(n_pnts - t[2]));
62  triangles.emplace_back(ref_pnts_vec, i0, i1, i2);
63  }
64  }
65 }
std::vector< GeoLib::Point * > _pnts
void copyPolygonPoints(GeoLib::Polygon const &polygon)
std::list< GeoLib::Triangle > _triangles
Eigen::Matrix3d rotatePointsToXY(InputIterator1 p_pnts_begin, InputIterator1 p_pnts_end, InputIterator2 r_pnts_begin, InputIterator2 r_pnts_end)
static const double t

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

◆ ~EarClippingTriangulation()

GeoLib::EarClippingTriangulation::~EarClippingTriangulation ( )

Definition at line 67 of file EarClippingTriangulation.cpp.

68 {
69  for (auto p : _pnts)
70  {
71  delete p;
72  }
73 }

References _pnts.

Member Function Documentation

◆ clipEars()

void GeoLib::EarClippingTriangulation::clipEars ( )
inlineprivate

Definition at line 207 of file EarClippingTriangulation.cpp.

208 {
209  std::list<std::size_t>::iterator it, prev, next;
210  // *** clip an ear
211  while (_vertex_list.size() > 3)
212  {
213  // pop ear from list
214  std::size_t ear = _ear_list.front();
215  _ear_list.pop_front();
216  // remove ear tip from _convex_vertex_list
217  _convex_vertex_list.remove(ear);
218 
219  // remove ear from vertex_list, apply changes to _ear_list,
220  // _convex_vertex_list
221  bool nfound(true);
222  it = _vertex_list.begin();
223  prev = _vertex_list.end();
224  --prev;
225  while (nfound && it != _vertex_list.end())
226  {
227  if (*it == ear)
228  {
229  nfound = false;
230  it = _vertex_list.erase(it); // remove ear tip
231  next = it;
232  if (next == _vertex_list.end())
233  {
234  next = _vertex_list.begin();
235  prev = _vertex_list.end();
236  --prev;
237  }
238  // add triangle
239  _triangles.emplace_back(_pnts, *prev, *next, ear);
240 
241  // check the orientation of prevprev, prev, next
242  std::list<std::size_t>::iterator prevprev;
243  if (prev == _vertex_list.begin())
244  {
245  prevprev = _vertex_list.end();
246  }
247  else
248  {
249  prevprev = prev;
250  }
251  --prevprev;
252 
253  // apply changes to _convex_vertex_list and _ear_list looking
254  // "backward"
256  *_pnts[*prevprev], *_pnts[*prev], *_pnts[*next]);
257  if (orientation == GeoLib::CW)
258  {
260  // prev is convex
261  if (isEar(*prevprev, *prev, *next))
262  {
263  // prev is an ear tip
265  }
266  else
267  {
268  // if necessary remove prev
269  _ear_list.remove(*prev);
270  }
271  }
272  else
273  {
274  // prev is not convex => reflex or collinear
275  _convex_vertex_list.remove(*prev);
276  _ear_list.remove(*prev);
277  if (orientation == GeoLib::COLLINEAR)
278  {
279  prev = _vertex_list.erase(prev);
280  if (prev == _vertex_list.begin())
281  {
282  prev = _vertex_list.end();
283  --prev;
284  }
285  else
286  {
287  --prev;
288  }
289  }
290  }
291 
292  // check the orientation of prev, next, nextnext
293  std::list<std::size_t>::iterator nextnext,
294  help_it(_vertex_list.end());
295  --help_it;
296  if (next == help_it)
297  {
298  nextnext = _vertex_list.begin();
299  }
300  else
301  {
302  nextnext = next;
303  ++nextnext;
304  }
305 
306  // apply changes to _convex_vertex_list and _ear_list looking
307  // "forward"
308  orientation = getOrientation(*_pnts[*prev], *_pnts[*next],
309  *_pnts[*nextnext]);
310  if (orientation == GeoLib::CW)
311  {
313  // next is convex
314  if (isEar(*prev, *next, *nextnext))
315  {
316  // next is an ear tip
318  }
319  else
320  {
321  // if necessary remove *next
322  _ear_list.remove(*next);
323  }
324  }
325  else
326  {
327  // next is not convex => reflex or collinear
328  _convex_vertex_list.remove(*next);
329  _ear_list.remove(*next);
330  if (orientation == GeoLib::COLLINEAR)
331  {
332  next = _vertex_list.erase(next);
333  if (next == _vertex_list.end())
334  next = _vertex_list.begin();
335  }
336  }
337  }
338  else
339  {
340  prev = it;
341  ++it;
342  }
343  }
344  }
345 
346  // add last triangle
347  next = _vertex_list.begin();
348  prev = next;
349  ++next;
350  if (next == _vertex_list.end())
351  {
352  return;
353  }
354  it = next;
355  ++next;
356  if (next == _vertex_list.end())
357  {
358  return;
359  }
360 
361  if (getOrientation(*_pnts[*prev], *_pnts[*it], *_pnts[*next]) ==
362  GeoLib::CCW)
363  {
364  _triangles.emplace_back(_pnts, *prev, *it, *next);
365  }
366  else
367  {
368  _triangles.emplace_back(_pnts, *prev, *next, *it);
369  }
370 }
bool isEar(std::size_t v0, std::size_t v1, std::size_t v2) const
std::list< std::size_t > _convex_vertex_list
void uniquePushBack(Container &container, typename Container::value_type const &element)
Definition: Algorithm.h:245
Orientation getOrientation(MathLib::Point3d const &p0, MathLib::Point3d const &p1, MathLib::Point3d const &p2)

References _convex_vertex_list, _ear_list, _pnts, _triangles, _vertex_list, GeoLib::CCW, 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 75 of file EarClippingTriangulation.cpp.

76 {
77  // copy points - last point is identical to the first
78  std::size_t n_pnts(polygon.getNumberOfPoints() - 1);
79  for (std::size_t k(0); k < n_pnts; k++)
80  {
81  _pnts.push_back(new GeoLib::Point(*(polygon.getPoint(k))));
82  }
83 }

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

Referenced by EarClippingTriangulation().

◆ ensureCWOrientation()

void GeoLib::EarClippingTriangulation::ensureCWOrientation ( )
inlineprivate

Definition at line 85 of file EarClippingTriangulation.cpp.

86 {
87  std::size_t n_pnts(_pnts.size());
88  // get the left most upper point
89  std::size_t min_x_max_y_idx(0); // for orientation check
90  for (std::size_t k(0); k < n_pnts; k++)
91  {
92  if ((*(_pnts[k]))[0] <= (*(_pnts[min_x_max_y_idx]))[0])
93  {
94  if ((*(_pnts[k]))[0] < (*(_pnts[min_x_max_y_idx]))[0])
95  {
96  min_x_max_y_idx = k;
97  }
98  else
99  {
100  if ((*(_pnts[k]))[1] > (*(_pnts[min_x_max_y_idx]))[1])
101  {
102  min_x_max_y_idx = k;
103  }
104  }
105  }
106  }
107  // determine orientation
108  if (0 < min_x_max_y_idx && min_x_max_y_idx < n_pnts - 1)
109  {
111  GeoLib::getOrientation(*_pnts[min_x_max_y_idx - 1],
112  *_pnts[min_x_max_y_idx],
113  *_pnts[min_x_max_y_idx + 1]);
114  }
115  else
116  {
117  if (0 == min_x_max_y_idx)
118  {
120  *_pnts[n_pnts - 1], *_pnts[0], *_pnts[1]);
121  }
122  else
123  {
125  *_pnts[n_pnts - 2], *_pnts[n_pnts - 1], *_pnts[0]);
126  }
127  }
129  {
130  // switch orientation
131  for (std::size_t k(0); k < n_pnts / 2; k++)
132  {
133  std::swap(_pnts[k], _pnts[n_pnts - 1 - k]);
134  }
135  }
136 }

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

Referenced by EarClippingTriangulation().

◆ initLists()

void GeoLib::EarClippingTriangulation::initLists ( )
inlineprivate

Definition at line 161 of file EarClippingTriangulation.cpp.

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

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

156 {
157  _vertex_list.resize(_pnts.size());
158  std::iota(begin(_vertex_list), end(_vertex_list), 0);
159 }

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

140 {
141  for (auto const& v : _vertex_list)
142  {
143  if (v != v0 && v != v1 && v != v2)
144  {
145  if (MathLib::isPointInTriangle(*_pnts[v], *_pnts[v0], *_pnts[v1],
146  *_pnts[v2]))
147  {
148  return false;
149  }
150  }
151  }
152  return true;
153 }
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)
static const double v

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

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 53 of file EarClippingTriangulation.h.

Referenced by clipEars(), and initLists().

◆ _ear_list

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

Definition at line 54 of file EarClippingTriangulation.h.

Referenced by clipEars(), and initLists().

◆ _original_orientation

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

Definition at line 61 of file EarClippingTriangulation.h.

Referenced by EarClippingTriangulation(), and ensureCWOrientation().

◆ _pnts

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

◆ _triangles

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

triangles of the triangulation (maybe in the wrong orientation)

Definition at line 59 of file EarClippingTriangulation.h.

Referenced by EarClippingTriangulation(), and clipEars().

◆ _vertex_list

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

Definition at line 52 of file EarClippingTriangulation.h.

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


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