我要解决的问题是将蓝色节点（源节点）作为给定输入点的地图进行细分，一旦我能够做到这一点，我想看看每个单元格中有多少黑色节点（需求节点）和将其分配给与该单元格关联的蓝色节点。
我想知道是否有更简单的方法可以在不使用 Fortune 算法的情况下执行此操作。我在 Mahotas 下遇到了这个名为 Mahotas.segmentation.gvoronoi(image) source的函数。但我不确定这是否能解决我的问题。
如果有更好的分割方法（Voronoi tessellation 除外），也请建议我。我不确定聚类算法是否是一个不错的选择。我是一个编程新手。
这是使用 Voronoi 细分的另一种方法：
在源节点上构建一个 kd 树。然后对于每个需求节点，使用 kd 树查找最近的源节点并增加与该附近源节点关联的计数器。
在http://code.google.com/p/python-kdtree/中找到的 kd 树的实现应该很有用。
我一直在寻找同样的东西，发现了这个：
我认为https://stackoverflow.com/users/1062447/wye-bee的空间索引答案（例如 kd-tree）是解决您问题的最简单方法。
此外，您还问过财富算法是否有更简单的替代方案，对于这个特定问题，我建议您参考：最容易实现的 Voronoi 图算法？
您的图表中没有很多点。这表明您可以对于每个需求节点，只需遍历所有源节点并找到最近的一个。
也许是这样：
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
此代码将为您提供一个字典，将源节点映射到所有需求节点的列表，这些节点比任何其他节点都更接近该源节点。
这不是特别有效，但非常简单！
在 Mathematica 中运行此代码。太壮观了！（是的，我知道它不是 Python，但是......）
pts3 = RandomReal[1, {50, 3}];
ListDensityPlot[pts3,
InterpolationOrder -> 0, ColorFunction -> "SouthwestColors", Mesh -> All]
您没有说明为什么要避免使用 Fortune 算法。我假设您的意思是您只是不想自己实现它，但是 Bill Simons 和 Carston Farmer 已经在脚本中实现了它，因此计算 voronoi 图应该不难。
在他们的脚本的基础上，我使它更易于使用，并以 Pytess 的名称将其上传到PyPi。因此，您可以使用基于蓝色点的 pytess.voronoi() 函数作为输入，返回原始点及其计算的 voronoi 多边形。然后，您必须通过多边形点测试来分配每个黑点，您可以基于http://geospatialpython.com/2011/08/point-in-polygon-2-on-line.html进行测试。
