Python中的Voronoi划分

Question

节点分配问题

我想解决的问题是，把地图上的蓝色节点（源节点）作为输入点进行平铺。一旦我能做到这一点，我想看看每个区域里有多少黑色节点（需求节点），然后把这些黑色节点分配给对应区域的蓝色节点。

我想知道有没有更简单的方法来实现这个目标，而不使用福尔图恩算法。我发现了一个叫Mahotas的库里的函数，叫做Mahotas.segmentation.gvoronoi(image)来源。但我不确定这个函数能否解决我的问题。

另外，请告诉我有没有更好的方法来进行这种分割（除了Voronoi平铺）。我不确定聚类算法是否是个好选择。我还是个编程新手。

Answer 1

你图上的点不多。这意味着对于每个需求节点，你可以简单地遍历所有的源节点，找到离它最近的那个。

比如这样：

def distance(a, b):
    return sum((xa - xb) ** 2 for (xa, xb) in zip(a, b))

def clusters(sources, demands):
    result = dict((source, []) for source in sources)
    for demand in demands:
        nearest = min(sources, key=lambda s: distance(s, demand))
        result[nearest].append(demand)
    return result

这段代码会给你一个字典，里面记录了每个源节点和所有离它更近的需求节点的列表。

虽然这样做效率不是特别高，但方法很简单！

Answer 2

我刚好在找同样的东西，发现了这个：

https://github.com/Softbass/py_geo_voronoi

Answer 3

这里有一种使用Voronoi划分的替代方法：

首先，建立一个k-d树，这个树是基于源节点（也就是你要找的点）。然后，对于每一个需求节点（你需要服务的点），利用这个k-d树找到离它最近的源节点，并给这个附近的源节点的计数器加一。

关于k-d树的实现，可以参考这个链接：http://code.google.com/p/python-kdtree/，这个应该会很有帮助。