CoreSource checked

Delaunay Triangulation

Triangulates points so triangles avoid skinny angles as much as possible.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Advanced
Family: Triangulation
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 5
Code example: Not ready
Visualization: Ready

Overview

Delaunay Triangulation connects points so no point lies inside the circumcircle of any triangle.

Core Concepts

geometric calculationtriangle meshgeometric predicatetriangulationspatial relationshipcoordinate calculation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use Delaunay Triangulation when you need to build triangles over a point set.
Use it for mesh generation with inputs like set of points.
Use it when the problem depends on spatial relationships between points, lines, or shapes.
Use it when the Triangulation tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when floating-point precision or degenerate cases are not handled.
Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not triangle mesh.

What It Does

Builds triangles over a point set
Maintains the empty circumcircle property

Use Cases

Mesh generation
Terrain modeling
Spatial interpolation

Inputs

Set of points

Outputs

Triangle mesh

Key Formulas (1)

Empty circumcircle rule

valid triangle if no other point lies inside its circumcircle

valid triangle if no other point lies inside its circumcircle

Captures the local condition that defines Delaunay triangles.

Pseudocode

1.Start with a containing super-triangle
2.Insert points one at a time
3.Remove triangles whose circumcircles contain the point
4.Retriangulate the cavity
5.Remove triangles connected to the super-triangle

Canonical Example

Input: points = [(0,0), (2,0), (1,1), (1,0)]
Output: spatial result such as a boundary, intersection, or containment answer
Explanation: Delaunay Triangulation: The algorithm uses geometric tests to reason about the input shapes.

Implementation Notes

Keep the input contract explicit: Set of points.
Use this step as the implementation spine: Start with a containing super-triangle.
Then preserve the next state change: Insert points one at a time.
Write tests for points on boundaries, equal coordinates, and very small distances.

Common Pitfalls

Delaunay Triangulation is closely related to Voronoi diagrams.
Forgetting collinear, duplicate, overlapping, or boundary cases.
Returning triangle mesh without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show points connected into triangles that satisfy empty circumcircles.

Step 1 of 5: Start with a containing super-triangle

delaunay-mesh

Notes

Delaunay Triangulation operates in O(n log n) time and O(n) space within the Triangulation family. Key governing relation: valid triangle if no other point lies inside its circumcircle. Often compared with Voronoi Diagram and Quickhull.