Skip to content
artem-ogrePublic

About

Constrained Delaunay Triangulation (Python)

Topics

Resources

Stars

69 stars

Watchers

3 watching

Forks

Repository files navigation

PythonCDT Logo

PythonCDT

Python bindings for CDT: C++ library for constrained Delaunay triangulation implemented with pybind11

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

What can PythonCDT do?

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

  • Constrained Delaunay triangulations: force edges into the Delaunay triangulation
  • Conforming Delaunay triangulations: add new points into the Delaunay triangulation until the edges are present in the triangulation
  • Refinement: add new points until triangles fulfill a minimum-angle or maximum-area criterion
  • Convex hulls
  • Automatically finding and removing holes

Properly handling the corner cases

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

  • Points exactly on the edges
  • Exactly overlapping edges
  • Resolving intersecting edges by adding points at the intersections (with IntersectingConstraintEdges.TRY_RESOLVE)

Refinement

Constrained Delaunay triangulation refined by minimum angle and by maximum area

refine_triangles() improves the shape of the triangles by inserting new points (Steiner points). It must be called before the triangulation is finalized: collect the triangles to remove first so that they are not refined, then remove them with finalize_triangulation() (the set is updated in place).

Limits of refinement

Sharp corner of the input that refinement can not improve

Some places can not be refined: e.g., a sharp angle between two constraint edges comes from the input and can not be made any larger. refine_triangles() returns the counts of such refinements; find_unrefined_triangles() and find_encroached_fixed_edges() locate them in the resulting triangulation.

Installation

pip install pythoncdt

Wheels are published for Linux, macOS and Windows.

Building from source

Building needs a C++17 compiler; pip fetches pybind11, and CMake if it is missing.

git clone --recurse-submodules https://github.com/artem-ogre/PythonCDT.git
cd PythonCDT
pip install . --group test  # needs pip 25.1+
pytest

Before committing, install the pre-commit hooks with pre-commit install: CI runs the same checks.

Usage examples

Constrained triangulation

Example of a triangulation with constrained boundaries and auto-detected holes

import numpy as np
import pythoncdt as cdt

vertices = np.array(
    [[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0], [0.4, 0.4]],
)
edges = np.array([[0, 1], [1, 2], [2, 3], [3, 0]], dtype=np.uintc)

t = cdt.Triangulation(
    cdt.VertexInsertionOrder.AUTO,
    cdt.IntersectingConstraintEdges.TRY_RESOLVE,
    0.0,
)
t.insert_vertices(vertices)
t.insert_edges(edges)
t.erase_outer_triangles_and_holes()

vv = t.vertices_array()  # numpy array with fields 'x' and 'y'
tt = t.triangles_array()  # numpy array with fields 'vertices' and 'neighbors'
tt["vertices"]  # (T, 3) vertex indices into vv

Notes

  • vertices_array() and triangles_array() return copies. With copy=False they return read-only views of the triangulation's memory instead; a view is invalidated by any call that modifies the triangulation.

Delaunay triangulation without constraints (triangulated convex hull)

Example of a triangulated convex hull

t = cdt.Triangulation(
    cdt.VertexInsertionOrder.AUTO,
    cdt.IntersectingConstraintEdges.NOT_ALLOWED,
    0.0,
)
t.insert_vertices(vertices)
t.erase_super_triangle()

Conforming triangulation

Example of a conforming triangulation

t = cdt.Triangulation(
    cdt.VertexInsertionOrder.AUTO,
    cdt.IntersectingConstraintEdges.TRY_RESOLVE,
    0.0,
)
t.insert_vertices(vertices)
t.conform_to_edges(edges)
t.erase_outer_triangles_and_holes()

Notes

  • conform_to_edges() splits the constraint edges as needed, instead of keeping them as they are.

Refined triangulation

Example of a refined triangulation

t = cdt.Triangulation(
    cdt.VertexInsertionOrder.AUTO,
    cdt.IntersectingConstraintEdges.TRY_RESOLVE,
    0.0,
)
t.insert_vertices(vertices)
t.insert_edges(edges)

to_erase = t.collect_outer_triangles_and_holes()
unrefined = t.refine_triangles(
    1000,
    cdt.RefinementCriterion.SMALLEST_ANGLE,
    cdt.deg_to_rad(20.0),
    to_erase,
)
t.finalize_triangulation(to_erase)

Threads

Triangulating releases the GIL, so separate triangulations can be built in parallel on Python threads. One triangulation can be shared between threads: calls on it wait for each other. Iterators (*_iter()) and copy=False views are not protected: don't use them while another thread modifies the triangulation.

License

Mozilla Public License, v. 2.0

Bundled CDT includes third-party code under other licenses:

Contributors

Example Gallery

A A A Bean Guitar Guitar with holes Guitar refined by maximum triangle area Lake Superior Sweden Sweden refined by minimum angle Overlapping boundaries

About

Constrained Delaunay Triangulation (Python)

Topics

Resources

Stars

69 stars

Watchers

3 watching

Forks

Releases

Packages

Used by

Contributors

Languages