Python中的Voronoi Tessellation

Question

节点分配问题

我想解决的问题是将蓝色节点(源节点)给出的地图镶嵌为给定的输入点,一旦我能够做到这一点,我想看看有多少黑节点(需求节点)落在每个小区内,将其分配给与该单元关联的蓝色节点.

我想知道在没有使用Fortune算法的情况下是否有更简单的方法.我在Mahotas下遇到了这个函数,名为Mahotas.segmentation.gvoronoi(image)source.但我不确定这是否能解决我的问题.

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

Answer 1

以下是使用Voronoi曲面细分的另一种方法:

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

在http://code.google.com/p/python-kdtree/上找到的kd树的实现应该很有用.