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

Использование R-деревьев, кажется, работает, но они действительно предназначены для прямоугольников, а не точек. Я мог бы использовать модифицированную версию алгоритма R-дерева, которая работает и с точками, но яНе буду изобретать велосипед, если уже есть какое-то лучшее решение. Я'Я не очень знаком со структурами данных, так что, возможно, уже существует структура, которая подходит для моей проблемы?

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

редактировать: это в 2D и прямоугольники не повернуты.