10#ifndef CDT_lNrmUayWQaIR5fxnsg9B
11#define CDT_lNrmUayWQaIR5fxnsg9B
16#include "remove_at.hpp"
90 typename TGetVertexCoordX,
91 typename TGetVertexCoordY>
95 TGetVertexCoordX getX,
96 TGetVertexCoordY getY);
105template <
typename TVertex,
typename TAllocator>
107 std::vector<TVertex, TAllocator>& vertices,
108 const std::vector<std::size_t>& duplicates);
139 typename TGetEdgeVertexStart,
140 typename TGetEdgeVertexEnd,
141 typename TMakeEdgeFromStartAndEnd>
145 const std::vector<std::size_t>& mapping,
146 TGetEdgeVertexStart getStart,
147 TGetEdgeVertexEnd getEnd,
148 TMakeEdgeFromStartAndEnd makeEdge);
158RemapEdges(std::vector<Edge>& edges,
const std::vector<std::size_t>& mapping);
193 typename TGetVertexCoordX,
194 typename TGetVertexCoordY,
195 typename TVertexAllocator,
197 typename TGetEdgeVertexStart,
198 typename TGetEdgeVertexEnd,
199 typename TMakeEdgeFromStartAndEnd>
201 std::vector<TVertex, TVertexAllocator>& vertices,
202 TGetVertexCoordX getX,
203 TGetVertexCoordY getY,
204 TEdgeIter edgesFirst,
206 TGetEdgeVertexStart getStart,
207 TGetEdgeVertexEnd getEnd,
208 TMakeEdgeFromStartAndEnd makeEdge);
219 std::vector<
V2d<T> >& vertices,
220 std::vector<Edge>& edges);
248 const unordered_map<Edge, EdgeVec>& edgeToPieces,
249 const std::vector<
V2d<T> >& vertices);
261#ifdef CDT_CXX11_IS_SUPPORTED
272#ifdef CDT_CXX11_IS_SUPPORTED
273 typedef std::hash<T> Hasher;
275 typedef boost::hash<T> Hasher;
277 return Hasher()(xy.
x) ^ Hasher()(xy.
y);
290 typename TVertexIter,
291 typename TGetVertexCoordX,
292 typename TGetVertexCoordY>
296 TGetVertexCoordX getX,
297 TGetVertexCoordY getY)
299 typedef unordered_map<V2d<T>, std::size_t> PosToIndex;
300 PosToIndex uniqueVerts;
301 const std::size_t verticesSize = std::distance(first, last);
303 std::vector<std::size_t>(verticesSize), std::vector<std::size_t>()};
304 for(std::size_t iIn = 0, iOut = iIn; iIn < verticesSize; ++iIn, ++first)
306 typename PosToIndex::const_iterator it;
308 tie(it, isUnique) = uniqueVerts.insert(
309 std::make_pair(
V2d<T>::make(getX(*first), getY(*first)), iOut));
321template <
typename TVertex,
typename TAllocator>
323 std::vector<TVertex, TAllocator>& vertices,
324 const std::vector<std::size_t>& duplicates)
337 typename TGetEdgeVertexStart,
338 typename TGetEdgeVertexEnd,
339 typename TMakeEdgeFromStartAndEnd>
342 const TEdgeIter last,
343 const std::vector<std::size_t>& mapping,
344 TGetEdgeVertexStart getStart,
345 TGetEdgeVertexEnd getEnd,
346 TMakeEdgeFromStartAndEnd makeEdge)
348 for(; first != last; ++first)
351 static_cast<VertInd>(mapping[getStart(*first)]),
352 static_cast<VertInd>(mapping[getEnd(*first)]));
359 typename TGetVertexCoordX,
360 typename TGetVertexCoordY,
361 typename TVertexAllocator,
363 typename TGetEdgeVertexStart,
364 typename TGetEdgeVertexEnd,
365 typename TMakeEdgeFromStartAndEnd>
367 std::vector<TVertex, TVertexAllocator>& vertices,
368 TGetVertexCoordX getX,
369 TGetVertexCoordY getY,
370 const TEdgeIter edgesFirst,
371 const TEdgeIter edgesLast,
372 TGetEdgeVertexStart getStart,
373 TGetEdgeVertexEnd getEnd,
374 TMakeEdgeFromStartAndEnd makeEdge)
385 const unordered_map<Edge, EdgeVec>& edgeToPieces,
386 const std::vector<
V2d<T> >& vertices)
388 typedef std::pair<VertInd, T> VertCoordPair;
391 bool operator()(
const VertCoordPair& a,
const VertCoordPair& b)
const
393 return a.second < b.second;
397 unordered_map<Edge, std::vector<VertInd> > edgeToSplitVerts;
398 typedef unordered_map<Edge, EdgeVec>::const_iterator It;
399 for(It e2pIt = edgeToPieces.begin(); e2pIt != edgeToPieces.end(); ++e2pIt)
401 const Edge& e = e2pIt->first;
402 const T dX = vertices[e.
v2()].x - vertices[e.
v1()].x;
403 const T dY = vertices[e.
v2()].y - vertices[e.
v1()].y;
404 const bool isX = std::abs(dX) >= std::abs(dY);
405 const bool isAscending =
406 isX ? dX >= 0 : dY >= 0;
407 const EdgeVec& pieces = e2pIt->second;
408 std::vector<VertCoordPair> splitVerts;
410 splitVerts.reserve(pieces.size() + 1);
411 typedef EdgeVec::const_iterator EIt;
412 for(EIt pieceIt = pieces.begin(); pieceIt != pieces.end(); ++pieceIt)
414 const array<VertInd, 2> vv = {pieceIt->v1(), pieceIt->v2()};
415 typedef array<VertInd, 2>::const_iterator VIt;
416 for(VIt v = vv.begin(); v != vv.end(); ++v)
418 const T c = isX ? vertices[*v].x : vertices[*v].y;
419 splitVerts.push_back(std::make_pair(*v, isAscending ? c : -c));
423 std::sort(splitVerts.begin(), splitVerts.end(), comparePred);
426 std::unique(splitVerts.begin(), splitVerts.end()),
428 assert(splitVerts.size() > 2);
429 std::pair<Edge, std::vector<VertInd> > val =
430 std::make_pair(e, std::vector<VertInd>());
431 val.second.reserve(splitVerts.size());
432 typedef typename std::vector<VertCoordPair>::const_iterator SEIt;
433 for(SEIt it = splitVerts.begin() + 1; it != splitVerts.end() - 1; ++it)
435 val.second.push_back(it->first);
437 edgeToSplitVerts.insert(val);
439 return edgeToSplitVerts;
444#ifndef CDT_USE_AS_COMPILED_LIBRARY
#define CDT_EXPORT
Export not needed in header-only mode.
Public API - implementation.
unsigned short LayerDepth
Type used for storing layer depths for triangles.
std::vector< TriIndVec > VerticesTriangles
Triangles by vertex index.
CDT_EXPORT void RemapEdges(TEdgeIter first, TEdgeIter last, const std::vector< std::size_t > &mapping, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd, TMakeEdgeFromStartAndEnd makeEdge)
Remap vertex indices in edges (in-place) using given vertex-index mapping.
CDT_EXPORT unordered_map< Edge, std::vector< VertInd > > EdgeToSplitVertices(const unordered_map< Edge, EdgeVec > &edgeToPieces, const std::vector< V2d< T > > &vertices)
CDT_EXPORT VerticesTriangles calculateTrianglesByVertex(const TriangleVec &triangles, VertInd verticesSize)
Calculate triangles adjacent to vertices (triangles by vertex index)
void RemoveDuplicates(std::vector< TVertex, TAllocator > &vertices, const std::vector< std::size_t > &duplicates)
Remove duplicates in-place from vector of custom points.
DuplicatesInfo RemoveDuplicatesAndRemapEdges(std::vector< TVertex, TVertexAllocator > &vertices, TGetVertexCoordX getX, TGetVertexCoordY getY, TEdgeIter edgesFirst, TEdgeIter edgesLast, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd, TMakeEdgeFromStartAndEnd makeEdge)
Find point duplicates, remove them from vector (in-place) and remap edges (in-place)
CDT_EXPORT EdgeUSet extractEdgesFromTriangles(const TriangleVec &triangles)
Extract all edges of triangles.
CDT_EXPORT unordered_map< Edge, EdgeVec > EdgeToPiecesMapping(const unordered_map< Edge, EdgeVec > &pieceToOriginals)
DuplicatesInfo FindDuplicates(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Find duplicates in given custom point-type range.
Namespace containing triangulation functionality.
std::vector< Edge > EdgeVec
Vector of edges.
unordered_set< Edge > EdgeUSet
Hash table of edges.
IndexSizeType VertInd
Vertex index.
std::vector< Triangle > TriangleVec
Vector of triangles.
Information about removed duplicated vertices.
std::vector< std::size_t > mapping
vertex index mapping
std::vector< std::size_t > duplicates
duplicates' indices
Edge connecting two vertices: vertex with smaller index is always first.
VertInd v2() const
V2 getter.
VertInd v1() const
V1 getter.