Teste se o ponto está em algum retângulo

Eu tenho uma grande coleção de retângulos, todos do mesmo tamanho. Estou gerando pontos aleatórios que não devem cair nesses retângulos, então o que eu quero fazer é testar se o ponto gerado está em um dos retângulos e, se isso acontecer, gerar um novo ponto.

O uso de árvores R parece funcionar, mas elas são realmente destinadas a retângulos e não a pontos. Eu poderia usar uma versão modificada de um algoritmo de R-tree que também funciona com pontos, mas prefiro não reinventar a roda, se já houver alguma solução melhor. Eu não estou muito familiarizado com estruturas de dados, então talvez já exista alguma estrutura que funcione para o meu problema?

Em resumo, basicamente o que eu estou perguntando é se alguém sabe de um bom algoritmo, que funciona em Python, que pode ser usado para verificar se um ponto está em qualquer retângulo em um determinado conjunto de retângulos.

edit: Isso é em 2D e os retângulos não são girados.