Need help with CDT?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

230 Stars 41 Forks Mozilla Public License 2.0 224 Commits 5 Opened issues


C++ library for constrained Delaunay triangulation (CDT)

Services available


Need anything else?

Contributors list

# 204,242
112 commits

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

is defined) - permissively-licensed (MPL-2.0) - backwards-compatible with C++03 - 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 - Online Documentation - Algorithm - Installation - Details - Using - Contributors - Contributing - Examples - Bibliography

Online Documentation

Latest online documentation (automatically generated with Doxygen).


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.

Pre-conditions: - No duplicated points (use provided functions for removing duplicate points and re-mapping edges) - No two constraint edges intersect each other

Post-conditions: - Triangles have counter-clockwise (CCW) winding


Adding to CMake project directly

Can be done with

command (e.g., see CDT visualizer's CMakeLists.txt). ```Cmake

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


To use as a compiled library define

and compile

Consume pre-build CDT in CMake project with


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
# build and install
cmake --build . && cmake --install .
# In consuming CMakeLists.txt

Consume as Conan package

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


  • 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.
  • 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:

  • Boost is an optional dependency used for:

    • Performance: rtree implementation for finding the closest point during points insertion:
      is a faster than
      . Also
      is used for faster triangle walking
    • Fall back for standard library features missing in C++98 compilers.

    To opt in define

    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 folder

    test files


Synopsis of the public API (see CDT.h )

namespace CDT

/// Enum of strategies for finding closest point to the newly inserted one struct FindingClosestPoint { enum Enum { #ifdef CDT_USE_BOOST BoostRTree, ///< use boost::geometry::rtree #endif ClosestRandom, ///< pick closest from few randomly selected candidates }; };

template class CDT_EXPORT Triangulation { public: typedef std::vector > VertexVec; ///< Vertices vector VertexVec vertices; ///< triangulation's vertices TriangleVec triangles; ///< triangulation's triangles EdgeUSet fixedEdges; ///< triangulation's constraints (fixed edges)

/*____ API _____*/
    const FindingClosestPoint::Enum closestPtMode,
    const size_t nRandSamples = 10);
template <typename tvertexiter typename tgetvertexcoordx tgetvertexcoordy>
void insertVertices(
    TVertexIter first,
    TVertexIter last,
    TGetVertexCoordX getX,
    TGetVertexCoordY getY);
void insertVertices(const std::vector<v2d> &gt;&amp; vertices);
template <typename tedgeiter typename tgetedgevertexstart tgetedgevertexend>
void insertEdges(
    TEdgeIter first,
    TEdgeIter last,
    TGetEdgeVertexStart getStart,
    TGetEdgeVertexEnd getEnd);
void insertEdges(const std::vector<edge>&amp; edges);
void eraseSuperTriangle();
void eraseOuterTriangles();
void eraseOuterTrianglesAndHoles();


struct DuplicatesInfo { std::vector<:size_t> mapping; ///< vertex index mapping std::vector<:size_t> duplicates; ///< duplicates' indices };

template DuplicatesInfo FindDuplicates( TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY);

template void RemoveDuplicates( std::vector& vertices, const std::vector<:size_t>& duplicates);

template DuplicatesInfo RemoveDuplicates(std::vector >& vertices);

void RemapEdges(std::vector& edges, const std::vector<:size_t>& mapping);

template < typename T, typename TVertex, typename TGetVertexCoordX, typename TGetVertexCoordY, typename TVertexAllocator, typename TEdgeAllocator> DuplicatesInfo RemoveDuplicatesAndRemapEdges( std::vector& vertices, std::vector& edges, TGetVertexCoordX getX, TGetVertexCoordY getY);

template DuplicatesInfo RemoveDuplicatesAndRemapEdges( std::vector >& vertices, std::vector& edges);

template std::vector CalculateTriangleDepths( const std::vector >& vertices, const TriangleVec& triangles, const EdgeUSet& fixedEdges);

TriIndUSet PeelLayer( std::stack seeds, const TriangleVec& triangles, const EdgeUSet& fixedEdges, const unsigned short layerDepth, std::vector& triDepths);

} // namespace CDT </:size_t></:size_t></:size_t></:size_t>

Triangulated convex-hull example

#include "CDT.h"
using Triangulation = CDT::Triangulation;

Triangulation cdt = Triangulation(CDT::FindingClosestPoint::BoostRTree); /* // Without boost::rtree: Triangulation(CDT::FindingClosestPoint::ClosestRandom, 10); / cdt.insertVertices(/ points /); cdt.eraseSuperTriangle(); / ... / = cdt.vertices; / ... */ = cdt.edges;

Triangulated region constrained by boundary example

// ... same as above
cdt.insertVertices(/* points */);
cdt.insertEdges(/* boundary edges */);
/* ... */ = cdt.vertices;
/* ... */ = cdt.edges;

Custom point type

struct CustomPoint2D
    double data[2];

std::vector points = ...; // containers other than std::vector will work too triangulation = CDT::Triangulation(...); triangulation.insertVertices( points.begin(), points.end(), [](const CustomPoint2D& p){ return[0]; }, [](const CustomPoint2D& p){ return[1]; } );

Custom edge type ```c++ struct CustomEdge { std::pair<:size_t std::size_t> vertices; };

std::vector edges = ...; // containers other than std::vector will work too triangulation = CDT::Triangulation(...); triangulation.insertVertices(...); triangulation.insertEdges( edges.begin(), edges.end(), { return e.vertices.first; }, { return e.vertices.second; } ); ```



Any feedback and contributions are welcome.


Mozilla Public License, v. 2.0


A Bean Guitar Guitar with holes Lake Superior Sweden


[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

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.