# Is there a tool for 3D Delaunay and Voronoi tessellations?

**URL:** <https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503>\
**Category:** Modelling & Simulations\
**Tags:** question, proposal\
**Created:** [January 11, 2019, 3:48am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503 "2019-01-11T03:48:24Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![afas](https://avatars.discourse-cdn.com/v4/letter/a/8dc957/32.png) [@afas](https://discourse.julialang.org/u/afas)\
**Post date:** [January 11, 2019, 3:48am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/1 "2019-01-11T03:48:24Z")

</div>

I am currently migrating all my research software to Julia, and so far I am very pleased with the experience and the relative easiness in transporting code.  
I have, however, reached a bottleneck cause I can’t seem to be able to find any tool to perform a simple non-constrained Delaunay triangulation in three dimensions. As I would really like not to write a ball-pivot algorithm function myself, I was wondering how is everyone doing this, as Delaunay is one of the most standard geometrical transformations used in 3-d modelling?

---

<div class="post-metadata">

**Author:** ![Gnimuc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gnimuc/32/2194_2.png) [@Gnimuc](https://discourse.julialang.org/u/Gnimuc)\
**Post date:** [January 11, 2019, 4:05am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/2 "2019-01-11T04:05:19Z")

</div>

There is a package for 2D Delaunay:

> **[GitHub - JuliaGeometry/VoronoiDelaunay.jl: Fast and robust Voronoi &...](https://github.com/JuliaGeometry/VoronoiDelaunay.jl)**
>
> Fast and robust Voronoi & Delaunay tessellation creation with Julia - GitHub - JuliaGeometry/VoronoiDelaunay.jl: Fast and robust Voronoi & Delaunay tessellation creation with Julia

and JuliaPolyhedra has serveral packages for convex hull:

> **[JuliaPolyhedra](https://github.com/JuliaPolyhedra)**
>
> Polyhedral Computation in Julia. JuliaPolyhedra has 14 repositories available. Follow their code on GitHub.

Currently I use marching cubes for meshing 3D pointclouds.

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [January 11, 2019, 4:18am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/3 "2019-01-11T04:18:51Z")

</div>

Worst case, you can always `ccall` Qhull or use PyCall.jl with `scipy.spatial.Voronoi` (which then calls Qhull).

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 11, 2019, 4:33am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/4 "2019-01-11T04:33:37Z")

</div>

There is already a Julia package wrapping Qhull:

> **[GitHub - JuliaPolyhedra/QHull.jl: A Julia wrapper around a PyCall wrapper...](https://github.com/JuliaPolyhedra/QHull.jl)**
>
> A Julia wrapper around a PyCall wrapper around the qhull Convex Hull library - GitHub - JuliaPolyhedra/QHull.jl: A Julia wrapper around a PyCall wrapper around the qhull Convex Hull library

(It works via Python; might be nice to eventually have a direct wrapper.)

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [January 11, 2019, 4:44am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/5 "2019-01-11T04:44:28Z")

</div>

Qhull.jl only wraps the convex hull part of Qhull though.

---

<div class="post-metadata">

**Author:** ![mkborregaard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkborregaard/32/556_2.png) [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)\
**Post date:** [January 11, 2019, 7:59am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/6 "2019-01-11T07:59:06Z")

</div>

There’s a 4-year-old issue with a suggested implementation: [3D Delaunay · Issue #8 · JuliaGeometry/VoronoiDelaunay.jl · GitHub](https://github.com/JuliaGeometry/VoronoiDelaunay.jl/issues/8)

---

<div class="post-metadata">

**Author:** ![Gnimuc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gnimuc/32/2194_2.png) [@Gnimuc](https://discourse.julialang.org/u/Gnimuc)\
**Post date:** [January 11, 2019, 1:09pm UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/7 "2019-01-11T13:09:50Z")

</div>

so currently the solution is to use [TetGen.jl](https://github.com/JuliaGeometry/TetGen.jl)?

---

<div class="post-metadata">

**Author:** ![sdanisch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sdanisch/32/1406_2.png) [@sdanisch](https://discourse.julialang.org/u/sdanisch)\
**Post date:** [January 11, 2019, 2:03pm UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/8 "2019-01-11T14:03:10Z")

</div>

Tetgen should work reasonably well, but we still haven’t added nice julia API.  
We started to add stuff like parsing the tetgen generated files:

> <https://github.com/JuliaGeometry/TetGen.jl/blob/master/src/TetGen.jl#L45>

But it’s still incomplete. Any help / revival of the issues would be appreciated

---

<div class="post-metadata">

**Author:** ![afas](https://avatars.discourse-cdn.com/v4/letter/a/8dc957/32.png) [@afas](https://discourse.julialang.org/u/afas)\
**Post date:** [January 14, 2019, 10:15pm UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/9 "2019-01-14T22:15:51Z")

</div>

> [@sdanisch](#):
>
> JuliaGeometry/TetGen.jl/blob/master/src/TetGen.jl#L45

Please count me in, as this would be something I will need to implement anyways.

---

<div class="post-metadata">

**Author:** ![afas](https://avatars.discourse-cdn.com/v4/letter/a/8dc957/32.png) [@afas](https://discourse.julialang.org/u/afas)\
**Post date:** [January 14, 2019, 10:17pm UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/10 "2019-01-14T22:17:24Z")

</div>

As far as I understand, Qhull only evaluates the convex hull. Couldn’t find any reference to the Delaunay and/or Voronoi tessellations.

---

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [April 24, 2019, 12:04pm UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/11 "2019-04-24T12:04:13Z")

</div>

This is slightly old, but I just wanted to mention one way to find Delaunay triangulations in arbitrary dimensions `N`. As explained in [Wikipedia](https://en.wikipedia.org/wiki/Delaunay_triangulation), if you know how to compute a convex hull in N+1 dimensions (which is supported by e.g. Polyhedra.jl) you can easily get Delaunay triangulations of N-dimensional points `ps...` by appending `|ps[i]|^2` to each point `ps[i]`, finding the convex hull, and then projecting back to `N` dimensions by removing the last coordinate in the vertices of the resulting hull mesh.

EDIT: I’m not so sure you can use `Polyhedra.jl` to `decompose` a convex hull into its faces in more than 3 dimensions, but you can certainly do it in 3D

---

<div class="post-metadata">

**Author:** ![fverdugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fverdugo/32/9446_2.png) [@fverdugo](https://discourse.julialang.org/u/fverdugo)\
**Post date:** [March 4, 2020, 4:07pm UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/12 "2020-03-04T16:07:00Z")

</div>

In our lab, we have implemented a simple Julia wrapper to Qhull in order to compute Delaunay triangulations in arbitrary dimensions.

> **[GitHub - gridap/MiniQhull.jl: A small Julia wrapper of the Qhull library](https://github.com/gridap/MiniQhull.jl)**
>
> A small Julia wrapper of the Qhull library. Contribute to gridap/MiniQhull.jl development by creating an account on GitHub.

We interface with Qhull via `ccall` (instead of `PyCall` ), so you don’t need to install scipy in your system, just Qhull itself and a C compiler. Moreover, we are using the re-entrant version of Qhull. Thus, our wrapper should be thread-safe (even though we have not confirmed it).

Hope you find the project useful!

---

<div class="post-metadata">

**Author:** ![evetion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/evetion/32/22679_2.png) [@evetion](https://discourse.julialang.org/u/evetion)\
**Post date:** [March 9, 2021, 7:47am UTC](https://discourse.julialang.org/t/is-there-a-tool-for-3d-delaunay-and-voronoi-tessellations/19503/13 "2021-03-09T07:47:44Z")

</div>

For future reference, I’ve made [StarTIN.jl](https://github.com/evetion/StarTIN.jl) a work-in-progress wrapper around [startin](https://github.com/hugoledoux/startin) a robust Delaunay triangulator, itself written in Rust.