Эффективно найти ближайшее неконфликтное положение для прямоугольника в 2D-пространстве? ⇐ Python

[Anonymous]

Я боролся с проблемой, связанной с обнаружением столкновений и позиционированием в 2D-пространстве, и мне действительно хотелось бы получить некоторые рекомендации по достижению хорошей производительности.
У меня есть прямоугольная граница (синий). Внутри этого пространства находится список сталкивающихся геометрий, включая контурные линии и другие прямоугольники (отмечены красным). Кроме того, у меня есть другие прямоугольники (отмечены зеленым), которые не должны сталкиваться с красными.
Когда зеленый прямоугольник сталкивается с красным прямоугольником, мне нужно определить ближайшие допустимые позиции для зеленый прямоугольник, который гарантирует, что он не перекрывается ни с одним из красных прямоугольников и линий.
ОТРЕДАКТИРОВАНО: зеленые прямоугольники не всегда имеют одинаковый размер. Зеленых прямоугольников может быть до 24, а количество красных линий и многоугольников может превышать 40 и более. Зеленые прямоугольники могут перекрываться друг с другом.


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


Ожидаемый результат должен предоставить ближайшие допустимые центральные позиции для зеленого прямоугольника, классифицированные по движение по разным осям:

• Только ось X: (14.5, 7.5)
• Только ось Y: [ (5.5, 14.5)]
• Обе оси: (4.5, 8.5)

Подробнее здесь: https://stackoverflow.com/questions/790 ... n-2d-space