更改 FloodFill 算法以获取两个数据点的 Voronoi 区域？

Question

我得到了一个有两个点的网格。我想计算每个点在另一个点之前可以到达的平方数。目前我实现了一个FloodFill-Algoritm，它可以计算一个点可以到达的方块数量。

我如何更改该算法以同时或至少一个接一个地对两个点进行“洪泛”？

Answer 1

“每个点都可以先于另一个点到达”是什么意思？

在我看来你需要找个BF。使用 FIFO 队列，如下所示：

令 p1 和 p2 为两个点的位置。

令 f 为队列中的第一个元素，l 为最后一个元素。最初 f = 0，l = 1。设 Q 为队列。

Q[f] = p1
Q[l] = p2
while ( f <= l )
{
   poz = Q[f];
   ++f;

   for each neighbour poz' of poz
      if poz' hasn't been marked yet
      {
         mark poz'
         add poz' to Q: Q[++l] = poz
      }
}

Q 需要是网格的大小（行 x 列）。您可以使用两个矩阵：一个具有 p1 可到达的位置，另一个具有 p2 可到达的位置，或者您可以使用一个矩阵，并用正数标记 p1 到达的方格，用负数标记 p2 到达的方格。如果您对它们相遇的位置感兴趣，您只需检查您是否要从负值（poz 负值和 poz' 正值）中标记正值，或者反之亦然。这基本上会依次进行泛洪：从 p1 泛洪一个方格，然后从 p2 泛洪，然后从 p1 泛洪，然后从 p2 泛洪，依此类推。