更改此时，floodFill算法得到的Vor​​onoi区域的两个数据点？ [英] Change FloodFill-Algorithm to get Voronoi Territory for two data points?

问题描述

我有一个网格连得两分。我想计算的金额广场每个点都可以在另一个之前到达。目前，我实现此时，floodFill-Algoritm，由此可以计算平方的一个点可以达到的数量。

I got a grid with two points. I want to calculate the amount squares each point can reach before the other. Currently I implement a FloodFill-Algoritm, which can calculate the amount of squares one point can reach.

我怎样才能改变这种算法做了洪水为点simaltaneuosly或至少一个又一个？

How can I change that algorithm to do the "flooding" for both points simaltaneuosly or at least one after another?

推荐答案

你是什么意思？

在我看来像你需要一个BF的搜索。使用FIFO队列，像这样：

It looks to me like you need a BF search. Use a FIFO queue like so:

让p1和p2是两个点的位置。

Let p1 and p2 be the positions of the two points.

设f是队列和L最后的第一个元素。最初F = 0，升= 1设q是队列中。

let f be the first element in the queue and l the last. Initially f = 0, l = 1. Let Q be the queue.

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
      }
}

问：将需要你的网格（行×COLS）的大小。你可以用两个矩阵：一个位置P1可以达到和其他与位置P2可以达到，或者你可以使用一个矩阵和标记P1达到与正数和的平方P2达到与负数的平方。如果你有兴趣，他们遇见，你只需要检查，如果你即将从负值标志着正值（POZ消极和POZ正）或其他方式。这将基本上做你的水浸轮流：洪水一平方从P1，然后从P2，然后从P1，然后从p2和等。

Q will need to be the size of your grid (rows x cols). You can use two matrices: one with the positions p1 can reach and the other with the positions p2 can reach, or you can use one matrix and mark the squares p1 reaches with positive numbers and the squares p2 reaches with negative numbers. If you are interested where they meet, you just need to check if you are about to mark a positive value from a negative value (poz negative and poz' positive) or the other way around. This will basically do your flooding in turns: flood one square from p1, then from p2, then from p1, then from p2 and so on.

这篇关于更改此时，floodFill算法得到的Vor​​onoi区域的两个数据点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！