Ищете алгоритм «грубой силы» для удаления пересекающихся областей коллекции Rects

Question

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

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

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

Оригинал:

Обработано:

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

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

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

Answer 1

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

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

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

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

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

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), но не recatngle 2 (значение y1 = 6> 5) нет необходимости проверять любые прямоугольники в списке после 2

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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