Altere o algoritmo de ativo de inundação para obter o território Voronoi para dois pontos de dados?

Question

Eu tenho uma grade com dois pontos. Quero calcular a quantidade de quadrados que cada ponto pode atingir antes do outro. Atualmente, implemento um algoritmo de athamento de inundação, que pode calcular a quantidade de quadrados que um ponto pode atingir.

Como posso mudar esse algoritmo para fazer a "inundação" para ambos os pontos simaltaneuosly ou pelo menos um após o outro?

Answer 1

O que você quer dizer com "Cada ponto pode alcançar diante do outro"?

Parece -me que você precisa de uma pesquisa de BF. Use uma fila do FIFO como assim:

Seja P1 e P2 as posições dos dois pontos.

Seja f o primeiro elemento na fila e l no último. Inicialmente F = 0, L = 1. Seja q a fila.

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 precisará ser do tamanho da sua grade (linhas x cols). Você pode usar duas matrizes: uma com as posições P1 pode alcançar e a outra com as posições P2 pode alcançar, ou você pode usar uma matriz e marcar os quadrados P1 atinge com números positivos e os quadrados P2 atingem números negativos. Se você estiver interessado onde eles se encontram, só precisará verificar se está prestes a marcar um valor positivo de um valor negativo (POZ negativo e POZ 'positivo) ou o contrário. Isso basicamente fará suas inundações em turnos: inundar um quadrado a partir de P1, depois de P2, depois de P1, depois de P2 e assim por diante.