算法计算一个泰森图上的一个领域？

StackOverflow https://stackoverflow.com/questions/545870

题

我在寻找一个简单的(如果存在的话)的算法找到泰森图设定的点上面的一个领域。源代码将是巨大的。我是德尔福人(是的，我知道...)，但我吃C码。

有帮助吗？

解决方案

下面是在纸球形Voronoi图

或者，如果你神交的Fortran（bleah！）有本网站。

其他提示

更新在日2016年：

由于一些志愿人员(特别是尼古拉Nowaczyk和I)，现在有更强健的/正确的代码，用于处理泰森图在表面上的一个领域中的蟒蛇。这是官方提供的作为 scipy.spatial.SphericalVoronoi 从版本 0.18 对这起。有一个工作实例的使用情况和绘图官 文档.

算法如下二次时间的复杂性。虽然对数线性是理论上的最佳用于泰森图在表面的领域，这是目前最好的我们已经能够实施。如果你想找出更多的帮助与发展努力有一些开放有关的问题改善的办法Python处理球泰森图和相关的数据结构：

为进一步的背景上理论/发展有关的挑战，以这种代码和相关的计算几何努力，你还可以检查出一些谈判从尼古拉和我:

原来的回答：

实际上，我最近写的一些开放源代码，用于泰森图在表面上的一个领域： https://github.com/tylerjereddy/py_sphere_Voronoi

该使用算法，并限制已记录在readthedocs(http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html).还有一些详细的例子有但我会放置一个或两个以下。该模块还处理计算的泰森地区的表面区域，尽管有一些数值的弱点，在当前开发的版本。

我还没有看到许多记录的开放源实现球泰森图，但有一点关于JavaScript实现在杰森*戴维斯的网站(http://www.jasondavies.com/maps/voronoi/).我不认为他的代码是开放的。我也看到了博客中有关使用Python处理问题的一部分(http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/).许多主要文献来源引在上述员额似乎非常具有挑战性的实施(我想他们中的一些)，但也许有些人会找到我的执行情况有益或甚至建议如何改进它。

实例：

1) 产生一个泰森图伪随机设置的点单元的领域：

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) 计算表面区域的泰森地区面和验证的重新组成的表面区域是明智的:

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

请注意，在球体Delaunay三角只是的凸包。 因此可以计算所述3D凸包（例如，使用CGAL） 并采取双

有一个纸从什么样的关于德洛内三角测量(DT)分躺在一个领域： 卡罗曼努埃尔*,et al.强大和有效的德洛内三角的地点或附近的一个领域。2009年。 在那里他们谈论一个实现在 CGAL.

纸张指的是各种可用的执行DT算法。

引用的文件：

一个简单和标准答案，包括在计算3D凸 点，这是众所周知的相当。

用于计算凸纸建议：

  1. 船体，计划为凸船体。
  2. Qhull.
  3. 三维凸船体。 在FORTRAN。三维凸船体。
  4. STRIPACK 在FORTRAN。

DT C++类CGAL有的方法 dual 获得泰森图。

根据 这个职位 由莫尼克Teillaud(一提交人的上面提到的纸)在我看来，在2012年十一月的执行是不是仍然做好准备。

它已经有一段时间，因为该问题已经回答，但我已经找到了两份文件，实施 幸运的算法 (效率O(N lg N)，存储器O(N))的面的领域。也许未来的观察者将会找到这个信息的有用的。

我的工作通过他们自己的那一刻，所以我不能解释得很好。基本的想法是，财富的算法表面上的球那么只要你计算的分的边界抛物线正确。因为表面的领域包裹，也可以使用一个圆形的列表中包含海滩线和不担心处理细胞在边缘的长方形空间。就这样，你可以扫从北极的领域的南部和再度回升，跳过网站介绍新分到海边的线路(加一个抛物线海滩线)或引进的单元折点(除一个抛物线从海滩线)。

这两份文件预期的高水准的舒适用线性代数以理解的概念，并且他们都保留失去我在这一点上，他们开始解释的算法本身。既不提供源代码，不幸的。

我认为可以使用非欧几里得几何构造维诺平面对于每个点。什么是一般2D平面上的一条线，现在是在球体上一个“大圈”（参见维基百科：的椭圆几何学）。这是很容易发现哪些点上两个点之间的任意大圆错误的一边通过简单地旋转球使得分大圆是赤道，然后它在另一半球比你点的所有点构建的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）的。我希望你知道我的意思，随便问：）

CGAL 正在工作的“球形内核”包，这将允许以计算准确这类事情。不幸的是，尚未发布，但也许这将是他们的下一个版本，因为他们已经的中三月一个谷歌的技术对话中提到它

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

  

要计算的点的Delaunay三角剖分上的球体，计算它们的凸包。如果球是在原点的单位球体，小平面法线是输入的沃罗诺伊顶点。

如果您的点是一个半球内，你可以从球形做一个心射投影到平面坐标，然后三角，因为大-圈成为最短距离的直线。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top