Interroger toutes les boîtes de délimitation qui contiennent un point

Question

Je recherche la structure de données d'indexation spatiale la plus efficace pour stocker et interroger les boîtes de délimitation qui contiennent des points individuels. Les points représentent les coordonnées 2D sur une grille, tandis que les boîtes de délimitation représentent les régions de la grille. Les boîtes de délimitation peuvent varier considérablement en taille et plusieurs boîtes de délimitation peuvent chevaucher un seul point. Les points et les boîtes de délimitation sont stockés comme des entiers signés.

Par exemple, dans le diagramme ci-dessous, si je devais interroger les points B $ et $ C $, je m'attendais à une seule boîte de délimitation en retour. Cependant, si je interroge Point $ a $, je m'attendais à un tableau contenant les deux boîtes de délimitation en retour.

--------     
| B  ============
|    |A|        |
-----|--     C  |
     ============

Je ne suis pas préoccupé par l'insert / supprimer efficace pour ajouter des boîtes à limites à la structure car toutes les boîtes de limites sont ajoutées à la structure lors d'une initialisation unique. Ma principale préoccupation est des recherches efficaces pour trouver les boîtes de délimitation contiennent un point, car de telles requêtes seront faites fréquemment.

Ma pensée initiale est d'utiliser un quadtree et de tester tous les objets contenus dans un nœud particulier pour voir s'ils contiennent le point interrogé. Cependant, je me demande: y a-t-il une meilleure structure de données avec laquelle je pourrais utiliser pour implémenter ce comportement?