10#ifndef CDT_obwOaxOTdAWcLNTlNnaq
11#define CDT_obwOaxOTdAWcLNTlNnaq
13#ifdef CDT_DONT_USE_BOOST_RTREE
15typedef char CDT_DONT_USE_BOOST_RTREE__was__replaced__with__CDT_USE_BOOST[-1];
21#if __cplusplus >= 201103L || (defined(_MSC_VER) && _MSC_VER >= 1900)
22#define CDT_CXX11_IS_SUPPORTED
23#elif !defined(__cplusplus) && !defined(_MSC_VER)
30#ifdef CDT_USE_AS_COMPILED_LIBRARY
31#define CDT_INLINE_IF_HEADER_ONLY
32#include "cdt_export.h"
38#define CDT_INLINE_IF_HEADER_ONLY inline
49#ifdef CDT_USE_STRONG_TYPING
50#include <boost/serialization/strong_typedef.hpp>
54#ifdef CDT_CXX11_IS_SUPPORTED
60#include <unordered_map>
61#include <unordered_set>
63#ifdef CDT_DISABLE_EXCEPTIONS
75using std::unordered_map;
76using std::unordered_set;
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>
90using boost::make_tuple;
93using boost::unordered_map;
94using boost::unordered_set;
97std::string to_string(
const T& value)
99 return boost::lexical_cast<std::string>(value);
108void handleException(
const T& error)
110#ifdef CDT_DISABLE_EXCEPTIONS
119array<T, 3>
arr3(
const T& v0,
const T& v1,
const T& v2)
121 const array<T, 3> out = {v0, v1, v2};
119array<T, 3>
arr3(
const T& v0,
const T& v1,
const T& v2) {
…}
129 const array<T, 3> out = {v, v, v};
171 return lhs.
x == rhs.
x && lhs.
y == rhs.
y;
174#ifdef CDT_USE_64_BIT_INDEX_TYPE
175typedef unsigned long long IndexSizeType;
177typedef unsigned int IndexSizeType;
180#ifdef CDT_USE_STRONG_TYPING
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);
222 :
min(std::numeric_limits<T>::
max(), std::numeric_limits<T>::
max())
223 ,
max(-std::numeric_limits<T>::
max(), -std::numeric_limits<T>::
max())
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);
244 typename TVertexIter,
245 typename TGetVertexCoordX,
246 typename TGetVertexCoordY>
250 TGetVertexCoordX getX,
251 TGetVertexCoordY getY)
253 for(; first != last; ++first)
275 iV1 < iV2 ? std::make_pair(iV1, iV2) : std::make_pair(iV2, iV1))
281 return m_vertices == other.m_vertices;
293 return m_vertices.first;
299 return m_vertices.second;
303 const std::pair<VertInd, VertInd>&
verts()
const
303 const std::pair<VertInd, VertInd>&
verts()
const {
…}
309 std::pair<VertInd, VertInd> m_vertices;
327 return Edge(iV1, iV2);
439CDT_EXPORT T
orient2D(
const V2d<T>& p,
const V2d<T>& v1,
const V2d<T>& v2);
447 T orientationTolerance = T(0));
469CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY
Index
473CDT_INLINE_IF_HEADER_ONLY
Index
477CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY
Index
481CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY
Index
485CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY
TriInd
489CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY
TriInd
493CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY
VertInd
505CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY
bool
510CDT_EXPORT T
distance(
const V2d<T>& a,
const V2d<T>& b);
520#ifndef CDT_USE_AS_COMPILED_LIBRARY
527#ifdef CDT_CXX11_IS_SUPPORTED
534#ifdef CDT_USE_STRONG_TYPING
543 return std::hash<std::size_t>()(vi.t);
554 return std::hash<std::size_t>()(vi.t);
571 static void hashCombine(std::size_t& seed,
const CDT::VertInd& key)
573#ifdef CDT_CXX11_IS_SUPPORTED
574 typedef std::hash<CDT::VertInd> Hasher;
576 typedef boost::hash<CDT::VertInd> Hasher;
578 seed ^= Hasher()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
581 static std::size_t hashEdge(
const CDT::Edge& e)
584 hashCombine(seed, e.
v1());
585 hashCombine(seed, e.
v2());
char couldnt_parse_cxx_standard[-1]
Error: couldn't parse standard.
Utilities and helpers - implementation.
Namespace containing triangulation functionality.
std::vector< Edge > EdgeVec
Vector of edges.
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.
unordered_set< Edge > EdgeUSet
Hash table of edges.
VertInd edge_get_v2(const Edge &e)
Get edge second vertex.
std::vector< TriInd > TriIndVec
Vector of triangle indices.
CDT_INLINE_IF_HEADER_ONLY Index edgeNeighborInd(const VerticesArr3 &vv, VertInd iVedge1, VertInd iVedge2)
Index of triangle's neighbor opposed to an edge.
VertInd edge_get_v1(const Edge &e)
Get edge first vertex.
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opposedTriangleInd(const VerticesArr3 &vv, VertInd iVert)
Index of triangle's neighbor opposed to a vertex.
CDT_EXPORT PtLineLocation::Enum classifyOrientation(T orientation, T orientationTolerance=T(0))
Classify value of orient2d predicate.
array< TriInd, 3 > NeighborsArr3
array of three neighbors
CDT_EXPORT T distance(const V2d< T > &a, const V2d< T > &b)
Distance between two 2D points.
IndexSizeType VertInd
Vertex index.
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.
CDT_EXPORT Index cw(Index i)
Advance vertex or neighbor index clockwise.
array< VertInd, 3 > VerticesArr3
array of three vertex indices
CDT_INLINE_IF_HEADER_ONLY bool touchesSuperTriangle(const Triangle &t)
Check if any of triangle's vertices belongs to a super-triangle.
array< T, 3 > arr3(const T &v0, const T &v1, const T &v2)
Needed for c++03 compatibility (no uniform initialization available)
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoVrt(Index neighborIndex)
Opposed vertex index from neighbor index.
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index opoNbr(Index vertIndex)
Opposed neighbor index from vertex index.
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index vertexInd(const VerticesArr3 &vv, VertInd iV)
If triangle has a given vertex return vertex-index.
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.
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.
CDT_EXPORT T distanceSquared(const V2d< T > &a, const V2d< T > &b)
Squared distance between two 2D points.
unordered_set< TriInd > TriIndUSet
Hash table of triangles.
CDT_EXPORT Index ccw(Index i)
Advance vertex or neighbor index counter-clockwise.
Edge edge_make(VertInd iV1, VertInd iV2)
Get edge second vertex.
CDT_EXPORT Index edgeNeighbor(PtTriLocation::Enum location)
Neighbor index from a on-edge location.
unordered_map< TriInd, TriInd > TriIndUMap
Triangle hash map.
const T & getX_V2d(const V2d< T > &v)
X- coordinate getter for V2d.
bool operator==(const CDT::V2d< T > &lhs, const CDT::V2d< T > &rhs)
If two 2D vectors are exactly equal.
unsigned char Index
Index in triangle.
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd opposedTriangle(const Triangle &tri, VertInd iVert)
Given triangle and a vertex find opposed triangle.
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.
CDT_EXPORT bool isOnEdge(PtTriLocation::Enum location)
Check if location is classified as on any of three edges.
IndexSizeType TriInd
Triangle index.
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.
std::vector< Triangle > TriangleVec
Vector of triangles.
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.
const T & getY_V2d(const V2d< T > &v)
Y-coordinate getter for V2d.
Box2d< T > & envelopPoint(const T x, const T y)
Envelop box around a point with given coordinates.
Box2d()
Box that doesn't contain any point.
V2d< T > max
max box corner
Box2d< T > & envelopPoint(const V2d< T > &p)
Envelop box around a point.
Box2d< T > & envelopPoints(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Envelop box around a collection of custom points.
V2d< T > min
min box corner
Box2d< T > & envelopPoints(const std::vector< V2d< T > > &vertices)
Envelop box around a collection of points.
Edge connecting two vertices: vertex with smaller index is always first.
const std::pair< VertInd, VertInd > & verts() const
Edges' vertices.
bool operator==(const Edge &other) const
Equals operator.
VertInd v1() const
V1 getter.
bool operator!=(const Edge &other) const
Not-equals operator.
Edge(const VertInd iV1, const VertInd iV2)
Constructor.
VertInd v2() const
V2 getter.
Relative location of point to a line.
Location of point on a triangle.
VerticesArr3 vertices
triangle's three vertices
std::pair< TriInd, VertInd > prev(const VertInd i) const
Previous triangle adjacent to a vertex (counter-clockwise)
NeighborsArr3 neighbors
triangle's three neighbors
bool containsVertex(const VertInd i) const
Check if triangle contains a vertex.
Triangle(const VerticesArr3 &vertices, const NeighborsArr3 &neighbors)
Triangle with given vertices and neighbors.
Triangle()
Triangle with no vertices and no neighbors.
std::pair< TriInd, VertInd > next(const VertInd i) const
Next triangle adjacent to a vertex (clockwise)
V2d(const T x, const T y)
Vertex with given coordinates.
V2d()
Vertex with zero coordinates.
std::size_t operator()(const CDT::Edge &e) const
Hash operator.
std::size_t operator()(const CDT::TriInd &vi) const
Hash operator.
std::size_t operator()(const CDT::VertInd &vi) const
Hash operator.