CDT  1.4.2
C++ library for constrained Delaunay triangulation
 
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Modules Pages
Loading...
Searching...
No Matches
CDTUtils.h
Go to the documentation of this file.
1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
9
10#ifndef CDT_obwOaxOTdAWcLNTlNnaq
11#define CDT_obwOaxOTdAWcLNTlNnaq
12
13#ifdef CDT_DONT_USE_BOOST_RTREE
14// CDT_DONT_USE_BOOST_RTREE was replaced with CDT_USE_BOOST
15typedef char CDT_DONT_USE_BOOST_RTREE__was__replaced__with__CDT_USE_BOOST[-1];
16#endif
17
18// #define CDT_USE_STRONG_TYPING // strong type checks on indices
19
20// check if c++11 is supported
21#if __cplusplus >= 201103L || (defined(_MSC_VER) && _MSC_VER >= 1900)
22#define CDT_CXX11_IS_SUPPORTED
23#elif !defined(__cplusplus) && !defined(_MSC_VER)
25#endif
26
27// Functions defined outside the class need to be 'inline'
28// if CDT is configured to be used as header-only library:
29// single-definition rule is violated otherwise
30#ifdef CDT_USE_AS_COMPILED_LIBRARY
31#define CDT_INLINE_IF_HEADER_ONLY
32#include "cdt_export.h" // automatically generated by CMake
33#else
38#define CDT_INLINE_IF_HEADER_ONLY inline
40#define CDT_EXPORT
41#endif
42
43#include <algorithm>
44#include <cassert>
45#include <cmath>
46#include <limits>
47#include <vector>
48
49#ifdef CDT_USE_STRONG_TYPING
50#include <boost/serialization/strong_typedef.hpp>
51#endif
52
53// use fall-backs for c++11 features
54#ifdef CDT_CXX11_IS_SUPPORTED
55
56#include <array>
57#include <functional>
58#include <string>
59#include <tuple>
60#include <unordered_map>
61#include <unordered_set>
62
63#ifdef CDT_DISABLE_EXCEPTIONS
64#include <exception>
65#endif
66
67namespace CDT
68{
69using std::array;
70using std::get;
71using std::make_tuple;
72using std::tie;
73using std::to_string;
74using std::tuple;
75using std::unordered_map;
76using std::unordered_set;
77} // namespace CDT
78
79#else
80#include <boost/array.hpp>
81#include <boost/functional/hash.hpp>
82#include <boost/lexical_cast.hpp>
83#include <boost/tuple/tuple.hpp>
84#include <boost/unordered_map.hpp>
85#include <boost/unordered_set.hpp>
86namespace CDT
87{
88using boost::array;
89using boost::get;
90using boost::make_tuple;
91using boost::tie;
92using boost::tuple;
93using boost::unordered_map;
94using boost::unordered_set;
95
96template <typename T>
97std::string to_string(const T& value)
98{
99 return boost::lexical_cast<std::string>(value);
100}
101} // namespace CDT
102#endif
103
104namespace CDT
105{
106
107template <typename T>
108void handleException(const T& error)
109{
110#ifdef CDT_DISABLE_EXCEPTIONS
111 std::terminate();
112#else
113 throw error;
114#endif
115}
116
118template <typename T>
119array<T, 3> arr3(const T& v0, const T& v1, const T& v2)
120{
121 const array<T, 3> out = {v0, v1, v2};
122 return out;
123}
124
126template <typename T>
127array<T, 3> arr3(const T& v)
128{
129 const array<T, 3> out = {v, v, v};
130 return out;
131}
132
134template <typename T>
135struct CDT_EXPORT V2d
136{
137 T x;
138 T y;
139
142 : x(T(0))
143 , y(T(0))
144 {}
145
147 V2d(const T x, const T y)
148 : x(x)
149 , y(y)
150 {}
151};
152
154template <typename T>
155const T& getX_V2d(const V2d<T>& v)
156{
157 return v.x;
158}
159
161template <typename T>
162const T& getY_V2d(const V2d<T>& v)
163{
164 return v.y;
165}
166
168template <typename T>
169bool operator==(const CDT::V2d<T>& lhs, const CDT::V2d<T>& rhs)
170{
171 return lhs.x == rhs.x && lhs.y == rhs.y;
172}
173
174#ifdef CDT_USE_64_BIT_INDEX_TYPE
175typedef unsigned long long IndexSizeType;
176#else
177typedef unsigned int IndexSizeType;
178#endif
179
180#ifdef CDT_USE_STRONG_TYPING
186BOOST_STRONG_TYPEDEF(IndexSizeType, TriInd);
187#else
189typedef unsigned char Index;
191typedef IndexSizeType VertInd;
193typedef IndexSizeType TriInd;
194#endif
195
197const static Index invalidIndex(std::numeric_limits<Index>::max());
199const static IndexSizeType
200 invalidIndexSizeType(std::numeric_limits<IndexSizeType>::max());
203const static IndexSizeType nSuperTriangleVertices(3);
205const static TriInd noNeighbor(invalidIndexSizeType);
207const static VertInd noVertex(invalidIndexSizeType);
208
209typedef std::vector<TriInd> TriIndVec;
210typedef array<VertInd, 3> VerticesArr3;
211typedef array<TriInd, 3> NeighborsArr3;
212
214template <typename T>
215struct CDT_EXPORT Box2d
216{
219
222 : min(std::numeric_limits<T>::max(), std::numeric_limits<T>::max())
223 , max(-std::numeric_limits<T>::max(), -std::numeric_limits<T>::max())
224 {}
225
228 {
229 return envelopPoint(p.x, p.y);
230 }
231
233 Box2d<T>& envelopPoint(const T x, const T y)
234 {
235 min.x = std::min(x, min.x);
236 max.x = std::max(x, max.x);
237 min.y = std::min(y, min.y);
238 max.y = std::max(y, max.y);
239 return *this;
240 }
241
243 template <
244 typename TVertexIter,
245 typename TGetVertexCoordX,
246 typename TGetVertexCoordY>
248 TVertexIter first,
249 TVertexIter last,
250 TGetVertexCoordX getX,
251 TGetVertexCoordY getY)
252 {
253 for(; first != last; ++first)
254 {
255 envelopPoint(getX(*first), getY(*first));
256 }
257 return *this;
258 }
259
261 Box2d<T>& envelopPoints(const std::vector<V2d<T> >& vertices)
262 {
263 return envelopPoints(
264 vertices.begin(), vertices.end(), getX_V2d<T>, getY_V2d<T>);
265 }
266};
267
270struct CDT_EXPORT Edge
271{
273 Edge(const VertInd iV1, const VertInd iV2)
274 : m_vertices(
275 iV1 < iV2 ? std::make_pair(iV1, iV2) : std::make_pair(iV2, iV1))
276 {}
277
279 bool operator==(const Edge& other) const
280 {
281 return m_vertices == other.m_vertices;
282 }
283
285 bool operator!=(const Edge& other) const
286 {
287 return !(this->operator==(other));
288 }
289
291 VertInd v1() const
292 {
293 return m_vertices.first;
294 }
295
297 VertInd v2() const
298 {
299 return m_vertices.second;
300 }
301
303 const std::pair<VertInd, VertInd>& verts() const
304 {
305 return m_vertices;
306 }
307
308private:
309 std::pair<VertInd, VertInd> m_vertices;
310};
311
313inline VertInd edge_get_v1(const Edge& e)
314{
315 return e.v1();
316}
317
319inline VertInd edge_get_v2(const Edge& e)
320{
321 return e.v2();
322}
323
326{
327 return Edge(iV1, iV2);
328}
329
330typedef std::vector<Edge> EdgeVec;
331typedef unordered_set<Edge> EdgeUSet;
332typedef unordered_set<TriInd> TriIndUSet;
333typedef unordered_map<TriInd, TriInd> TriIndUMap;
334
336/*
337 * v3
338 * /\
339 * n3/ \n2
340 * /____\
341 * v1 n1 v2
342 */
343struct CDT_EXPORT Triangle
344{
347
350 : vertices(arr3(noVertex))
351 , neighbors(arr3(noNeighbor))
352 {}
353
359
362 std::pair<TriInd, VertInd> next(const VertInd i) const
363 {
364 assert(vertices[0] == i || vertices[1] == i || vertices[2] == i);
365 if(vertices[0] == i)
366 {
367 return std::make_pair(neighbors[0], vertices[1]);
368 }
369 if(vertices[1] == i)
370 {
371 return std::make_pair(neighbors[1], vertices[2]);
372 }
373 return std::make_pair(neighbors[2], vertices[0]);
374 }
375
378 std::pair<TriInd, VertInd> prev(const VertInd i) const
379 {
380 assert(vertices[0] == i || vertices[1] == i || vertices[2] == i);
381 if(vertices[0] == i)
382 return std::make_pair(neighbors[2], vertices[2]);
383 if(vertices[1] == i)
384 return std::make_pair(neighbors[0], vertices[0]);
385 return std::make_pair(neighbors[1], vertices[1]);
386 }
387
389 bool containsVertex(const VertInd i) const
390 {
391 return std::find(vertices.begin(), vertices.end(), i) != vertices.end();
392 }
393};
394
395typedef std::vector<Triangle> TriangleVec;
396
398CDT_EXPORT Index ccw(Index i);
399
401CDT_EXPORT Index cw(Index i);
402
404struct CDT_EXPORT PtTriLocation
405{
407 enum Enum
408 {
409 Inside,
410 Outside,
411 OnEdge1,
412 OnEdge2,
413 OnEdge3,
414 OnVertex,
415 };
416};
417
419CDT_EXPORT bool isOnEdge(PtTriLocation::Enum location);
420
423CDT_EXPORT Index edgeNeighbor(PtTriLocation::Enum location);
424
426struct CDT_EXPORT PtLineLocation
427{
429 enum Enum
430 {
431 Left,
432 Right,
433 OnLine,
434 };
435};
436
438template <typename T>
439CDT_EXPORT T orient2D(const V2d<T>& p, const V2d<T>& v1, const V2d<T>& v2);
440
442template <typename T>
444 const V2d<T>& p,
445 const V2d<T>& v1,
446 const V2d<T>& v2,
447 T orientationTolerance = T(0));
448
450template <typename T>
451CDT_EXPORT PtLineLocation::Enum
452classifyOrientation(T orientation, T orientationTolerance = T(0));
453
455template <typename T>
457 const V2d<T>& p,
458 const V2d<T>& v1,
459 const V2d<T>& v2,
460 const V2d<T>& v3);
461
463CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoNbr(Index vertIndex);
464
466CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoVrt(Index neighborIndex);
467
469CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index
470opposedTriangleInd(const VerticesArr3& vv, VertInd iVert);
471
473CDT_INLINE_IF_HEADER_ONLY Index
474edgeNeighborInd(const VerticesArr3& vv, VertInd iVedge1, VertInd iVedge2);
475
477CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index
478opposedVertexInd(const NeighborsArr3& nn, TriInd iTopo);
479
481CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index
482vertexInd(const VerticesArr3& vv, VertInd iV);
483
485CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd
486opposedTriangle(const Triangle& tri, VertInd iVert);
487
489CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd
490edgeNeighbor(const Triangle& tri, VertInd iVedge1, VertInd iVedge2);
491
493CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY VertInd
494opposedVertex(const Triangle& tri, TriInd iTopo);
495
497template <typename T>
498CDT_EXPORT bool isInCircumcircle(
499 const V2d<T>& p,
500 const V2d<T>& v1,
501 const V2d<T>& v2,
502 const V2d<T>& v3);
503
505CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY bool
506verticesShareEdge(const TriIndVec& aTris, const TriIndVec& bTris);
507
509template <typename T>
510CDT_EXPORT T distance(const V2d<T>& a, const V2d<T>& b);
511
513template <typename T>
514CDT_EXPORT T distanceSquared(const V2d<T>& a, const V2d<T>& b);
515
517CDT_INLINE_IF_HEADER_ONLY bool touchesSuperTriangle(const Triangle& t);
518} // namespace CDT
519
520#ifndef CDT_USE_AS_COMPILED_LIBRARY
521#include "CDTUtils.hpp"
522#endif
523
524//*****************************************************************************
525// Specialize hash functions
526//*****************************************************************************
527#ifdef CDT_CXX11_IS_SUPPORTED
528namespace std
529#else
530namespace boost
531#endif
532{
533
534#ifdef CDT_USE_STRONG_TYPING
535
537template <>
538struct hash<CDT::VertInd>
539{
541 std::size_t operator()(const CDT::VertInd& vi) const
542 {
543 return std::hash<std::size_t>()(vi.t);
544 }
545};
546
548template <>
549struct hash<CDT::TriInd>
550{
552 std::size_t operator()(const CDT::TriInd& vi) const
553 {
554 return std::hash<std::size_t>()(vi.t);
555 }
556};
557
558#endif // CDT_USE_STRONG_TYPING
559
561template <>
562struct hash<CDT::Edge>
563{
565 std::size_t operator()(const CDT::Edge& e) const
566 {
567 return hashEdge(e);
568 }
569
570private:
571 static void hashCombine(std::size_t& seed, const CDT::VertInd& key)
572 {
573#ifdef CDT_CXX11_IS_SUPPORTED
574 typedef std::hash<CDT::VertInd> Hasher;
575#else
576 typedef boost::hash<CDT::VertInd> Hasher;
577#endif
578 seed ^= Hasher()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
579 }
580
581 static std::size_t hashEdge(const CDT::Edge& e)
582 {
583 std::size_t seed(0);
584 hashCombine(seed, e.v1());
585 hashCombine(seed, e.v2());
586 return seed;
587 }
588};
589
590} // namespace std/boost
591
592#endif // header guard
char couldnt_parse_cxx_standard[-1]
Error: couldn't parse standard.
Definition CDTUtils.h:24
Utilities and helpers - implementation.
Namespace containing triangulation functionality.
std::vector< Edge > EdgeVec
Vector of edges.
Definition CDTUtils.h:330
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY VertInd opposedVertex(const Triangle &tri, TriInd iTopo)
Given two triangles, return vertex of first triangle opposed to the second.
Definition CDTUtils.hpp:201
unordered_set< Edge > EdgeUSet
Hash table of edges.
Definition CDTUtils.h:331
VertInd edge_get_v2(const Edge &e)
Get edge second vertex.
Definition CDTUtils.h:319
std::vector< TriInd > TriIndVec
Vector of triangle indices.
Definition CDTUtils.h:209
CDT_INLINE_IF_HEADER_ONLY Index edgeNeighborInd(const VerticesArr3 &vv, VertInd iVedge1, VertInd iVedge2)
Index of triangle's neighbor opposed to an edge.
Definition CDTUtils.hpp:139
VertInd edge_get_v1(const Edge &e)
Get edge first vertex.
Definition CDTUtils.h:313
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opposedTriangleInd(const VerticesArr3 &vv, VertInd iVert)
Index of triangle's neighbor opposed to a vertex.
Definition CDTUtils.hpp:129
CDT_EXPORT PtLineLocation::Enum classifyOrientation(T orientation, T orientationTolerance=T(0))
Classify value of orient2d predicate.
Definition CDTUtils.hpp:60
array< TriInd, 3 > NeighborsArr3
array of three neighbors
Definition CDTUtils.h:211
CDT_EXPORT T distance(const V2d< T > &a, const V2d< T > &b)
Distance between two 2D points.
Definition CDTUtils.hpp:248
IndexSizeType VertInd
Vertex index.
Definition CDTUtils.h:191
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY bool verticesShareEdge(const TriIndVec &aTris, const TriIndVec &bTris)
Test if two vertices share at least one common triangle.
Definition CDTUtils.hpp:225
CDT_EXPORT Index cw(Index i)
Advance vertex or neighbor index clockwise.
Definition CDTUtils.hpp:24
array< VertInd, 3 > VerticesArr3
array of three vertex indices
Definition CDTUtils.h:210
CDT_INLINE_IF_HEADER_ONLY bool touchesSuperTriangle(const Triangle &t)
Check if any of triangle's vertices belongs to a super-triangle.
Definition CDTUtils.hpp:259
array< T, 3 > arr3(const T &v0, const T &v1, const T &v2)
Needed for c++03 compatibility (no uniform initialization available)
Definition CDTUtils.h:119
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoVrt(Index neighborIndex)
Opposed vertex index from neighbor index.
Definition CDTUtils.hpp:115
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoNbr(Index vertIndex)
Opposed neighbor index from vertex index.
Definition CDTUtils.hpp:102
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index vertexInd(const VerticesArr3 &vv, VertInd iV)
If triangle has a given vertex return vertex-index.
Definition CDTUtils.hpp:184
CDT_EXPORT T orient2D(const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2)
Orient p against line v1-v2 2D: robust geometric predicate.
Definition CDTUtils.hpp:43
CDT_EXPORT PtLineLocation::Enum locatePointLine(const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, T orientationTolerance=T(0))
Check if point lies to the left of, to the right of, or on a line.
Definition CDTUtils.hpp:49
CDT_EXPORT T distanceSquared(const V2d< T > &a, const V2d< T > &b)
Squared distance between two 2D points.
Definition CDTUtils.hpp:254
unordered_set< TriInd > TriIndUSet
Hash table of triangles.
Definition CDTUtils.h:332
CDT_EXPORT Index ccw(Index i)
Advance vertex or neighbor index counter-clockwise.
Definition CDTUtils.hpp:19
Edge edge_make(VertInd iV1, VertInd iV2)
Get edge second vertex.
Definition CDTUtils.h:325
CDT_EXPORT Index edgeNeighbor(PtTriLocation::Enum location)
Neighbor index from a on-edge location.
Definition CDTUtils.hpp:36
unordered_map< TriInd, TriInd > TriIndUMap
Triangle hash map.
Definition CDTUtils.h:333
const T & getX_V2d(const V2d< T > &v)
X- coordinate getter for V2d.
Definition CDTUtils.h:155
bool operator==(const CDT::V2d< T > &lhs, const CDT::V2d< T > &rhs)
If two 2D vectors are exactly equal.
Definition CDTUtils.h:169
unsigned char Index
Index in triangle.
Definition CDTUtils.h:189
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd opposedTriangle(const Triangle &tri, VertInd iVert)
Given triangle and a vertex find opposed triangle.
Definition CDTUtils.hpp:195
CDT_EXPORT bool isInCircumcircle(const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, const V2d< T > &v3)
Test if point lies in a circumscribed circle of a triangle.
Definition CDTUtils.hpp:214
CDT_EXPORT bool isOnEdge(PtTriLocation::Enum location)
Check if location is classified as on any of three edges.
Definition CDTUtils.hpp:29
IndexSizeType TriInd
Triangle index.
Definition CDTUtils.h:193
CDT_EXPORT PtTriLocation::Enum locatePointTriangle(const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, const V2d< T > &v3)
Check if point a lies inside of, outside of, or on an edge of a triangle.
Definition CDTUtils.hpp:70
std::vector< Triangle > TriangleVec
Vector of triangles.
Definition CDTUtils.h:395
BOOST_STRONG_TYPEDEF(unsigned char, Index)
Index in triangle.
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opposedVertexInd(const NeighborsArr3 &nn, TriInd iTopo)
Index of triangle's vertex opposed to a triangle.
Definition CDTUtils.hpp:173
const T & getY_V2d(const V2d< T > &v)
Y-coordinate getter for V2d.
Definition CDTUtils.h:162
Box2d< T > & envelopPoint(const T x, const T y)
Envelop box around a point with given coordinates.
Definition CDTUtils.h:233
Box2d()
Box that doesn't contain any point.
Definition CDTUtils.h:221
V2d< T > max
max box corner
Definition CDTUtils.h:218
Box2d< T > & envelopPoint(const V2d< T > &p)
Envelop box around a point.
Definition CDTUtils.h:227
Box2d< T > & envelopPoints(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Envelop box around a collection of custom points.
Definition CDTUtils.h:247
V2d< T > min
min box corner
Definition CDTUtils.h:217
Box2d< T > & envelopPoints(const std::vector< V2d< T > > &vertices)
Envelop box around a collection of points.
Definition CDTUtils.h:261
Edge connecting two vertices: vertex with smaller index is always first.
Definition CDTUtils.h:271
const std::pair< VertInd, VertInd > & verts() const
Edges' vertices.
Definition CDTUtils.h:303
bool operator==(const Edge &other) const
Equals operator.
Definition CDTUtils.h:279
VertInd v1() const
V1 getter.
Definition CDTUtils.h:291
bool operator!=(const Edge &other) const
Not-equals operator.
Definition CDTUtils.h:285
Edge(const VertInd iV1, const VertInd iV2)
Constructor.
Definition CDTUtils.h:273
VertInd v2() const
V2 getter.
Definition CDTUtils.h:297
Relative location of point to a line.
Definition CDTUtils.h:427
Location of point on a triangle.
Definition CDTUtils.h:405
VerticesArr3 vertices
triangle's three vertices
Definition CDTUtils.h:345
std::pair< TriInd, VertInd > prev(const VertInd i) const
Previous triangle adjacent to a vertex (counter-clockwise)
Definition CDTUtils.h:378
NeighborsArr3 neighbors
triangle's three neighbors
Definition CDTUtils.h:346
bool containsVertex(const VertInd i) const
Check if triangle contains a vertex.
Definition CDTUtils.h:389
Triangle(const VerticesArr3 &vertices, const NeighborsArr3 &neighbors)
Triangle with given vertices and neighbors.
Definition CDTUtils.h:355
Triangle()
Triangle with no vertices and no neighbors.
Definition CDTUtils.h:349
std::pair< TriInd, VertInd > next(const VertInd i) const
Next triangle adjacent to a vertex (clockwise)
Definition CDTUtils.h:362
2D vector
Definition CDTUtils.h:136
V2d(const T x, const T y)
Vertex with given coordinates.
Definition CDTUtils.h:147
V2d()
Vertex with zero coordinates.
Definition CDTUtils.h:141
std::size_t operator()(const CDT::Edge &e) const
Hash operator.
Definition CDTUtils.h:565
std::size_t operator()(const CDT::TriInd &vi) const
Hash operator.
Definition CDTUtils.h:552
std::size_t operator()(const CDT::VertInd &vi) const
Hash operator.
Definition CDTUtils.h:541