Cambiare FloodFill-algoritmo per ottenere Voronoi Territorio per due punti dati?

Question

Ho una griglia con due punti. Voglio calcolare la quantità piazze ogni punto può raggiungere prima che l'altro. Attualmente implemento un FloodFill-Algoritm, in grado di calcolare la quantità di quadrati un punto può arrivare.

Come faccio a cambiare la situazione algoritmo per fare il "flooding" per entrambi i punti simaltaneuosly o almeno uno dopo l'altro?

Answer 1

Che cosa si intende per "ogni punto può arrivare prima degli altri"?

Sembra a me come avete bisogno di una ricerca BF. Utilizzare una coda FIFO in questo modo:

Lasciate P1 e P2 siano le posizioni dei due punti.

Sia F il primo elemento della coda e l l'ultimo. Inizialmente f = 0, l = 1. Sia Q coda.

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 dovrà essere la dimensione della griglia (righe x colonne). È possibile utilizzare due matrici: una con le posizioni P1 può raggiungere e l'altra con le posizioni p2 può raggiungere, oppure è possibile utilizzare una matrice e segnare le piazze p1 raggiunge con numeri positivi e le piazze p2 raggiunge con i numeri negativi. Se siete interessati, dove si incontrano, non vi resta che verificare se si è in procinto di segnare un valore positivo da un valore negativo (POZ negativo e POZ' positivo) o viceversa. Questo sarà essenzialmente fare la tua inondazioni a turno: inondare un quadrato da p1, p2 poi da, poi da p1, poi da p2 e così via.