3 ms·
There's an algorithm that does it. I wrote a hobby implementation ten years ago. Basically, it's a modification of the sweeping line algorithm that sweeps the s
by orthoxerox 4mo ago
There's an algorithm that does it. I wrote a hobby implementation ten years ago. Basically, it's a modification of the sweeping line algorithm that sweeps the sphere from pole to pole.
edit: Found the code. Looks like I instead ended up simply building a convex hull (which is the Delaunay triangulation) and deriving the Voronoi diagram from it.
- srean 4mo agoFor spherical geometry you should not need to do anything special, no ? Compute the Voronoi tessellation as usual and then project the linear separators back to the sphere (by connecting points on it to centre and extending the ray to the spherical surface).
- orthoxerox 4mo agoYeah, but that's basically projecting 3D geometry back onto the sphere (which is also what I ultimately did). There's a faster algorithm that does it "on the sphere", which I thought I used, but turns out I was wrong. I think it was this one: https://www.math.kent.edu/~zheng/papers/voronoi_paper_updated.pdf https://www.math.kent.edu/~zheng/papers/voronoi_paper_update... or this one http://nautilus.fc.ul.pt/jd/jd10sphere.pdf http://nautilus.fc.ul.pt/jd/jd10sphere.pdf
- srean 4mo agoAh! I see. Thanks for the reference.