Geometry Boost List: [geometry] Thoughts on adding 3D Delaunay triangulation and subsequent Voronoi diagram?

Subject: [geometry] Thoughts on adding 3D Delaunay triangulation and subsequent Voronoi diagram?
From: Christian Mazakas (christian.mazakas_at_[hidden])
Date: 2017-06-29 16:49:14

So, the ever-arrogant programmer that I am recently discovered that
Boost.Polygon does not support 3D Voronoi diagrams. This simply cannot be!

My proposal is relatively straight-forward, we add a 3D Delaunay
triangulator and use that to implement the Voronoi tessellation for a given
set of points.

Now, before any code is written we must first decide a couple of things.

Namely, we need to discuss the algorithm of the Delaunay triangulator.

I propose that we eschew the perturbative method as outlined in the
Simulation of Simplicity and instead opt to handle the case of a point
being on the face of a tetrahedron directly. This implies that the
algorithm we will use is an incremental construction algorithm with a
jump-and-walk approach. These are relatively straight-forward to implement
and because of that, likely easier to maintain by future developers.

>From there, we can work on making it parallel and the using our underlying
triangulation, we can develop the Voronoi tessellation from that.

Also, support for arbitrary precision seems mandatory and is now an
industry standard.

Unfortunately, this problem is not uniquely solved. There are tons of
libraries out there that already do this kind of stuff but they don't
interface as directly with Boost. I suppose the overall goal of this
library addition would be to give the same functionality but with a better
way of working within the current Boost ecosystem.

Thoughts?

- Chris