有效地将一个区域分成几部分 Python
Eve*_*lse 2 python algorithm geometry computer-vision computational-geometry
我有一个方形网格，其中一些点被标记为网格子部分的中心。我希望能够将网格内的每个位置分配给正确的子部分。例如，如果该区域的子部分以黑点为中心，我希望能够将红点分配给右下角的区域，因为它是最近的黑点。
目前，我通过迭代每个可能的红点，并将其与每个黑点的距离进行比较来做到这一点。然而，网格中黑点的宽度、长度和数量都非常高，所以我想知道是否有更有效的算法。
我的特定数据的格式如下，其中数字只是与给定示例相对应的占位符：
black_dots = [(38, 8), (42, 39), (5, 14), (6, 49)]
grid = [[0 for i in range(0, 50)] for j in range(0, 50)]
作为参考，在示例案例中，我希望能够填充grid整数 1、2、3、4，具体取决于它们是否最接近 black_dots 中的第 1 个、第 2 个、第 3 个或第 4 个条目，最终得到一些结果这将允许我创建类似于下图的东西，其中每个整数对应于一种颜色（保留点以供显示）。
总而言之，有/什么更有效的方法可以做到这一点？
可以使用广度优先遍历来解决这个问题。
创建先进先出队列。（队列进行广度优先遍历。）
创建一个 Visited 掩码，指示网格中的单元格是否已添加到队列中。将掩码设置为 false。
创建一个父蒙版，指示单元格最终属于哪个黑点。
将所有黑点放入队列中，在 Visited 掩码中标记它们，并在 Parent 掩码中为它们分配唯一的 id。
开始从队列中一一弹出单元格。对于每个单元格，迭代该单元格的邻居。将每个邻居放入队列中，在“已访问”中标记它，并将其在“父”中的值设置为等于您刚刚弹出的单元格的值。
继续直到队列为空。
广度优先遍历产生一个从每个源单元格（黑点）向外扩展的波。由于波都以相同的速度穿过网格，因此每个波都会吞噬最接近其源的那些单元。
这在O(N)时间内解决了问题。