CoreSource checked

Constrained Delaunay Triangulation

Constrained Delaunay Triangulation uses building Delaunay-like triangles while preserving required input edges for constrained triangulation.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Intermediate
Family: Triangulation
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 6
Code example: Ready
Visualization: Ready

Overview

Constrained Delaunay Triangulation handles constrained triangulation by building Delaunay-like triangles while preserving required input edges.

Core Concepts

constrained triangulationtriangulationgeometry

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use Constrained Delaunay Triangulation when solving triangulation and you want to benefit from building Delaunay-like triangles while preserving required input edges.
Choose it when O(n log n) average/worst-case time and O(n) memory match your workload profile.
Prefer it over Monotone Polygon Partitioning or Hertel-Mehlhorn Convex Decomposition when the problem structure favors constrained triangulation.

When Not to Use

Avoid when coordinate precision is too low for the required geometric decisions.
Avoid when degenerate cases dominate and the implementation has no robustness strategy.

What It Does

Constrained Delaunay Triangulation uses building Delaunay-like triangles while preserving required input edges for constrained triangulation
Organizes the work around constrained triangulation and triangulation.

Use Cases

Production and research workloads requiring triangulation via building Delaunay-like triangles while preserving required input edges.
Triangulation pipelines where O(n log n) time and O(n) space fit system constraints.
Engineering comparisons against Monotone Polygon Partitioning and Hertel-Mehlhorn Convex Decomposition when tuning triangulation.

Inputs

Points, segments, polygons, or geometric primitives
Query or construction parameters

Outputs

Geometric decision, measurement, or constructed structure

Pseudocode

1.Normalize input coordinates, primitives, or pixel buffers and initialize spatial data structures for constrained triangulation.
2.Establish the sweep event queue, hierarchy, or scale-space pyramid required by Constrained Delaunay Triangulation.
3.Process geometric predicates or pixel neighborhoods by building Delaunay-like triangles while preserving required input edges.
4.Resolve boundary degeneracies, occlusions, or threshold suppressions to maintain consistency.
5.Output the final triangulation primitives, descriptors, or composited buffer.

Canonical Example

Input: Points, segments, polygons, or geometric primitives configured for a representative triangulation test case
Output: Geometric decision, measurement, or constructed structure satisfying Constrained Delaunay Triangulation invariants
Explanation: Constrained Delaunay Triangulation processes the input by building Delaunay-like triangles while preserving required input edges, tracking constrained triangulation and triangulation to produce the verified triangulation result.

Implementation Notes

Normalize orientation and coordinate conventions at module boundaries.
Add degenerate cases such as collinear points and touching edges.
Use robust predicates where sign errors change topology.

Common Pitfalls

Ignoring collinear, coincident, or nearly degenerate geometry.
Relying on floating-point signs without a robustness strategy.
Mixing coordinate systems or orientation conventions.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show building Delaunay-like triangles while preserving required input edges on a small constrained triangulation example.

Step 1 of 5: Normalize input coordinates, primitives, or pixel buffers and initialize spatial data structures for constrained triangulation.

geometry-mechanism

Notes

Constrained Delaunay Triangulation operates in O(n log n) time and O(n) space within the Triangulation family. Often compared with Monotone Polygon Partitioning and Hertel-Mehlhorn Convex Decomposition.