Teste si le point est dans un rectangle

J'ai une grande collection de rectangles, tous de la même taille. Je suis de la génération aléatoire des points qui ne doivent pas tomber dans ces rectangles, donc ce que je voudrais faire, c'est de tester si l'généré point se trouve dans l'un des rectangles, et si elle le fait, générer un nouveau point.

À l'aide de R-arbres semblent fonctionner, mais ils sont vraiment conçus pour les rectangles et pas des points. Je pourrais utiliser une version modifiée d'un R-tree algorithme qui fonctionne avec des points de trop, mais je préfère ne pas réinventer la roue, si il y a déjà une meilleure solution. Je ne suis pas très familier avec les données des structures, donc peut-être qu'il existe déjà une structure qui fonctionne pour mon problème?

En résumé, en gros ce que je demande, c'est si quelqu'un connaît un bon algorithme, qui fonctionne en Python, qui peut être utilisée pour vérifier si un point se trouve dans tout rectangle dans un ensemble donné de rectangles.

edit: C'est en 2D et les rectangles ne sont pas en rotation.

source d'informationauteur pafcu | 2009-12-13