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

Question

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

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

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

Оригинал:

Обработанный:

В идеале подпись метода будет выглядеть так:

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

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

Answer 1

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

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

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

При выборе сортировки в направлении 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 2

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

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

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

Answer 3

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

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

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

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