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

[Anonymous]

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

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

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