Используя Python, как мне узнать, перекрываются ли прямоугольник и фигура?

Question

Я пишу программу на Python. У меня есть серия фигур (многоугольники, определенные как последовательность пар координат), и мне нужно сказать, перекрывают ли они определенный прямоугольник.

Есть ли простой алгоритм для обработки этого? Или, лучше, есть чистая библиотека Python, которая может обрабатывать эти вычисления для меня?

Answer 1

Предполагая, что ваши "произвольные фигуры" действительно являются полигонами (учитывая, что они описаны как пары координат), определить, перекрываются ли они (на любом языке), - относительно тривиальное вычисление. Вам просто нужно вычислить, пересекает ли любая сторона полигона A любую другую сторону многоугольника B.

Если вам нужен пример, на Математическом форуме Drexel .

есть довольно подробное описание.

Существует ряд модулей Python, которые могут помочь вам в этом деле, например Sympy , Numpy , PyGame и т. Д., Но все они довольно тяжелые, если это единственный геометрический расчет, который вам нужно сделать.