Python 中的 Voronoi 曲面细分

Question

节点分配问题

我要解决的问题是用蓝色节点（源节点）给定的地图进行细分）作为给定的输入点，一旦我能够做到这一点，我想查看每个单元格内有多少黑色节点（需求节点）并将其分配给与该单元格关联的蓝色节点。

我想知道是否有一种更简单的方法可以在不使用财富算法的情况下完成此操作。我在 Mahotas 下遇到了这个名为 Mahotas.segmentation.gvoronoi(image) 的函数来源。但我不确定这是否能解决我的问题。

另外请建议我是否有更好的方法来进行此分割（除了 Voronoi 曲面细分）。我不确定聚类算法是否是一个不错的选择。我是一个编程新手。

Answer 1

你没有说为什么你想避开《财富》的算法。我假设您的意思是您只是不想自己实现它，但是 Bill Simons 和 Carston Farmer 已经在脚本中实现了它，因此计算 voronoi 图应该不难。

在他们的脚本的基础上，我让它更容易使用，并将其上传到 PyPi，名称为 Pytess.因此，您可以使用基于蓝点的 pytess.voronoi() 函数作为输入，返回原始点及其计算的 voronoi 多边形。然后，您必须通过多边形内的点测试来分配每个黑点，您可以基于 http://geospatialpython.com/2011/08/point-in-polygon-2-on-line.html。

Answer 2

在 Mathematica 中运行此代码。太壮观了！ （是的，我知道它不是 Python，但是...）

pts3 = RandomReal[1, {50, 3}];
ListDensityPlot[pts3, 
    InterpolationOrder -> 0, ColorFunction -> "SouthwestColors", Mesh -> All]

       

Answer 3

这是使用 Voronoi 曲面细分的另一种方法：

在源节点上构建 kd 树。然后，对于每个需求节点，使用 kd 树查找最近的源节点并递增与该附近源节点关联的计数器。

kd 树的实现位于 http://code.google.com/p/python- kdtree/ 应该有用。

Answer 4

我一直在寻找同样的东西，发现了这个：

https://github.com/Softbass/py_geo_voronoi

Answer 5

你的图中没有太多点。这表明，对于每个需求节点，您可以迭代所有源节点并找到最近的一个。

也许是这样的：

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 6

我认为 https://stackoverflow.com/users/1062447/wye-bee 的空间索引答案（A例如 kd-tree）是解决您的问题的最简单的解决方案。

此外，您还问是否有比《财富》算法更简单的替代方案，对于这个特定问题，我建议您参考：最容易实现的 Voronoi 图算法？