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

artem-ogre
145 Stars 21 Forks Mozilla Public License 2.0 219 Commits 2 Opened issues

Description

C++ library for constrained Delaunay triangulation (CDT)

Services available

!
?

Need anything else?

Contributors list

# 258,868
Shell
C++
c-plus-...
compile...
107 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

CDT_USE_AS_COMPILED_LIBRARY
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).

Algorithm

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

Installation

Adding to CMake project directly

Can be done with

add_subdirectory
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

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.

Details

  • 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: https://github.com/wlenthe/GeometricPredicates.

  • Boost is an optional dependency used for:

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

    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 folder

    test files
    .

Using

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 _____*/
Triangulation(
    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.eraseOuterTriangles();
/* ... */ = 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 p.data[0]; }, [](const CustomPoint2D& p){ return p.data[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; } ); ```

Contributors

Contributing

Any feedback and contributions are welcome.

License

Mozilla Public License, v. 2.0

Examples

A Bean Guitar Guitar with holes Lake Superior Sweden

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

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.