更改FloodFill-Algorithm以获得两个数据点的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泛洪，依此类推。