Pergunta

I'm looking for the most efficient spatial-indexing data-structure for storing and querying bounding boxes which contain individual points. The points represent 2D coordinates on a grid, while the bounding boxes represent regions of the grid. The bounding boxes may vary greatly in size, and multiple bounding boxes may overlap a single point. Both points and bounding boxes are stored as signed integers.

For example, in the diagram below, if I were to query points $B$ and $C$, I'd expect a single bounding box in return. However, if I query point $A$, I'd expect an array containing both bounding boxes in return.

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

I'm not concerned with insert/remove efficient for adding bounding-boxes to the structure as all bounding-boxes are added to the structure during a one-time initialization. My main concern is efficient look-ups for finding which bounding boxes contain a point, as such queries will be made frequently.

My initial thought is to use a quadtree, and to test all objects contained in a particular node to see if they contain the point being queried. However, I'm wondering: is there a better data-structure I could use to implement this behavior with?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top