OGS
EarClippingTriangulation.cpp
Go to the documentation of this file.
1 
16 
17 #include <numeric>
18 
19 #include "BaseLib/Algorithm.h"
21 #include "Point.h"
22 #include "Polygon.h"
23 #include "Triangle.h"
24 
25 namespace GeoLib
26 {
28  GeoLib::Polygon const& polygon, std::list<GeoLib::Triangle>& triangles,
29  bool rot)
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 }
66 
68 {
69  for (auto p : _pnts)
70  {
71  delete p;
72  }
73 }
74 
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 }
84 
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 }
137 
138 bool EarClippingTriangulation::isEar(std::size_t v0, std::size_t v1,
139  std::size_t v2) const
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 }
154 
156 {
157  _vertex_list.resize(_pnts.size());
158  std::iota(begin(_vertex_list), end(_vertex_list), 0);
159 }
160 
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 }
206 
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 }
371 
372 } // end namespace GeoLib
Definition of the EarClippingTriangulation class.
void WARN(char const *fmt, Args const &... args)
Definition: Logging.h:37
Definition of the Polygon class.
bool isEar(std::size_t v0, std::size_t v1, std::size_t v2) const
std::vector< GeoLib::Point * > _pnts
EarClippingTriangulation(GeoLib::Polygon const &polygon, std::list< GeoLib::Triangle > &triangles, bool rot=true)
std::list< std::size_t > _convex_vertex_list
void copyPolygonPoints(GeoLib::Polygon const &polygon)
std::list< GeoLib::Triangle > _triangles
std::size_t getPointID(std::size_t i) const
Definition: Polyline.cpp:160
std::size_t getNumberOfPoints() const
Definition: Polyline.cpp:109
const Point * getPoint(std::size_t i) const
returns the i-th point contained in the polyline
Definition: Polyline.cpp:186
std::vector< Point * > const & getPointsVec() const
Definition: Polyline.cpp:192
void uniquePushBack(Container &container, typename Container::value_type const &element)
Definition: Algorithm.h:245
Eigen::Matrix3d rotatePointsToXY(InputIterator1 p_pnts_begin, InputIterator1 p_pnts_end, InputIterator2 r_pnts_begin, InputIterator2 r_pnts_end)
Orientation getOrientation(MathLib::Point3d const &p0, MathLib::Point3d const &p1, MathLib::Point3d const &p2)
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
static const double t