高效地将一个区域划分为多个部分Python

Question

我有一个正方形的网格，其中一些点被标记为网格子部分的中心。我希望能够将网格中的每个位置分配到正确的子部分。例如，如果区域的子部分以黑点为中心，我希望能够将红点指定给右下角的区域，因为它是最近的黑点。在

目前，我通过迭代每个可能的红点，并比较其与每个黑点的距离来实现这一点。然而，网格中黑点的宽度、长度和数量都很高，所以我想知道是否有更有效的算法。在

我的特定数据是这样格式化的，其中数字只是与给定示例相对应的占位符：

black_dots = [(38, 8), (42, 39), (5, 14), (6, 49)]
grid = [[0 for i in range(0, 50)] for j in range(0, 50)]

作为参考，在这个例子中，我希望能够用整数1、2、3、4填充grid，这取决于它们是否最接近第1、第2、第3，或者第四个黑点的输入，最后得到一个类似于下面图片的东西，其中每个整数对应于一种颜色（点被留下来显示）。在

总而言之，有没有/有什么更有效的方法？在

Answer 1

“8路”Voronoi图可以通过两次扫描线过程有效地构建（在线性时间内与像素数相对应）。（8向表示距离计算为两个像素之间最短的8连通路径的长度。）

为每个中心指定一个不同的颜色，并创建一个与图像大小相同的距离数组，在中心初始化为0，在其他地方初始化为“无穷大”。在

在自上而下/从左到右的过程中，将所有像素的距离更新为W、NW、N和NE四个邻居的距离的最小值加1，并为当前像素指定达到最小值的邻居的颜色。在

在自下而上/从右到左的过程中，将所有像素的距离更新为当前距离的最小值以及四个邻居E、SE、S、SW加一的距离，并为当前像素指定达到最小值的邻居的颜色（或保持当前颜色）。在

---

也可以有效地（在线性时间内）计算欧几里德Voronoi图，但这需要更复杂的算法。它可以基于一篇精彩的论文《计算距离的通用算法》 “线性时间变换”，作者：A.MEIJSTER'J.B.T.M.ROERDINK和W.H.HESSELINK，必须通过对造成最小距离的邻居的一些考虑来增强这一点。在

Answer 2

您可以使用宽度优先遍历来解决这个问题。在

1. 创建先进先出队列。（队列首先进行遍历宽度。）

2. 创建一个访问掩码，指示网格中的单元格是否已添加到队列中。将遮罩设置为false。

3. 创建一个父遮罩，指示该单元最终属于哪个黑点。

4. 将所有的黑点放入队列中，在访问的掩码中标记它们，并在父掩码中为它们分配唯一的id。

5. 开始从队列中逐个弹出单元格。对于每个单元格，迭代该单元格的邻居。在它的父队列中，在它的每一个被访问的单元格中设置为相等的值。

6. 继续，直到队列为空。

宽度优先遍历产生一个从每个源单元向外扩展的波（黑点）。因为所有的波都以相同的速度穿过你的网格，每一个波都会吞噬离它的源最近的那些细胞。在

这在O（N）时间内解决了这个问题。在

Answer 3

如果我理解正确，你真正需要的是构建一个你的中心的Voronoi图：

https://en.m.wikipedia.org/wiki/Voronoi_diagram

它可以非常有效地构造出与计算其凸壳相似的计算复杂度。在

Voronoi图允许您构建围绕中心的最佳多边形，从而划分最接近中心的区域。在

有了Voronoi图，任务就减少到检测红点所在的多边形。由于Voronoi单元是凸的，你需要一个算法来确定一个点是否在凸多边形内。然而，遍历所有多边形的复杂性为O（n）。在

有几种算法可以加速点定位，因此可以在O（logn）中完成：

https://en.m.wikipedia.org/wiki/Point_location

另请参见

Nearest Neighbor Searching using Voronoi Diagrams