Cambiar FloodFill-Algoritmo para obtener Territorio de Voronoi de dos puntos de datos?

Question

Tengo una cuadrícula con dos puntos. Quiero calcular los cuadrados cantidad que cada punto puede llegar antes que el otro. Actualmente implemento un FloodFill-Algoritm, que puede calcular la cantidad de cuadrados de un punto puede alcanzar.

¿Cómo puedo cambiar el algoritmo para hacer la "inundación" para ambos puntos simaltaneuosly o, al menos, uno tras otro?

Answer 1

¿Qué quiere decir con "cada punto puede llegar antes que el otro"?

A mi me parece como que necesita una búsqueda BF. Utilizar una cola FIFO de esta manera:

Deje que p1 y p2 sean las posiciones de los dos puntos.

sea F el primer elemento en la cola y l la última. Inicialmente f = 0, l = 1. Sea Q la cola.

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 tendrá que ser el tamaño de la cuadrícula (filas x cols). Se pueden utilizar dos matrices: una con las posiciones P1 puede alcanzar y el otro con las posiciones P2 puede alcanzar, o puede utilizar una matriz y marcar las casillas P1 alcanza con números positivos y los cuadrados p2 alcanza con números negativos. Si usted está interesado en que se encuentran, sólo tiene que comprobar si está a punto de marcar un valor positivo de un valor negativo (POZ negativo y POZ' positivo) o al revés. Básicamente, esto hará que su inundaciones en turnos: inundar un cuadrado de p1, p2 desde entonces, después de p1, p2 desde entonces y así sucesivamente.