CDT  1.4.1
C++ library for constrained Delaunay triangulation
Loading...
Searching...
No Matches
CDT.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
10#ifndef CDT_lNrmUayWQaIR5fxnsg9B
11#define CDT_lNrmUayWQaIR5fxnsg9B
12
13#include "CDTUtils.h"
14#include "Triangulation.h"
15
16#include "remove_at.hpp"
17
18#include <algorithm>
19#include <cassert>
20#include <cstdlib>
21#include <iterator>
22#include <memory>
23#include <stack>
24#include <vector>
25
27namespace CDT
28{
29
34
40typedef unsigned short LayerDepth;
41typedef LayerDepth BoundaryOverlapCount;
42
44typedef std::vector<TriIndVec> VerticesTriangles;
45
50
57CDT_EXPORT VerticesTriangles
58calculateTrianglesByVertex(const TriangleVec& triangles, VertInd verticesSize);
59
67struct CDT_EXPORT DuplicatesInfo
68{
69 std::vector<std::size_t> mapping;
70 std::vector<std::size_t> duplicates;
71};
72
87template <
88 typename T,
89 typename TVertexIter,
90 typename TGetVertexCoordX,
91 typename TGetVertexCoordY>
92DuplicatesInfo FindDuplicates(
93 TVertexIter first,
94 TVertexIter last,
95 TGetVertexCoordX getX,
96 TGetVertexCoordY getY);
97
105template <typename TVertex, typename TAllocator>
106void RemoveDuplicates(
107 std::vector<TVertex, TAllocator>& vertices,
108 const std::vector<std::size_t>& duplicates);
109
117template <typename T>
118CDT_EXPORT DuplicatesInfo RemoveDuplicates(std::vector<V2d<T> >& vertices);
119
137template <
138 typename TEdgeIter,
139 typename TGetEdgeVertexStart,
140 typename TGetEdgeVertexEnd,
141 typename TMakeEdgeFromStartAndEnd>
142CDT_EXPORT void RemapEdges(
143 TEdgeIter first,
144 TEdgeIter last,
145 const std::vector<std::size_t>& mapping,
146 TGetEdgeVertexStart getStart,
147 TGetEdgeVertexEnd getEnd,
148 TMakeEdgeFromStartAndEnd makeEdge);
149
157CDT_EXPORT void
158RemapEdges(std::vector<Edge>& edges, const std::vector<std::size_t>& mapping);
159
190template <
191 typename T,
192 typename TVertex,
193 typename TGetVertexCoordX,
194 typename TGetVertexCoordY,
195 typename TVertexAllocator,
196 typename TEdgeIter,
197 typename TGetEdgeVertexStart,
198 typename TGetEdgeVertexEnd,
199 typename TMakeEdgeFromStartAndEnd>
200DuplicatesInfo RemoveDuplicatesAndRemapEdges(
201 std::vector<TVertex, TVertexAllocator>& vertices,
202 TGetVertexCoordX getX,
203 TGetVertexCoordY getY,
204 TEdgeIter edgesFirst,
205 TEdgeIter edgesLast,
206 TGetEdgeVertexStart getStart,
207 TGetEdgeVertexEnd getEnd,
208 TMakeEdgeFromStartAndEnd makeEdge);
209
217template <typename T>
218CDT_EXPORT DuplicatesInfo RemoveDuplicatesAndRemapEdges(
219 std::vector<V2d<T> >& vertices,
220 std::vector<Edge>& edges);
221
228CDT_EXPORT EdgeUSet extractEdgesFromTriangles(const TriangleVec& triangles);
229
235CDT_EXPORT unordered_map<Edge, EdgeVec>
236EdgeToPiecesMapping(const unordered_map<Edge, EdgeVec>& pieceToOriginals);
237
246template <typename T>
247CDT_EXPORT unordered_map<Edge, std::vector<VertInd> > EdgeToSplitVertices(
248 const unordered_map<Edge, EdgeVec>& edgeToPieces,
249 const std::vector<V2d<T> >& vertices);
250
252
254
255} // namespace CDT
256
257//*****************************************************************************
258// Implementations of template functionlity
259//*****************************************************************************
260// hash for CDT::V2d<T>
261#ifdef CDT_CXX11_IS_SUPPORTED
262namespace std
263#else
264namespace boost
265#endif
266{
267template <typename T>
268struct hash<CDT::V2d<T> >
269{
270 size_t operator()(const CDT::V2d<T>& xy) const
271 {
272#ifdef CDT_CXX11_IS_SUPPORTED
273 typedef std::hash<T> Hasher;
274#else
275 typedef boost::hash<T> Hasher;
276#endif
277 return Hasher()(xy.x) ^ Hasher()(xy.y);
278 }
279};
280} // namespace std
281
282namespace CDT
283{
284
285//-----
286// API
287//-----
288template <
289 typename T,
290 typename TVertexIter,
291 typename TGetVertexCoordX,
292 typename TGetVertexCoordY>
293DuplicatesInfo FindDuplicates(
294 TVertexIter first,
295 TVertexIter last,
296 TGetVertexCoordX getX,
297 TGetVertexCoordY getY)
298{
299 typedef unordered_map<V2d<T>, std::size_t> PosToIndex;
300 PosToIndex uniqueVerts;
301 const std::size_t verticesSize = std::distance(first, last);
302 DuplicatesInfo di = {
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)
305 {
306 typename PosToIndex::const_iterator it;
307 bool isUnique;
308 tie(it, isUnique) = uniqueVerts.insert(
309 std::make_pair(V2d<T>::make(getX(*first), getY(*first)), iOut));
310 if(isUnique)
311 {
312 di.mapping[iIn] = iOut++;
313 continue;
314 }
315 di.mapping[iIn] = it->second; // found a duplicate
316 di.duplicates.push_back(iIn);
317 }
318 return di;
319}
320
321template <typename TVertex, typename TAllocator>
322void RemoveDuplicates(
323 std::vector<TVertex, TAllocator>& vertices,
324 const std::vector<std::size_t>& duplicates)
325{
326 vertices.erase(
327 remove_at(
328 vertices.begin(),
329 vertices.end(),
330 duplicates.begin(),
331 duplicates.end()),
332 vertices.end());
333}
334
335template <
336 typename TEdgeIter,
337 typename TGetEdgeVertexStart,
338 typename TGetEdgeVertexEnd,
339 typename TMakeEdgeFromStartAndEnd>
340void RemapEdges(
341 TEdgeIter first,
342 const TEdgeIter last,
343 const std::vector<std::size_t>& mapping,
344 TGetEdgeVertexStart getStart,
345 TGetEdgeVertexEnd getEnd,
346 TMakeEdgeFromStartAndEnd makeEdge)
347{
348 for(; first != last; ++first)
349 {
350 *first = makeEdge(
351 static_cast<VertInd>(mapping[getStart(*first)]),
352 static_cast<VertInd>(mapping[getEnd(*first)]));
353 }
354}
355
356template <
357 typename T,
358 typename TVertex,
359 typename TGetVertexCoordX,
360 typename TGetVertexCoordY,
361 typename TVertexAllocator,
362 typename TEdgeIter,
363 typename TGetEdgeVertexStart,
364 typename TGetEdgeVertexEnd,
365 typename TMakeEdgeFromStartAndEnd>
366DuplicatesInfo RemoveDuplicatesAndRemapEdges(
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)
375{
376 const DuplicatesInfo di =
377 FindDuplicates<T>(vertices.begin(), vertices.end(), getX, getY);
378 RemoveDuplicates(vertices, di.duplicates);
379 RemapEdges(edgesFirst, edgesLast, di.mapping, getStart, getEnd, makeEdge);
380 return di;
381}
382
383template <typename T>
384unordered_map<Edge, std::vector<VertInd> > EdgeToSplitVertices(
385 const unordered_map<Edge, EdgeVec>& edgeToPieces,
386 const std::vector<V2d<T> >& vertices)
387{
388 typedef std::pair<VertInd, T> VertCoordPair;
389 struct ComparePred
390 {
391 bool operator()(const VertCoordPair& a, const VertCoordPair& b) const
392 {
393 return a.second < b.second;
394 }
395 } comparePred;
396
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)
400 {
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); // X-coord longer
405 const bool isAscending =
406 isX ? dX >= 0 : dY >= 0; // Longer coordinate ascends
407 const EdgeVec& pieces = e2pIt->second;
408 std::vector<VertCoordPair> splitVerts;
409 // size is: 2[ends] + (pieces - 1)[split vertices] = pieces + 1
410 splitVerts.reserve(pieces.size() + 1);
411 typedef EdgeVec::const_iterator EIt;
412 for(EIt pieceIt = pieces.begin(); pieceIt != pieces.end(); ++pieceIt)
413 {
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)
417 {
418 const T c = isX ? vertices[*v].x : vertices[*v].y;
419 splitVerts.push_back(std::make_pair(*v, isAscending ? c : -c));
420 }
421 }
422 // sort by longest coordinate
423 std::sort(splitVerts.begin(), splitVerts.end(), comparePred);
424 // remove duplicates
425 splitVerts.erase(
426 std::unique(splitVerts.begin(), splitVerts.end()),
427 splitVerts.end());
428 assert(splitVerts.size() > 2); // 2 end points with split vertices
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)
434 {
435 val.second.push_back(it->first);
436 }
437 edgeToSplitVerts.insert(val);
438 }
439 return edgeToSplitVerts;
440}
441
442} // namespace CDT
443
444#ifndef CDT_USE_AS_COMPILED_LIBRARY
445#include "CDT.hpp"
446#endif
447
448#endif // header-guard
CDTUtils.h
Utilities and helpers.
CDT_EXPORT
#define CDT_EXPORT
Export not needed in header-only mode.
Definition CDTUtils.h:40
CDT.hpp
Public API - implementation.
Triangulation.h
Triangulation class.
CDT::LayerDepth
unsigned short LayerDepth
Type used for storing layer depths for triangles.
Definition CDT.h:40
CDT::VerticesTriangles
std::vector< TriIndVec > VerticesTriangles
Triangles by vertex index.
Definition CDT.h:44
CDT::RemapEdges
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.
Definition CDT.h:340
CDT::EdgeToSplitVertices
CDT_EXPORT unordered_map< Edge, std::vector< VertInd > > EdgeToSplitVertices(const unordered_map< Edge, EdgeVec > &edgeToPieces, const std::vector< V2d< T > > &vertices)
Definition CDT.h:384
CDT::calculateTrianglesByVertex
CDT_EXPORT VerticesTriangles calculateTrianglesByVertex(const TriangleVec &triangles, VertInd verticesSize)
Calculate triangles adjacent to vertices (triangles by vertex index)
Definition CDT.hpp:20
CDT::RemoveDuplicates
void RemoveDuplicates(std::vector< TVertex, TAllocator > &vertices, const std::vector< std::size_t > &duplicates)
Remove duplicates in-place from vector of custom points.
Definition CDT.h:322
CDT::RemoveDuplicatesAndRemapEdges
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)
Definition CDT.h:366
CDT::extractEdgesFromTriangles
CDT_EXPORT EdgeUSet extractEdgesFromTriangles(const TriangleVec &triangles)
Extract all edges of triangles.
Definition CDT.hpp:74
CDT::EdgeToPiecesMapping
CDT_EXPORT unordered_map< Edge, EdgeVec > EdgeToPiecesMapping(const unordered_map< Edge, EdgeVec > &pieceToOriginals)
Definition CDT.hpp:88
CDT::FindDuplicates
DuplicatesInfo FindDuplicates(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Find duplicates in given custom point-type range.
Definition CDT.h:293
CDT
Namespace containing triangulation functionality.
Definition InitializeWithGrid.h:25
CDT::EdgeVec
std::vector< Edge > EdgeVec
Vector of edges.
Definition CDTUtils.h:245
CDT::EdgeUSet
unordered_set< Edge > EdgeUSet
Hash table of edges.
Definition CDTUtils.h:246
CDT::VertInd
IndexSizeType VertInd
Vertex index.
Definition CDTUtils.h:142
CDT::TriangleVec
std::vector< Triangle > TriangleVec
Vector of triangles.
Definition CDTUtils.h:308
CDT::DuplicatesInfo
Information about removed duplicated vertices.
Definition CDT.h:68
CDT::DuplicatesInfo::mapping
std::vector< std::size_t > mapping
vertex index mapping
Definition CDT.h:69
CDT::DuplicatesInfo::duplicates
std::vector< std::size_t > duplicates
duplicates' indices
Definition CDT.h:70
CDT::Edge
Edge connecting two vertices: vertex with smaller index is always first.
Definition CDTUtils.h:209
CDT::Edge::v2
VertInd v2() const
V2 getter.
Definition CDTUtils.hpp:62
CDT::Edge::v1
VertInd v1() const
V1 getter.
Definition CDTUtils.hpp:57
CDT::V2d
2D vector
Definition CDTUtils.h:96
CDT::V2d::y
T y
Y-coordinate.
Definition CDTUtils.h:98
CDT::V2d::x
T x
X-coordinate.
Definition CDTUtils.h:97