4

我将使用一组数千个点。我可以实现或使用现有的财富算法实现来生成点的 Voronoi 图，但我的应用程序还要求我知道每个 Voronoi 单元的邻接关系。

更具体地说，对于任何 Voronoi 单元，我需要知道与其相邻的单元。在这一点上，我不关心输出或存储方法，因为我可能会按摩实现以对我有利。

有没有人知道算法，或者更好地知道可以完成小区邻接确定的已实现算法？我将要做的工作是在 python 中，但任何事情都会很棒，因为我可以轻松地翻译代码。

谢谢！

4

3 回答 3

11

尽管这是一个老问题，但我一直在寻找相同的问题，并认为答案可能对某人仍有帮助。可以Delaunay从scipy模块中使用。

from scipy.spatial import Delaunay
from collections import defaultdict
import itertools

points=[[0.0, 0.0], [0.0, 1.0], [0.2, 0.5], [0.3, 0.6], [0.4, 0.5], [0.6, 0.3], [0.6, 0.5], [1.0, 0.0], [1.0, 1.0]]
tri = Delaunay(points)
neiList=defaultdict(set)
for p in tri.vertices:
    for i,j in itertools.combinations(p,2):
        neiList[i].add(j)
        neiList[j].add(i)

for key in sorted(neiList.iterkeys()):
    print("%d:%s" % (key,','.join([str(i) for i in neiList[key]])))

0:1,2,5,7
1:0,8,2,3
2:0,1,3,4,5
3:8,1,2,4,6
4:2,3,5,6
5:0,2,4,6,7
6:8,3,4,5,7
7:8,0,5,6
8:1,3,6,7
   
# This is for visualization
from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt
vor = Voronoi(points)
voronoi_plot_2d(vor)
for i,p in enumerate(x):
    plt.text(p[0], p[1], '#%d' % i, ha='center')
plt.show()

在此处输入图像描述

于 2013-05-28T12:51:27.560 回答
3

你可以通过几种不同的方式做到这一点。

如果您只能访问 Voronoi 图，则可以在单元格之间寻找共享的边缘段。如果您发现两个单元格共享一个 Voronoi 边缘段，则意味着它们是相邻的。为整个数据集构建邻接信息的一种有效方法是通过扫描 Voronoi 单元列表来构建边缘哈希表。

for (all cells in voronoi diagram)
    for (all edges in current cell)
        if (matching edge found in hash table)
            // the current cell is adjacent to the cell that added
            // the matching edge segment to the hash table
        else
            // push current edge segment onto hash table and mark with 
            // current cell index
        endif
    endfor
endfor

有许多很好的现有软件包可用于计算点集的 Voronoi 图/Delaunay 三角剖分。由于它是一种计算成本高且对数值敏感的操作，我建议坚持使用现有的库。Triangle和QHull包被广泛使用。

希望这可以帮助。

于 2012-03-11T09:42:26.227 回答
1

此处提供了一种可能的算法 ，该算法使用线性规划方法。

PuLP 可以生成 MPS 或 LP 文件并调用GLPK、COIN、CPLEX和GUROBI来解决线性问题。

PuLP是用 Python 编写的 LP 建模器，可用于在 Python 中对该线性程序进行建模，然后使用GLPK求解。

于 2012-03-11T08:00:33.367 回答