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

Question

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

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

Answer 1

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

Мне кажется, вам нужен поиск БФ.Используйте очередь 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, отрицательными числами.Если вам интересно, где они встречаются, вам просто нужно проверить, собираетесь ли вы отметить положительное значение от отрицательного значения (позитивное и позитивное) или наоборот.По сути, это будет выполнять наводнение по очереди:затопить одну клетку с п1, потом с п2, потом с п1, потом с п2 и так далее.