Архив форумов ЦИТФорума

[Mystique]

Нужен алгоритм, разбивающий кучу прямоугольников на группы пересекающихся областей. Т.е. например, если пересекаются прямоугольники с номерами 1,2,3 в одной группе(например пересекаются 1 и 2, 2 и 3) и 4,5 в другой группе, то выходом должен быть список:
1,2,3
4,5
Простой перебор и сравнение каждого с каждым не проходит (слишком долго). Подскажите пожалуйста идейку алгоритма, работающего по шустрее...

[JekLove]

сначала отсортировать список прямоугольников по x- или y-координате. Число проверок значительно уменьшится (в общем случае).

[Chea]

Для найденной группы создай прямоугольник содержащий всю группу и проверяй его. Если с ним нет пересечения то нет пересечения и с прямоугольниками группы

[Mystique]

Очень часто попадаются варианты, когда одна группа наползает на другую по Х и по У, но на самом деле они не пересекаются (пример: две группы, расположенные под 45 градусов к горизонту, идущие более-менее параллельно друг к другу). Опознаются, как одна группа.
Что бы тут можно еще придумать? Чувствую, что можно как-то приспособиться с сортировкой, но как-то хитрее...

[Mystique]

Попробовал. Действительно стало шустрее. Спасибо. Но, к сожалению, не намного, т.к. исходные данные в большинстве ситуаций идут большим количеством групп, каждая из которых состоит из 3-5 областей. Так что ускорилось где-то в те самые раза 3. К сожалению, надо еще шустрее... Посоветуйте еще что-нибудь, если не сложно... Заранее большое спасибо!

[Борис]

-

[Mystique]

Дык, мне бы и идейки хватило бы... Ну не представляю я, как можно сделать еще шустрее... Именно к классу сложности N*logN я и стремлюсь...

[Борис]

-

[Chea]

В общих чертах идея следующая
1 Сортируем по горизонтали
2 Проверяем последовательно N и N+1 если не пересекаются то и предыдущие не пересекаются следовательно группы разные. Таким образом выделяем подгруппы.
3 Каждую подгруппу сортируем по вертикали
4 Проверяем последовательно в каждой подгруппе M и M+1 Получаем группы.

В таком варианте есть ряд дополнительных условий, но как кажется может получиться

[Mystique]

Сорри, а что это? Если не трудно, можно чуть подробне? Заранее спасибо!

[Mystique]

Все бы хорошо, только вот одна беда: если следующая группа начинается раньше, чем заканчивается другая (после сортировки), то первая группа (та, что начиналась раньше) будет разбита этой точкой на 2. К моему огромному сожалению, такая ситуация тоже достаточно часто встречается...

PS Огромное спасибо за помощь! Еще немного и мы найдем правильный вариант алгоритма. Подскажи пожалуйста, как бы модифицировать это, чтобы решить описанную проблемку?

[Chea]

1 Тогда используемый алгоритм надо несколько модифицировать: анализировать после сортировки обе координаты - думаю на 2-м этапе (это значительно усложняет и увеличивает время)
2 Предлагаю для пробы еще 1 вариант:
а) Сортируем все п-ки по возрастанию по Х по верхнему-левому (с указанием длины по Х) Пример: Пр-к (2,3-10,5) сортируется с использованием 2 (для i-го пр-ка обозначим Хi1)и с этой двойкой тянется 8=10-2 (в сортировке не участвует - обозначим Хi2).
б)Строим граф (матрица М) где вершины Vi - прямоугольники.
Дуга от Vi к Vj строится если Xi1+Xi2 больше чем Xj1 (j больше i) M[i,j]=M[i,j]+1 для всех j пока выполняется условие Xi1+Xi2 больше Xj1
в) Сортируем Все пр-ки по Y так же как по Х
г) Дополняем граф М новыми дугами по следующему условию:
Дуга от Vj к Vi строится если Yi1+Yi2 больше чем Yj1 (j больше i) обрати внимание на индексы при построении дуг М[j,i]=M[j,i]+1 для всех j пока выполняется условие Yi1+Yi2 больше Yj1
д) В результате получаем матрицу NxN с 0,1 и 2
Из матрицы получаем группы:
К одной группе относятся вершины (пр-ки) которые имеют дуги друг к другу M[i,j]=M[j,i]=1 или 2 вершины когда из одной вершины две дуги во вторую вершину (M[i,j]=2)
т.е. проходя плностью строку и анализируя все элементы получаем список (индексы j) прямоугольников в группе.

Алгоритм срабатывает при крестах и полных охватах. Однако если есть повернутые пр-ки то требуется доработка(использовать охватывающие пр-ки, выполнять поворот, наложение по слоям и т.д.)
мой e-mail: cheanews@yandex.ru
Удачи.