39

我正在寻找一种简单的（如果存在）算法来找到球体表面上一组点的 Voronoi 图。源代码会很棒。我是一个德尔福人（是的，我知道......），但我也吃 C 代码。

4

11 回答 11

26

2016 年 7 月更新：

感谢许多志愿者（尤其是 Nikolai Nowaczyk 和我），现在有更健壮/正确的代码来处理 Python 中球体表面上的 Voronoi 图。这scipy.spatial.SphericalVoronoi从0.18scipy 版本开始正式可用。官方文档中有一个使用和绘图的工作示例。

该算法遵循二次时间复杂度。虽然对数线性是球体表面上 Voronoi 图的理论最优值，但这是目前我们能够实现的最佳值。如果您想了解更多信息并帮助开发工作，有一些与改进 Python 处理球形 Voronoi 图和相关数据结构的方式相关的未解决问题：

有关与此 Python 代码和相关计算几何工作相关的理论/开发/挑战的进一步背景，您还可以查看 Nikolai 和我的一些谈话：

原答案：

实际上，我最近为球体表面的 Voronoi 图编写了一些开源 Python 代码：https ://github.com/tylerjereddy/py_sphere_Voronoi

用法、算法和限制记录在 readthedocs ( http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html ) 上。那里有一些详细的示例，但我也会在下面放置一两个。该模块还处理 Voronoi 区域表面积的计算，尽管在当前开发版本中存在一些数值弱点。

我还没有看到很多有据可查的球形 Voronoi 图的开源实现，但是 Jason Davies 的网站 ( http://www.jasondavies.com/maps/voronoi/ )上的 JavaScript 实现引起了一些关注。 . 我不认为他的代码是开放的。我还看到了一篇关于使用 Python 处理部分问题的博客文章（http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code /）。上述帖子中引用的许多主要文献来源似乎很难实施（我尝试了其中一些），但也许有些人会发现我的实施很有用，甚至提出改进它的方法。

例子：

1)为单位球面上的一组伪随机点生成 Voronoi 图：

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)

在此处输入图像描述

2)计算 Voronoi 区域多边形的表面积并验证重构的表面积是否合理：

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
于 2014-11-27T12:29:10.700 回答
12

这是一篇关于球形 Voronoi 图的论文。

或者，如果您了解 Fortran（哎呀！），这里有这个网站。

原文链接（死）：https ://people.sc.fsu.edu/~jburkardt/f_src/sxyz_voronoi/sxyz_voronoi.html

于 2009-02-13T13:34:58.370 回答
8

请注意，球体上的 Delaunay 三角剖分只是凸包。因此，您可以计算 3D 凸包（例如使用 CGAL）并采用对偶。

于 2012-12-20T10:32:38.810 回答
3

简而言之，试试NCAR Graphics的cssgrid。我在 codereview.stackexchange.com 上为类似问题写了更长的答案。

于 2012-03-19T05:32:46.580 回答
3

INRIA 有一篇关于球面上点的德劳内三角剖分 (DT) 的论文：CAROLI、Manuel 等。对球体上或球体附近的点进行稳健且高效的 Delaunay 三角剖分。2009.他们谈论在CGAL中的实现。

本文参考了 DT 算法的各种可用实现。

引用论文：

一个简单而标准的答案是计算点的 3D 凸包，这是众所周知的等价。

为了计算凸包，本文建议：

  1. Hull，凸包程序。
  2. 库尔。
  3. 三维凸包。在 FORTRAN 中。三维凸包。
  4. FORTRAN 中的STRIPACK。

CGAL的DT C++类有dual获取Voronoi Diagram的方法。

根据Monique Teillaud（上述论文的作者之一）的这篇文章，在我看来，2012 年 11 月的实施还没有准备好。

于 2013-06-20T20:25:44.590 回答
3

已经有一段时间没有回答这个问题了，但是我发现了两篇论文在球体表面上实现了Fortune 的算法（效率 O(N lg N)，内存 O(N)）。也许未来的观众会发现这些信息很有用。

我目前正在自己​​处理它们，所以我无法很好地解释它。基本思想是，只要您正确计算点的边界抛物线，Fortune 的算法就可以在球体表面上工作。因为球体的表面包裹，您也可以使用圆形列表来包含海滩线，而不必担心处理矩形空间边缘的单元格。这样，您可以从球体的北极向南扫过并再次返回，跳到向海滩线引入新点的站点（向海滩线添加抛物线）或引入单元顶点（移除海滩线的抛物线）。

这两篇论文都希望对线性代数理解这些概念有很高的舒适度，并且在他们开始解释算法本身的时候，他们都一直在迷失我。不幸的是，它们都不提供源代码。

于 2013-09-23T00:50:08.813 回答
2

我认为可以使用非欧几里得几何构造每个点的 Voronoi 平面。通常是二维平面上的一条线，现在是球体上的一个“大圆”（参见维基百科：椭圆几何）。很容易找到两个点之间的任何大圆的错误一侧的点，只需旋转球体，使分割大圆是赤道，然后它是另一个半球上的所有点而不是你所在的点构建 Voronoi 平面。

这不是完整的答案，但这是我要开始的地方..

于 2009-06-23T21:04:22.553 回答
1

这里有一个很好的 Voronoi 图示例程序（包括 Delphi 5/6 的源代码）。

我认为“球体表面上的点”意味着您首先必须将它们重新映射到 2D 坐标，创建 Voronoi 图，然后将它们重新映射到球体表面坐标。维基百科 UV 映射文章中的两个公式在这里有效吗？

另请注意，Voronoi 图将具有错误的拓扑结构（它在矩形内并且不会“环绕”），在这里它可以帮助将所有点从 (0,0)-(x, y) 复制到邻居高于 (0, -y * 2)-(x, 0)、低于 (0, y)-(x, y * 2)、左侧 (-x, 0)-(0, y) 和右侧 (x, 0)-(x*2, y)。我希望你知道我的意思，随时问:)

于 2009-02-13T13:20:11.870 回答
1

CGAL正在研究“球形内核”包，它可以精确地计算这些东西。不幸的是，还没有发布，但可能会在他们的下一个版本中，因为他们已经在三月份的谷歌技术演讲中提到了它

于 2009-06-19T12:11:18.143 回答
1

引用此参考：http ://www.qhull.org/html/qdelaun.htm

要计算球体上点的 Delaunay 三角剖分，请计算它们的凸包。如果球体是原点的单位球体，则面法线是输入的 Voronoi 顶点。

于 2013-04-01T05:35:30.920 回答
0

如果您的点在一个半球内，您可以从球面坐标到平面坐标进行晷投影，然后进行三角测量，因为大圆变成最短距离的直线。

于 2011-04-15T18:28:44.423 回答