有效地将一个区域分成多个部分 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，取决于它们是否最接近1st，2nd，3rd，或 black_dots 中的第 4 个条目以最终允许我创建类似于下图的内容的内容结束，其中每个整数对应一种颜色（保留点以供显示）。

总而言之，是否有/什么是更有效的方法？

Answer 1

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

创建先进先出队列。（队列使遍历广度优先。）
创建一个 Visited 掩码，指示您的网格中的单元格是否已添加到队列中。将掩码设置为 false。
创建一个父掩码，指示单元格最终属于哪个黑点。
将所有黑点放入队列中，在 Visited mask 中标记它们，并在 Parent mask 中为它们分配唯一的 id。
开始从队列中一个一个地弹出单元格。对于每个单元格，迭代单元格的邻居。将每个邻居放入队列中，在 Visited 中对其进行标记，并将其在 Parent 中的值设置为等于您刚刚弹出的单元格的值。
继续直到队列为空。

广度优先遍历产生一个从每个源单元格（黑点）向外扩展的波浪。由于波浪都以相同的速度穿过您的网格，因此每个波浪都会吞噬最靠近其源头的细胞。

这在 O(N) 时间内解决了问题。

Answer 2

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

它可以非常有效地构建，其计算复杂度与计算其凸包相似。

Voronoi 图允许您构建围绕中心的最佳多边形，这些多边形划定了最靠近中心的区域。

有了 Voronoi 图，任务就减少到检测红点位于哪个多边形中。由于 Voronoi 单元是凸的，因此您需要一种算法来确定点是否在凸多边形内。然而遍历所有多边形的复杂度为 O(n).

有几种算法可以加速点定位，因此可以在 O(log n) 中完成：

另见

Nearest Neighbor Searching using Voronoi Diagrams

Answer 3

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

为每个中心分配不同的颜色并创建一个与图像大小相同的距离数组，在中心用 0 初始化，在其他地方用 "infinity" 初始化。

在top-down/left-right遍中，将所有像素的距离更新为W、NW、N和NE四个邻居的距离中的最小值加一，并为当前像素分配颜色达到最小值的邻居。

在bottom-up/right-left遍中，将所有像素的距离更新为当前距离和四个邻居E，SE，S，SW的距离加一的最小值，并分配当前像素达到最小值（或保持当前颜色）的邻居的颜色。

也可以高效地（线性时间）计算 欧几里德 Voronoi 图，但这需要更复杂的算法。它可以基于精彩的论文“计算距离的通用算法” 线性时间变换”，作者：A. MEIJSTER，J.B.T.M。ROERDINK 和 W.H。HESSELINK，必须通过计算导致最小距离的邻居来增强。

Divide a region into parts efficiently Python