search

artem-ogre / CDT

Constrained Delaunay Triangulation (C++)
https://artem-ogre.github.io/CDT/
Mozilla Public License 2.0
947 stars 125 forks source link
c-plus-plus cdt compiled computational-geometry conforming constrained constrained-delaunay-triangulation delaunay delaunay-triangulation fast header-only library robust triangle triangulation

readme

Overview

CDT Logo

CI Builds

CDT is a C++ library for generating constraint or conforming Delaunay triangulations.

If CDT helped you please consider adding a star on GitHub. This means a lot to the authors 🤩

Table of Contents

What can CDT do?

CDT show-case: constrained and conforming triangulations, convex hulls, automatically removing holes

Properly Handling the Corner-Cases

CDT supported corner cases: points on edges, overlapping edges, resolving edge intersections

Online Documentation

Latest online documentation (automatically generated with Doxygen).

Algorithm

Pre-conditions:

Post-conditions:

Implementation Details

Adding CDT to your C++ project Using a Package Manager

vcpkg

CDT port is available in Microsoft's vcpkg.

Conan

CDT is not in the conan-center but there's a conanfile.py recipe provided (in this repo). Note that it might need small adjustments like changing boost version to fit your needs.

spack

A recipe for CDT is available in spack.

Installation/Building

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

CMake options

Option Default value Description
CDT_USE_64_BIT_INDEX_TYPE OFF Use 64bits to store vertex/triangle index types. Otherwise 32bits are used (up to 4.2bn items)
CDT_USE_AS_COMPILED_LIBRARY OFF Instantiate templates for float and double and compiled into a library

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 ..
# build and install
cmake --build . && cmake --install .
# In consuming CMakeLists.txt
find_package(CDT REQUIRED CONFIG)

Using

Public API is provided in two places:

Code Examples

Delaunay triangulation without constraints (triangulated convex-hull)

Example of a triangulated convex hull 
#include "CDT.h"
CDT::Triangulation<double> cdt;
cdt.insertVertices(/* points */);
cdt.eraseSuperTriangle();
/* access triangles */ = cdt.triangles;
/* access vertices */ = cdt.vertices;
/* access boundary (fixed) edges */ = cdt.fixedEdges;
/* calculate all edges (on demand) */ = CDT::extractEdgesFromTriangles(cdt.triangles);

Constrained Delaunay triangulation (auto-detected boundaries and holes)

Example of a triangulation with constrained boundaries and auto-detected holes 
// ... same as above
cdt.insertVertices(/* points */);
cdt.insertEdges(/* boundary edges */);
cdt.eraseOuterTrianglesAndHoles();
/* access triangles */ = cdt.triangles;
/* access vertices */ = cdt.vertices;
/* access boundary (fixed) edges */ = cdt.fixedEdges;
/* calculate all edges (on demand) */ = CDT::extractEdgesFromTriangles(cdt.triangles);

Conforming Delaunay triangulation

Use CDT::Triangulation::conformToEdges instead of CDT::Triangulation::insertEdges

Resolve edge intersections by adding new points and splitting edges

Pass CDT::IntersectingConstraintEdges::TryResolve to CDT::Triangulation constructor.

Custom point/edge type

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; }
);

Python bindings?

For work-in-progress on Python bindings check-out PythonCDT

Contributors

Contributing

Any feedback and contributions are welcome.

License

Mozilla Public License, v. 2.0

For attribution you can use the following template:

This software is based part on CDT (C++ library for constrained Delaunay triangulation):
Copyright © 2019 Leica Geosystems Technology AB
Copyright © The CDT Contributors
Licensed under the MPL-2.0 license.
https://github.com/artem-ogre/CDT
${INSERT_FULL_MPL_2.0_TEXT}

Example Gallery

A Bean Guitar Guitar with holes Lake Superior Sweden Overlapping boundaries

Bibliography

[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

[4] Liu, Jianfei & Yan, Jinhui & Lo, S.. A new insertion sequence for incremental Delaunay triangulation. Acta Mechanica Sinica, Volume 29, 2013