C++ implementation of constrained Delaunay triangulation (CDT)
- numerically robust (uses robust geometric predicates)
- header-only (default)
- using as compiled library is possible by defining
CDT_USE_AS_COMPILED_LIBRARY - permissively-licensed (MPL-2.0)
- compatible with C++03
- cross-platform: tested on Windows and Linux
-
Uses William C. Lenthe's implementation of robust orientation and in-circle geometric predicates: https://github.com/wlenthe/GeometricPredicates.
-
Optionally depends on Boost for rtree implementation (finding closest point) and fall back for some std types on pre-C++11 compilers. Boost dependency can be easily be removed via defining
CDT_DONT_USE_BOOST_RTREE. This replacesnearestVertexRtreewith slowernearestVertexRand. -
A demonstrator tool is included: requires Qt for GUI. When running demo-tool make sure that working directory contains folder
test files.
Implementation closely follows incremental construction algorithm by Anglada [1]. During the legalization, the cases when at least one vertex belongs to super-triangle are resolved using an approach as described in Žalik et. al [2]. For efficient search of a triangle that contains inserted point randomized walking search is applied [3]. To find the starting triangle we first find the nearest point using boost::rtree or using a closest random point.
- No duplicated points
- No two constraint edges intersect each other
No installation is needed. For the demonstrator tool qmake project file is used. It could either be opened in QtCreator directly, or qmake can be used to generate project files (e.g., makefiles or MSVC-project)
Define CDT_USE_AS_COMPILED_LIBRARY and compile CDT.cpp
namespace CDT
{
struct FindingClosestPoint
{
enum Enum
{
#ifndef CDT_DONT_USE_BOOST_RTREE
BoostRTree,
#endif
ClosestRandom,
};
};
template <typename T>
class Triangulation
{
public:
/*____ Data ____*/
std::vector<Vertex<T> > vertices;
std::vector<Triangle> triangles;
EdgeUSet fixedEdges;
/*____ API _____*/
Triangulation(
const FindingClosestPoint::Enum closestPtMode,
const size_t nRandSamples = 10);
void insertVertices(const std::vector<V2d<T> >& vertices);
void insertEdges(const std::vector<Edge>& edges);
void eraseSuperTriangle();
void eraseOuterTriangles();
// ...
}
} // namespace CDT#include "CDT.h"
using Triangulation = CDT::Triangulation<float>;
Triangulation cdt =
Triangulation(CDT::FindingClosestPoint::BoostRTree);
/*
// Without boost::rtree:
Triangulation(CDT::FindingClosestPoint::ClosestRandom, 10);
*/
cdt.insertVertices(/* points */);
cdt.eraseSuperTriangle();
/* ... */ = cdt.vertices;
/* ... */ = cdt.edges;// ... same as above
cdt.insertVertices(/* points */);
cdt.insertEdges(/* boundary edges */);
cdt.eraseOuterTriangles();
/* ... */ = cdt.vertices;
/* ... */ = cdt.edges;Karl Åkerblom: algorithm implementation, triangle walking
Any feedback and contributions are welcome.
Mozilla Public License, v. 2.0
[1] Marc Vigo Anglada, An improved incremental algorithm for constructing restricted Delaunay triangulations, Computers & Graphics, Volume 21, Issue 2, 1997, Pages 215-223, ISSN 0097-8493.
[2] Borut Žalik and Ivana Kolingerová, An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm, International Journal of Geographical Information Science, Volume 17, Issue 2, Pages 119-138, 2003, DOI 10.1080/713811749.
[3] Olivier Devillers, Sylvvain Pion, Monique Tellaud, Walking in a triangulation, International Journal of Foundations of Computer Science, Volume 13, Issue 2, Pages 181-199, 2002