Algorithm to compute a Voronoi diagram on a sphere

2019-01-21 05:00发布

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.

11条回答
女痞
2楼-- · 2019-01-21 05:19

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 :)

查看更多
欢心
3楼-- · 2019-01-21 05:24

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..

查看更多
姐就是有狂的资本
4楼-- · 2019-01-21 05:29

Notice that Delaunay triangulation on a sphere is just the convex hull. Thus you can compute the 3D convex hull (e.g. using CGAL) and take the dual.

查看更多
Bombasti
5楼-- · 2019-01-21 05:29

There is a paper from INRIA about the Delaunay Triangulation (DT) of points lying on a sphere: CAROLI, Manuel, et al. Robust and Efficient Delaunay triangulations of points on or close to a sphere. 2009. where they talk about an implementation in CGAL.

The paper refers to various available implementation of DT algorithms.

Quoting from the paper:

An easy and standard answer consists in computing the 3D convex hull of the points, which is notoriously equivalent.

for computing the convex hull the paper suggests:

  1. Hull, a program for convex hulls.
  2. Qhull.
  3. Three-dimensional convex hulls. in FORTRAN.Three-dimensional convex hulls.
  4. STRIPACK in FORTRAN.

The DT C++ class of CGAL has the method dual to get the Voronoi Diagram.

According to this post by Monique Teillaud (one of the author of the above mentioned paper) it seems to me that in November 2012 the implementation was not still ready.

查看更多
该账号已被封号
6楼-- · 2019-01-21 05:30

If your points are within one hemisphere, you could do a gnomonic projection from spherical to planar coordinates, and then triangulate, since great-circles become straight lines of shortest distance.

查看更多
做个烂人
7楼-- · 2019-01-21 05:37

Update in July 2016:

Thanks to a number of volunteers (especially Nikolai Nowaczyk and I), there is now far more robust / correct code for handling Voronoi diagrams on the surface of a sphere in Python. This is officially available as scipy.spatial.SphericalVoronoi from version 0.18 of scipy onwards. There's a working example of usage and plotting in the official docs.

The algorithm follows quadratic time complexity. While loglinear is the theoretical optimum for Voronoi diagrams on the surfaces of spheres, this is currently the best we've been able to implement. If you'd like to find out more and help with the development effort there are some open issues related to improving the way Python handles spherical Voronoi diagrams and the related data structures:

For further background on the theory / development / challenges related to this Python code and related computational geometry efforts you can also check out some talks from Nikolai and I:


Original Answer:

I've actually recently written some open source Python code for Voronoi diagrams on the surface of a sphere: https://github.com/tylerjereddy/py_sphere_Voronoi

The usage, algorithm, and limitations are documented on readthedocs (http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html). There are some detailed examples there but I'll place one or two below as well. The module also handles the calculation of the Voronoi region surface areas, albeit with some numerical weaknesses in the current development version.

I haven't seen many well-documented open source implementations for spherical Voronoi diagrams, but there has been a bit of buzz about the JavaScript implementation on Jason Davies' website (http://www.jasondavies.com/maps/voronoi/). I don't think his code is open though. I also saw a blog post about using Python to deal with part of the problem (http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/). Many of the primary literature sources cited in the above posts seemed very challenging to implement (I tried some of them) but maybe some people will find my implementation useful or even suggest ways to improve it.

Examples:

1) Produce a Voronoi diagram for a pseudo-random set of points on the unit sphere:

import matplotlib
import matplotlib.pyplot as plt
import matplotlib.colors as colors
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np
import scipy as sp
import voronoi_utility
#pin down the pseudo random number generator (prng) object to avoid certain pathological generator sets
prng = np.random.RandomState(117) #otherwise, would need to filter the random data to ensure Voronoi diagram is possible
#produce 1000 random points on the unit sphere using the above seed
random_coordinate_array = voronoi_utility.generate_random_array_spherical_generators(1000,1.0,prng)
#produce the Voronoi diagram data
voronoi_instance = voronoi_utility.Voronoi_Sphere_Surface(random_coordinate_array,1.0)
dictionary_voronoi_polygon_vertices = voronoi_instance.voronoi_region_vertices_spherical_surface()
#plot the Voronoi diagram
fig = plt.figure()
fig.set_size_inches(2,2)
ax = fig.add_subplot(111, projection='3d')
for generator_index, voronoi_region in dictionary_voronoi_polygon_vertices.iteritems():
   random_color = colors.rgb2hex(sp.rand(3))
   #fill in the Voronoi region (polygon) that contains the generator:
   polygon = Poly3DCollection([voronoi_region],alpha=1.0)
   polygon.set_color(random_color)
   ax.add_collection3d(polygon)
ax.set_xlim(-1,1);ax.set_ylim(-1,1);ax.set_zlim(-1,1);
ax.set_xticks([-1,1]);ax.set_yticks([-1,1]);ax.set_zticks([-1,1]); 
plt.tick_params(axis='both', which='major', labelsize=6)

enter image description here

2) Calculate the surface areas of the Voronoi region polygons and verify that the reconstituted surface area is sensible:

import math
dictionary_voronoi_polygon_surface_areas = voronoi_instance.voronoi_region_surface_areas_spherical_surface()
theoretical_surface_area_unit_sphere = 4 * math.pi
reconstituted_surface_area_Voronoi_regions = sum(dictionary_voronoi_polygon_surface_areas.itervalues())
percent_area_recovery = round((reconstituted_surface_area_Voronoi_regions / theoretical_surface_area_unit_sphere) * 100., 5)
print percent_area_recovery
97.87551 #that seems reasonable for now
查看更多
登录 后发表回答