Hi, I'm looking for a simple (if exists) algorithm to find the Voronoi diagram for a set of points on the surface of a sphere. Source code would be great. I'm a Delphi man (yes, I know...), but I eat C-code too. TIA Steven
A:
There's a nice Voronoi diagram example program here (including source code for Delphi 5/6).
I think "points on the surface of a sphere" means that you first have to remap them to 2D-coordinates, create the Voronoi diagram and then remap them to sphere surface coordinates. Are the two formulas from Wikipedia UV mapping article working here?
Also notice that the Voronoi diagram will have the wrong topology (it is inside a rectangle and does not "wrap around"), here it could help to copy all the points from (0,0)-(x, y) to the neighbour regions above (0, -y * 2)-(x, 0), below (0, y)-(x, y * 2), left (-x, 0)-(0, y) and right (x, 0)-(x*2, y). I hope you know what I mean, feel free to ask :)
schnaader
2009-02-13 13:20:11
I thought about remapping to a 2D plane but that doesn't work; AFAIK there's no sphere-to-plane mapping which preserves distance. Simple example: distances between any pair of vertices a regular tetrahedron are the same, but you can't draw this in a 2D plane.Thanks for your reply anyway.
stevenvh
2009-02-13 14:06:50
+4
A:
I don't have ACM document access but there's a paper on spherical Voronoi diagrams.
Or if you grok Fortran (bleah!) there's this site.
Jason S
2009-02-13 13:34:58
For me, there's a download link for the paper here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.6737 - it is not that helpful though...
schnaader
2009-02-13 14:10:50
A:
CGAL is working on the "spherical kernel" package, which would allow to compute exactly these kind of things. Unfortunately, is not released yet, but maybe it will be in their next release, since they already mentioned it in a google tech talk in march
balint.miklos
2009-06-19 12:11:18
+1
A:
I think the Voronoi plane for each point can be constructed using non-Euclidian geometry. What was normally a line on a 2d plane, is now a 'great circle' on the sphere (see Wikipedia:elliptic geometry). It is easy to find which points are on the wrong side of any great circle between two points, by simply rotating the sphere such that the dividing great circle is the equator, and then it's all points on the other hemisphere than the point you're constructing the Voronoi plane for.
This is not the entire answer, but this is where I'd start..