Changer FloodFill-algorithme pour obtenir le territoire Voronoi pour deux points de données?

Question

Je suis une grille avec deux points. Je veux calculer les carrés montant chaque point peut atteindre avant que l'autre. Actuellement je mets en œuvre une FloodFill-Algoritm, qui permet de calculer la quantité de carrés d'un point peut atteindre.

Comment puis-je changer cet algorithme pour faire le « inondation » pour les deux points de simaltaneuosly ou au moins l'un après l'autre?

Answer 1

Que voulez-vous dire par « chaque point peut atteindre avant que l'autre »?

Il me semble que vous avez besoin d'une recherche BF. Utiliser une file d'attente FIFO comme ceci:

Laissez p1 et p2 soient les positions des deux points.

soit f du premier élément dans la file d'attente et l dernier. Initialement, f = 0, l = 1. Soit Q la file d'attente.

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 devra être la taille de votre réseau (lignes x CLO). Vous pouvez utiliser deux matrices: une avec les positions p1 peut atteindre et l'autre avec les positions p2 peut atteindre, ou vous pouvez utiliser une matrice et marquer les carrés p1 atteint avec des chiffres positifs et les places p2 atteint avec des chiffres négatifs. Si vous êtes intéressé où ils se rencontrent, il vous suffit de vérifier si vous êtes sur le point de marquer une valeur positive d'une valeur négative (POZ négative et POZ » positif) ou l'inverse. Ce sera essentiellement faire vos inondations dans les virages: inonder un carré de p1, puis de p2, puis de p1, puis de p2 et ainsi de suite.