Ищем алгоритм "грубой силы", чтобы удалить пересекающиеся области коллекции Rects

Question

У меня есть коллекция Rects размера n, большинство из которых пересекаются друг с другом.Я хотел бы удалить пересечения и сократить пересекающиеся Rects в меньшие непересекающиеся rects.

Я мог бы легко перебрать решение, но я ищу эффективный алгоритм.

Вот визуализация:

Оригинал:

Обработано:

В идеале сигнатура метода должна выглядеть следующим образом:

public static List<RectF> resolveIntersection(List<RectF> rects);

результат будет больше или равенвход, где выход разрешает вышеуказанное визуальное представление.

Answer 1

Алгоритмы Sweepline хороши при обработке пересечений в 2D вселенных.Я имею в виду рассмотреть горизонтальную линию, перемещающуюся от края прямоугольника к следующему краю прямоугольника.Линия попадает в ряд прямоугольников, образуя так называемые активные списки.Активный список обновляется при каждом движении.

Изучая диапазоны абсцисс вдоль горизонтальной линии, вы можете обнаружить перекрытия.

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

Answer 2

это проблема, которую я решил в прошлом. Первым делом это отсортировать прямоугольники по значению x или y одного из ребер. Допустим, вы заказываете в направлении у и используете верхний край. Самый верхний прямоугольник в вашем примере - первый в отсортированном порядке. Для каждого прямоугольника вы знаете его размер в направлении у.

Теперь для каждой записи (назовите ее текущей записью, она соответствует прямоугольнику) в отсортированном списке вы просматриваете список вперед, пока не достигнете записи, превышающей текущую запись + соответствующий размер прямоугольника. (назовите это остановкой)

Любые записи в отсортированном списке между текущей записью и этой останавливающей записью будут потенциальными пересечениями. Просто проверьте, пересекаются ли x-диапазоны прямоугольников.

При выборе сортировки в направлении x или y, лучше выбрать размер, который больше, так как это будет означать меньшее пересечение в среднем, а значит меньше проверки.

Вот пример. Прямоугольники определяются как R (x1, x2, y1, y2), где x1 - левая сторона, x2 - правая сторона, y1 - верхняя, а y2 - нижняя

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8)
rectangle 3 (2,4,2,3)
rectangle 4 (3,6,3,7)
rectangle 5 (3,6,9,15)

сортировка по y1 для получения

#              y1  size
rectangle 1     0   4
rectangle 3     2   3
rectangle 4     3   4
rectangle 2     6   2
rectangle 5     9   6

Итак, прямоугольник 1 имеет y1 + size = 0 + 4 = 4, что означает, что он потенциально пересекает прямоугольник 3 (значение y1 = 3 <4) и прямоугольник 4 (значение y1 = 3 <4), но не прямоугольник 2 (значение y1 = 6> 4) ... нет необходимости проверять какие-либо прямоугольники в списке после 2

Прямоугольник 3 имеет y2 + size = 2 + 3 = 5, подразумевая, что он потенциально пересекает прямоугольник 4 (значение y1 = 3 <5), но не повторяет 2 (значение y1 = 6> 5), нет необходимости проверять любые прямоугольники в список после 2

Прямоугольник 4 имеет y2 + size = 3 + 4 = 7, подразумевая, что он потенциально пересекает прямоугольник 2 (значение y1 = 6 <7), но не повторяет 5 (значение y1 = 9> 7)

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

Answer 3

то, что вы описываете - это проблема упаковки, посмотрите на wikipedia

это относится к этой статье, описывающей алгоритм упаковки прямоугольников в прямоугольники

это из статьи:

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