#triangulation #delaunay #refinement #incremental #bowyer-watson


Delaunay Triangulation and Refinement implementation through Bowyer Watson incremental insertion, conflict maps and ghost vertices

2 releases

0.1.1 May 1, 2020
0.1.0 May 1, 2020

#1213 in Algorithms

Custom license

1.5K SLoC

Rust Delaunay Triangulation


This repository implements Delaunay Triangulation in Rust, according to this reference [1].

The major objective is to implement a 3D refinement in pure Rust, so that it may be portable to wasm-pack applications.

I've searched for some packages in open repositories. There were good jobs and efficient implementations (svew, mourner, tynril, ucarion, d-dorazio), but none are extensible to this purpose. Some lack documentation, some follow other approaches.


The approach is to implement Bowyer Watson incremental insertion algorithm, with ghost triangles and conflict graph . This approach is extensible to 3D, given the proper handle to sliver exudation and smooth surfaces.

The choice for Rust is due to its portability in sereral rust contexts and its integration to Javascript through wasm-pack .

Task List

- [x] 2D Delaunay Triangulation
- [ ] publishing release to crates.io
- [ ] 2D Delaunay Refinement

- [ ] 3D Delaunay Triangulation
- [ ] 3D Delaunay Refinement


  • Standard Delaunay Triangulation
  • Incremental Vertex Insertion
  • Decremental Vertex Deletion
  • Holes
  • Refinement (in progress)
  • Tetrahedralization (in progress)


In progress


At first, clone the repository, with a cargo environment. Fork it if you want. Run the tests. Read the code.

Open an issue with suggestions, code reviews, refactoring.


  1. Cheng, Siu-Wing; Dey, Tama Krishna; Shewchuk, Jonathan Richard. Delaunay Mesh Generation. 2013 by Taylor & Francis Group, LLC.


~70K SLoC