Ändern FloodFill-Algorithmus zu Voronoi Territory für zwei Datenpunkte zu bekommen?

Question

habe ich ein Gitter mit zwei Punkten. Ich will die Menge Quadrate jeder Punkt vor dem anderen erreichen berechnen. Derzeit implementieren ich einen FloodFill-Algoritm, was die Menge der Quadrate einen Punkt erreichen kann, berechnen kann.

Wie kann ich diesen Algorithmus ändern, um die „Überflutung“ für beiden Punkte simaltaneuosly oder zumindest einen nach dem anderen zu tun?

Answer 1

Was meinst du mit „jeder Punkt vor dem anderen erreichen kann“?

Es scheint mir, wie Sie eine BF suchen müssen. Verwenden Sie eine FIFO-Warteschlange wie folgt:

Lassen Sie P1 und P2 sind die Positionen der beiden Punkte sein.

sei f das erste Element in der Warteschlange und l die letzten. Zunächst f = 0, l = 1. Es sei Q die Warteschlange sein.

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 muss die Größe des Rasters sein (Zeilen x Spalten). Sie können zwei Matrizen verwenden: ein mit den Positionen p1 erreichen kann und die andere mit den Positionen P2 erreichen kann, oder können Sie eine Matrix verwenden, und markieren Sie die Quadrate P1 erreicht mit positiven Zahlen und die Quadrate P2 erreicht mit negativen Zahlen. Wenn Sie interessiert sind, wo sie sich treffen, müssen Sie nur, wenn Sie im Begriff sind, um einen positiven Wert von einem negativen Wert (POZ negativ und POZ‘positiv) oder die andere Art und Weise zu markieren. Dies wird im Grunde tun, um Ihre Überschwemmungen in Kurven: Flut ein Quadrat aus p1, dann von p2, dann aus p1, dann von p2 und so weiter.