CDT  1.1.2
C++ library for constrained Delaunay triangulation (CDT)
CDT Documentation

CDT Logo

CDT: Constrained Delaunay Triangulation

CI Builds

Numerically robust C++ implementation of constrained Delaunay triangulation (CDT)

  • uses robust geometric predicates for numerical robustness
  • can be consumed as header-only (default) or compiled (if CDT_USE_AS_COMPILED_LIBRARY is defined)
  • permissively-licensed (MPL-2.0)
  • backwards-compatible with C++98
  • cross-platform: tested on Windows, Linux (Ubuntu), and macOS

Please ★ this repository if it helped. This means a lot to the authors :)

Table of Contents

<a name="online-doc"/>Online Documentation</a>

Latest online documentation (automatically generated with Doxygen).

<a name="algorithm"/>Algorithm</a>

  • 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 finding a triangle that contains inserted point remembering randomized triangle walk is used [3]. To find the starting triangle for the walk the nearest point is found using a kd-tree with mid-split nodes.
  • By default inserted vertices are randomly shuffled internally to improve performance and avoid worst-case scenarios. The original vertices order can be optied-in using VertexInsertionOrder::AsProvided when constructing a triangulation.

Pre-conditions:

  • No duplicated points (use provided functions for removing duplicate points and re-mapping edges)
  • No two constraint edges intersect each other (overlapping boundaries are allowed)

Post-conditions:

  • Triangles have counter-clockwise (CCW) winding

<a name="details"/>Implementation Details</a>

  • Supports three ways of removing outer triangles:
    • eraseSuperTriangle: produce a convex-hull
    • eraseOuterTriangles: remove all outer triangles until a boundary defined by constraint edges
    • eraseOuterTrianglesAndHoles: remove outer triangles and automatically detected holes. Starts from super-triangle and traverses triangles until outer boundary. Triangles outside outer boundary will be removed. Then traversal continues until next boundary. Triangles between two boundaries will be kept. Traversal to next boundary continues (this time removing triangles). Stops when all triangles are traversed.
  • Supports overlapping boundaries
  • Removing duplicate points and re-mapping constraint edges can be done using functions: RemoveDuplicatesAndRemapEdges, RemoveDuplicates, RemapEdges
  • Uses William C. Lenthe's implementation of robust orientation and in-circle geometric predicates: https://github.com/wlenthe/GeometricPredicates.
  • Boost is an optional dependency used for:
    • Fall back for standard library features missing in C++98 compilers.
    • Minor performance tweaks: boost::container::flat_set is used for faster triangle walking
To opt in define `CDT_USE_BOOST` either in CMake or in a preprocessor.
  • A demonstrator tool is included: requires Qt for GUI. When running demo-tool make sure that working directory contains files from 'data' folder.

<a name="installation"/>Installation/Building</a>

CDT uses modern CMake and should just work out of the box without any suprises. The are many ways to consume CDT:

  • copy headers and use as a header-only library
  • add to CMake project directly with add_subdirectory
  • pre-build and add to CMake project as a dependency with find_package
  • consume as a Conan package

CMake options

Option

Default value

Description </thead> <tbody>

CDT_USE_BOOST

OFF

If enabled Boost is used as a fall-back for features missing in C++98 and performance tweaks (e.g., using boost::flat_set)

CDT_USE_64_BIT_INDEX_TYPE

OFF

If enabled 64bits are used to store vertex/triangle index types. Otherwise 32bits are used (up to 4.2bn items)

CDT_USE_AS_COMPILED_LIBRARY

OFF

If enabled templates for float and double will be instantiated and compiled into a library </tbody>

Adding to CMake project directly

Can be done with add_subdirectory command (e.g., see CDT visualizer's CMakeLists.txt).

# add CDT as subdirectory to CMake project
add_subdirectory(../CDT CDT)

Adding to non-CMake project directly

To use as header-only copy headers from CDT/include

To use as a compiled library define CDT_USE_AS_COMPILED_LIBRARY and compile CDT.cpp

**Consume pre-build CDT in CMake project with find_package**

CDT provides package config files that can be included by other projects to find and use it.

# from CDT folder
mkdir build && cd build
# configure with desired CMake flags
cmake -DCDT_USE_AS_COMPILED_LIBRARY=ON -DCDT_USE_BOOST=ON ..
# build and install
cmake --build . && cmake --install .
# In consuming CMakeLists.txt
find_package(CDT REQUIRED CONFIG)

Consume as Conan package

There's a conanfile.py recipe provided. Note that it might need small adjustments like changing boost version to fit your needs.

<a name="using"/>Using</a>

Public API is provided in two places:

  • CDT::Triangulation class is used for performing constrained Delaunay triangulations.
  • Free functions in CDT.h provide some additional functionality for removing duplicates, re-mapping edges and triangle depth-peeling

Code Examples

Triangulation with constrained boundaries

Example of a triangulation with constrained boundaries and auto-detected holes

{c++}
// ... same as above
cdt.insertVertices(/* points */);
cdt.insertEdges(/* boundary edges */);
cdt.eraseOuterTrianglesAndHoles();
/* access triangles */ = cdt.triangles;
/* access vertices */ = cdt.vertices;
/* access boundary edges */ = cdt.edges;

Triangulated convex-hull

Example of a triangulated convex hull

{c++}
#include "CDT.h"
CDT::Triangulation<double> cdt;
cdt.insertVertices(/* points */);
cdt.eraseSuperTriangle();
/* access triangles */ = cdt.triangles;
/* access vertices */ = cdt.vertices;
/* access boundary edges */ = cdt.edges;

Custom point/edge type

{c++}
struct CustomPoint2D
{
double data[2];
};
struct CustomEdge
{
std::pair<std::size_t, std::size_t> vertices;
};
// containers other than std::vector will work too
std::vector<CustomPoint2D> points = /*...*/;
std::vector<CustomEdge> edges = /*...*/;
CDT::Triangulation<double> cdt;
cdt.insertVertices(
points.begin(),
points.end(),
[](const CustomPoint2D& p){ return p.data[0]; },
[](const CustomPoint2D& p){ return p.data[1]; }
);
cdt.insertEdges(
edges.begin(),
edges.end(),
[](const CustomEdge& e){ return e.vertices.first; },
[](const CustomEdge& e){ return e.vertices.second; }
);

<a name="contributors"/>Contributors</a>

<a name="contributing"/>Contributing</a>

Any feedback and contributions are welcome.

<a name="license"/>License</a>

Mozilla Public License, v. 2.0

<a name="example-gallery"/>Example Gallery</a>

A Bean Guitar Guitar with holes Lake Superior Sweden Overlapping boundaries

<a name="bibliography"/>Bibliography</a>

[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