CDT constrained Delaunay triangulation in C++

CDT's constrained triangulation scope

CDT addresses a specific computational geometry problem: constructing a Delaunay triangulation in which selected input edges must remain present. That requirement matters when edges represent boundaries, barriers, domain limits, or other lines that an unconstrained triangulation would otherwise cross. The library is intended for C++ applications that need control over the topology as well as a collection of triangles. It can build a constrained Delaunay triangulation, a conforming Delaunay triangulation, or a triangulation refined to meet numerical quality criteria.

The scope extends beyond a basic convex-hull triangulation. According to the README, CDT can calculate convex hulls and automatically find and remove holes. It also handles points lying exactly on edges, edges that overlap exactly, and intersecting edges that can be resolved by adding intersection points. These cases are part of the stated supported input geometry rather than incidental examples. That makes CDT relevant to mesh pipelines dealing with segmented domains, polylines, and boundary networks.

CDT is a library, not a complete interactive mesher. The README lists callbacks and visualization resources, but it does not document a command-line application, file format, interactive editor, or complete mesh-generation workflow. A team looking for a ready-made mesh generator with material models, boundary layers, or a full geometry-import pipeline would need to supply that layer separately.

Incremental construction and constraint conformance

The documented algorithm follows Anglada's incremental construction method. Input vertices are inserted into a growing triangulation, and the resulting triangles are legalized to restore the Delaunay property. The README notes a separate approach for legalization cases involving vertices associated with the triangulation's super-triangle. This outer construction region helps the algorithm process input incrementally before excluded exterior triangles are removed or finalized.

Locating the triangle for a newly inserted point uses a randomized triangle walk. A k-d-tree with mid-split nodes supplies a nearby point as the starting reference for that walk. Insertion order is controlled through `CDT::VertexInsertionOrder`. With `CDT::VertexInsertionOrder::Auto`, initial bulk loading traverses the k-d-tree in breadth-first order, while later calls to `CDT::Triangulation::insertVertices` use randomized insertion. The documentation says this avoids worst-case insertion scenarios and is generally faster. Applications that require the original sequence can select `CDT::VertexInsertionOrder::AsProvided`.

Constraint edges and conforming edges solve different problems. A constrained Delaunay triangulation forces each supplied edge into the result. A conforming Delaunay triangulation instead permits CDT to insert additional points until the requested edge is represented in the triangulation. Intersecting constraints introduce another path: `CDT::IntersectingConstraintEdges::TryResolve` can add points where edges intersect and split the affected edges. This distinction affects both input requirements and the resulting vertex and triangle counts.

Ruppert refinement and its stopping limits

CDT 2.0 adds a refinement implementation that follows Ruppert's Delaunay refinement algorithm. `CDT::Triangulation::refineTriangles` inserts Steiner points until selected triangles satisfy minimum-angle or maximum-area criteria. The two criteria exposed through `CDT::RefinementCriterion` are `SmallestAngle` and `LargestArea`. Angle thresholds are expressed in radians, and the README directs callers to `CDT::degToRad` for conversions.

Refinement is constrained by several budget rules. Insertion stops when `maxVerticesToInsert` is exhausted, and edges or triangles already shorter than `minEdgeLength` are not split further. Constraint edges must remain conformed to. When a nearby point encroaches on one, CDT can split that edge, while refinement does not insert new points across an input boundary. Encroached constraint edges are processed before a circumcenter is inserted. At input corners with small angles, the documented algorithm splits edges on concentric shells based on powers of two so refinement can terminate.

There is a genuine quality boundary. A sharp corner formed by two input constraint edges cannot be made larger because it comes from the input geometry. `refineTriangles` can therefore return `CDT::Unrefined` with counts of refinements that could not be completed. Applications can inspect unresolved triangles with `findUnrefinedTriangles` and encroached fixed edges with `findEncroachedFixedEdges`. This is preferable to assuming that a successful function call means every requested quality condition was met.

Finalization, holes, and selective refinement

CDT requires callers to account for triangles outside the intended domain. Refinement must occur before the triangulation is finalized with an `erase` method. When only retained triangles should be refined, the documented sequence starts by collecting unwanted geometry with `collectSuperTriangle`, `collectOuterTriangles`, or `collectOuterTrianglesAndHoles`. The retained triangles are passed to `refineTriangles`, after which `finalizeTriangulation` removes the collected triangles.

This staged process reflects CDT's status as a topology-level library. It does not treat exterior construction triangles as ordinary output. It also allows a caller to refine a selected subset rather than spend the vertex budget on geometry that will later disappear. The trade-off is procedural complexity: callers must understand which collection method matches their domain and must finalize in the correct order.

The README does not provide the complete error-handling contract. In particular, it does not enumerate every exception type or show how duplicate input points should be remapped. It does state one firm precondition: input points must not be duplicated. The library provides functions for removing duplicate points and remapping references, but their signatures are not included in the README text. Production integration therefore needs the API documentation to implement that mapping correctly rather than deduplicating points and continuing without reconciling constraint references.

Installing CDT and making a first integration decision

The project documentation provides package-manager and direct installation or build sections, but the README text does not include their commands or package names. The project homepage is `https://artem-ogre.github.io/CDT/`, and the online API documentation is generated with Doxygen. Since no verified installation command appears in the README, this tutorial does not invent one.

A first integration should therefore begin by choosing the repository's documented package-manager route or its `Installation/Building` workflow for the target environment. After obtaining the headers or compiled library, the first API-level operation should match the required topology. For a plain Delaunay triangulation, construct `CDT::Triangulation` with `CDT::VertexInsertionOrder::Auto`, provide vertices, and insert them before producing the required triangles. For constrained input, provide the constraint edges as part of the construction sequence.

If a requested segment must survive triangulation without forcing the original segment representation into the result, use the conforming triangulation example rather than the constrained triangulation example. If supplied edges cross, route that case through `CDT::IntersectingConstraintEdges::TryResolve`. For triangle quality, defer finalization, call `CDT::Triangulation::refineTriangles`, inspect `CDT::Unrefined` when returned, and then remove the excluded triangles. The repository contains a `visualizer/` entry, but the README does not document how to build or operate it, so it should not be treated as a guaranteed first-run path.

Header-only use, platform scope, and library trade-offs

CDT can be consumed as a header-only library or built as a compiled library. Header-only use can simplify deployment when integrating source code directly, while compiled use separates build work from application compilation. The README does not document compile flags or build-system files, so the practical difference depends on the repository instructions for the selected distribution mode.

The library has no external dependencies by default and remains backwards-compatible with C++98. Those properties can be useful for older C++ codebases, although the README does not state that CDT is intended specifically for embedded systems. It is documented as tested on Windows, Linux with Ubuntu, and macOS, with `x64` and `arm64` architectures listed.

CDT maintenance, MPL-2.0, and upgrade exposure

The repository is not archived, and its last push was on 2026-10-13. The release history includes version 2.0.1 on 2026-10-13, version 2.0.0 on 2026-09-20, and version 1.4.5 on 2026-07-22. Version 2.0.0 is described as adding Ruppert refinement along with improvements and fixes, so users moving from the 1.x line should review refinement behavior and API changes rather than treating 2.0.1 as a routine patch release.

The project is licensed under MPL-2.0. The README characterizes this as permissive. MPL-2.0 commonly operates at the file level when a distribution includes modified MPL-covered files, but this review does not provide legal advice or determine the obligations for a particular product. Release 2.0.1 specifically mentions a bugfix and third-party licenses, making the license files bundled with that release the relevant source for an adoption decision.

Upgrading can affect more than package metadata because 2.0.0 introduced a refinement implementation centered on `refineTriangles`, `RefinementCriterion`, encroached-edge handling, and explicit finalization rules. An existing pipeline should review calls to triangulation finalization, input ordering, and any newly adopted quality criteria. The current release cadence is visible, but the README does not promise long-term API stability beyond the stated C++98 backwards compatibility.

Editorial conclusion

Adopt CDT when the application needs fine-grained control over C++ triangulation, especially constrained boundaries, holes, conforming edges, or quality refinement. Do not choose it merely as a general mesh generator or expect every triangle-quality target to be satisfied. Before adoption, verify the duplicate-point precondition, the handling of intersecting and encroached constraints, the build form required by your project, and whether `CDT::Unrefined` reports regions that your geometry cannot improve.

Frequently asked questions

Official sources

1. artem-ogre/CDT on GitHub
2. License: MPL-2.0
3. Project website
4. README
5. Releases