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

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

0 голосов
/ 18 февраля 2010

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

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

1 Ответ

2 голосов
/ 18 февраля 2010

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

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

...