Fast N-dimensional Delaunay triangulation in Rust with Python bindings (PyO3).
Drop-in replacement for adaptive's Triangulation class — 30-300× faster standalone, ~3.3× end-to-end in LearnerND (where adaptive's own Python code dominates).
Used automatically by adaptive ≥ 1.5 when installed.
Measured with the scripts in examples/ against adaptive 1.5.0, best of 3.
Absolute times are machine-dependent; the ratios are representative.
| Case | Rust | Python | Speedup |
|---|---|---|---|
| 2D, 1K pts | 18 ms | 730 ms | 41× |
| 2D, 5K pts | 138 ms | 14,442 ms | 105× |
| 3D, 500 pts | 32 ms | 3,037 ms | 94× |
| 3D, 2K pts | 150 ms | 44,531 ms | 297× |
| N pts | Learner2D (scipy) | LearnerND (Python) | LearnerND (Rust) |
|---|---|---|---|
| 1,000 | 0.23 s | 0.50 s | 0.16 s |
| 2,000 | 0.90 s | 1.01 s | 0.32 s |
| 5,000 | 5.69 s | 2.57 s | 0.79 s |
LearnerND + Rust is 3.3× faster than LearnerND + Python, and 7× faster than Learner2D at 5K points. The end-to-end ratio is smaller than the standalone one because adaptive's own Python-side loss machinery dominates once the triangulation is fast.
simplices_containing and default_loss move two of the remaining LearnerND Python hot loops into Rust.
Wired in the way a future adaptive release would use them (examples/learnernd_batched_apis.py), they add 1.17× (2D, 3000 pts) to 1.40× (3D, 1500 pts) on top of the table above, while sampling identical points.
pip install adaptive-triangulationRequires a Rust toolchain for building from source. Pre-built wheels are available for common platforms via CI.
fromadaptive_triangulationimportTriangulation# Build a 2D triangulationtri=Triangulation([(0, 0), (1, 0), (0, 1), (1, 1)])
# Insert points incrementally (Bowyer-Watson)deleted, added=tri.add_point((0.5, 0.5))
# Query propertiesprint(len(tri.simplices)) # number of trianglesprint(tri.dim) # 2print(tri.reference_invariant()) # TrueSince adaptive 1.5.0 this package is detected and used automatically — no code changes needed:
pip install "adaptive[rust]"Per learner, the backend can be selected explicitly with LearnerND(..., triangulation_backend="auto" | "python" | "rust"), or globally with the ADAPTIVE_TRIANGULATION_BACKEND environment variable.
For adaptive < 1.5.0, monkey-patch the module instead:
importadaptive_triangulationasatfromadaptive.learnerimportlearnerNDaslnd_modfromadaptive.learner.learnerNDimportLearnerND# Replace both the class and standalone functionslnd_mod.Triangulation=at.Triangulationlnd_mod.circumsphere=at.circumspherelnd_mod.simplex_volume_in_embedding=at.simplex_volume_in_embeddinglnd_mod.point_in_simplex=at.point_in_simplex# Now use LearnerND as normal — including neighbor-aware losses# like curvature_loss_function()learner=LearnerND(my_function, bounds=[(-1, 1), (-1, 1)])See examples/adaptive_learnernd.py for a full working example with timing comparison.
tri=Triangulation(coords) # Build from initial pointstri.add_point(point) # Incremental insertion → (deleted, added)tri.locate_point(point) # Find containing simplextri.circumscribed_circle(simplex) # → (center, radius)tri.volume(simplex) # Simplex volumetri.volumes() # All simplex volumestri.point_in_simplex(point, simplex) # Containment testtri.simplices_containing(point) # All simplices containing a point, in one call# instead of a point_in_simplex loop; pass a known# containing simplex via simplex=... to skip the# locate step, or restrict with candidates=...tri.point_in_circumcircle(pt, simplex) # Circumcircle testtri.bowyer_watson(pt_index) # Direct Bowyer-Watsontri.get_opposing_vertices(simplex) # Facet neighbours' opposite verticestri.get_simplices_attached_to_points(simplex) # Facet-sharing neighbourstri.reference_invariant() # Consistency checkProperties:vertices, simplices, vertex_to_simplices, hull, dim, default_transform
fromadaptive_triangulationimport (
circumsphere, # General circumspherefast_2d_circumcircle, # Optimized 2Dfast_3d_circumsphere, # Optimized 3Dpoint_in_simplex, # Containment testvolume, # Simplex volumesimplex_volume_in_embedding, # Volume in embedding spacedefault_loss, # LearnerND's default loss (embedded simplex volume),# signature-compatible with loss_per_simplexorientation, # Face orientation
)examples/basic_usage.py— Core API walkthroughexamples/adaptive_learnernd.py— LearnerND integration with timingexamples/benchmark_vs_python.py— Standalone benchmarks across dimensions
Point sets that mix widely separated coordinate scales force sliver simplices that no floating-point predicate can handle reliably.
Unlike the Python reference (which can corrupt its state on such input), this implementation validates every insertion before mutating: a cavity that cannot be re-triangulated is first repaired with exact predicates (Shewchuk's, via the robust crate), and if even that fails the insertion raises with the triangulation untouched, so callers can skip the point and continue.
Well-conditioned inputs behave identically to the reference.
The full policy is documented in src/tolerances.rs.
# Build (requires Rust toolchain)
pip install maturin
maturin develop --release
# Tests
cargo test# Rust tests
python -m pytest tests/ -v # Python tests# Linting
pre-commit run --all-files # ruff, mypy, cargo fmt, cargo clippyBSD-3-Clause