5 ms·
While the stereographic prohection trick sounds neat, it looks like it could produuce a bad triangulation if the input points are distributed non-uniformly. Ind
by vbarrielle 8y ago
While the stereographic prohection trick sounds neat, it looks like it could produuce a bad triangulation if the input points are distributed non-uniformly. Indeed the 2d Delaunay triangulation algorithm tries to build the most uniform triangulation, but the projection step creates distortion which means a uniform projected triangulation might map to a non-uniform 3d triangulation.
I'm not sure it is an issue because some other factor may compensate this issue, but there should be a rigorous analysis of the stability of this approach to various inputs.
- amelius 8y agoI'm not sure if delaunay by itself would produce "regular" triangulations. To get some kind of regularity, you'd generally need a refinement step where more points are inserted. Of course, this could be difficult with the given projection.
- vbarrielle 8y agoYeah I used regular as a shorthand but nostly I meant that it would flip edges to avoid thin triangles.
- amitp 8y agoSee section 8.5 of http://www.cis.upenn.edu/~cis610/convex8.pdf http://www.cis.upenn.edu/~cis610/convex8.pdf for the analysis showing that the stereographic projection is the projection that preserves the properties needed for Delaunay triangulation. I learned this technique from Philippe Riviere, who uses it in the d3-geo-voronoi library - https://beta.observablehq.com/collection/@fil/voronoi https://beta.observablehq.com/collection/@fil/voronoi