Изменить алгоритм FloodFill, чтобы получить территорию Вороного для двух точек данных?
-
21-09-2019 - |
Вопрос
У меня получилась сетка с двумя точками.Я хочу вычислить количество квадратов, которых может достичь каждая точка раньше другой.В настоящее время я реализую алгоритм FloodFill, который может вычислять количество квадратов, которых может достичь одна точка.
Как я могу изменить этот алгоритм, чтобы выполнять «наводнение» для обеих точек одновременно или, по крайней мере, одну за другой?
Решение
Что вы подразумеваете под «каждая точка может достичь раньше другой»?
Мне кажется, вам нужен поиск БФ.Используйте очередь 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 и так далее.