4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @Evil Efficient look-ups. I'm trying to avoid iterating over all bounding boxes testing if they contain a point, as points will be queried frequently. All the bounding boxes would be initialized and inserted into the structure at once, and would never be updated after that one-time initialization. Both the points and bounding boxes are stored using signed integers. The points represent 2D coordinates on a grid, and bounding boxes represent regions on that grid. Lastly, there is no set maximum amount of bounding boxes or points. $\endgroup$ – jocopa3 Jan 6 '17 at 3:29
  • 1
    $\begingroup$ Ok, this is quite important, could you edit your question to include it? Have you considered something like the 2D interval tree? $\endgroup$ – Evil Jan 6 '17 at 3:34
  • 1
    $\begingroup$ In 1D, we could solve this with an interval tree or segment tree; the queries you mentioned are called "stabbing queries". Perhaps there are analogous data structures for 2D rectangles -- it sounds like maybe Evil knows more. (Maybe en.wikipedia.org/wiki/Interval_tree#Higher_dimensions or en.wikipedia.org/wiki/…) Anyway, maybe that gives you an additional search term you can use. $\endgroup$ – D.W. Jan 6 '17 at 4:07
  • $\begingroup$ Thanks for the suggestions. I have heard of 2D interval trees, but I haven't found much information on implementing 2D interval trees containing 2D rectangles. Most of my searches for implementing a 2D interval tree or 2D segment tree lead me to implementations of quadtrees; however, I will do a bit more research. $\endgroup$ – jocopa3 Jan 6 '17 at 4:50
  • $\begingroup$ You would have to try it out, especially the expected result size plays a big role. In my experience, STR-Trees are best if you expect to find 1000 or more intersections with your query rectangle (or query point). For fewer intersections, you may get better results with quadtrees or even a PH-tree. $\endgroup$ – TilmannZ Jan 6 '17 at 16:21
5
$\begingroup$

Use a 2-d segment tree. Assuming we have $n$ items, construction takes time $O(n \cdot \log^2(n))$ and each query takes $O(\log^2(n))$ time. These times become $O(n \cdot \log(n))$ and $O(\log(n))$ time, respectively, if we use fractional cascading and lowest-level interval tree. These are good times unless there is more problem structure.


The query is called "multi-dimensional stabbing query" or "point enclosure query".

Range tree involves finding points in a query range. Segment tree involves finding rectangles that contain a query point.

On an unrelated note, one might wish to use an R-tree with sort-tile-recursive (STR) bulk-loading. This leads to almost no overlap between bounding boxes for a node's children and the structure is balanced. If we are lucky (i.e. R-tree involves heuristics and we wish to avoid ties for each component), the structure is good for moderate number of dimensions because factor of $d \cdot \log(n)$ for time is lower than $\log^{\textrm{max}(d - 1, 1)}(n)$ (noting that $d \geq 1$). We take advantage of fact that use of R-tree does not involve cloning primitives. Also, nearest neighbor via heuristic can perform quite well with R-tree, which seems to be something that that excels at w.r.t. segment tree and range tree. Additionally, one might wish to for dynamic structure use an R*-tree or one might wish to for slightly more dimensions use an X-tree. The more dimensions one has, the more likely linear scan is more affordable via a kind of "curse of dimensionality".

Further, if one has only distances and no absolute locations, a metric tree will prove useful. Structures that assume rectangle primitives will be aided by fact that a point is a degenerate rectangle. A pair of points that act as opposite corners of a rectangle can be turned into one point via a "corner transformation" from Pagel 1993.

One strategy that may be used with R-tree is augmenting it with "look-ahead" and edge checks to get guaranteed theoretically acceptable time for a query such as point enclosure query. This is even when it seems an R-tree is designed specifically for this kind of query.

References

  • Pagel et al. - The transformation technique for spatial objects revisited (1993)
$\endgroup$
  • $\begingroup$ Just to add some information, for the suggested bulk-loading, Sort-Tile-Recursive (STR) loading is likely the most common approach. For C++, there is an implementation in Boost. $\endgroup$ – TilmannZ Jan 6 '17 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.