Изменить алгоритм FloodFill, чтобы получить территорию Вороного для двух точек данных?

Получилась сетка с двумя точками. Я хочу рассчитать количество квадратов, которые каждая точка может достичь раньше другой. В настоящее время я реализую FloodFill-Algoritm, который может вычислять количество квадратов, которых может достичь одна точка.

Как я могу изменить этот алгоритм, чтобы «заливать» обе точки одновременно или хотя бы одну за другой?


algorithm flood-fill voronoi
person Sven    schedule 18.02.2010    source источник
comment
Приветствую вас, участник конкурса Google AI :)   -  person Rafał Dowgird    schedule 18.02.2010
comment
Спасибо, вы это уже реализовали или у вас другая стратегия?   -  person Sven    schedule 18.02.2010
comment
Я сделал, просто используя своего рода одновременную BFS из двух точек - аналогично ответу IVlad.   -  person Rafał Dowgird    schedule 18.02.2010

Ответы (1)


arrow_upward
2
arrow_downward

Что вы имеете в виду под «каждая точка может достигнуть раньше другой»?

Мне кажется, вам нужен поиск BF. Используйте очередь FIFO следующим образом:

Пусть p1 и p2 - положения двух точек.

пусть f будет первым элементом в очереди, а l последним. Первоначально f = 0, l = 1. Пусть Q - очередь.

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 должен быть размером вашей сетки (строки x столбцы). Вы можете использовать две матрицы: одна с позициями, которых может достичь p1, а другая с позициями, которых может достичь p2, или вы можете использовать одну матрицу и пометить квадраты, которых достигает p1, положительными числами, а квадраты, которых достигает p2, - отрицательными числами. Если вам интересно, где они встречаются, вам просто нужно проверить, собираетесь ли вы пометить положительное значение из отрицательного значения (poz negative и poz 'положительное) или наоборот. Это в основном будет заливать вас по очереди: заливать один квадрат из точки p1, затем из точки p2, затем из точки p1, затем из точки p2 и так далее.

person IVlad    schedule 18.02.2010