更改FloodFill算法以獲得兩個數據點的Voronoi區域？

Question

我得到了一個兩點的網格。我想計算每個點可以在另一個點之前達到的數量平方。目前我實現了FloodFill-Algoritm，它可以計算一點可以達到的平方量。

我該如何改變這個算法來爲兩個點都進行「泛洪」，或者至少一個接一個地進行？

Answer 1

你所說的「每個點都可以在另一個之前達到」呢？

它在我看來像你需要一個BF搜索。使用如下的FIFO隊列：

設p1和p2爲兩點的位置。

設F是在隊列中和升最後的第一個元素。最初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 cols）的大小。您可以使用兩個矩陣：一個位置p1可以達到，另一個位置p2可以達到，或者您可以使用一個矩陣並標記正方形p1到達，正方形p2達到負數。如果你對他們見面的地方感興趣，你只需要檢查你是否要從負值標記正值（poz negative和poz'positive）或者反過來。這將基本上輪流進行你的淹水：從p1，然後從p2，然後從p1，然後從p2，等等氾濫一個方格。