I have a bunch of polygons and a coarse uniform grid. I want to implement two different range queries, for a rectangle aligned with the uniform grid:

  1. Does the rectangle intersect with any polygon at all?
  2. Give me all the polygons which intersect the rectangle.

A simple data-structure would be to have for each cell a list of pointers to the polygons that overlap the cell. This data-structure is appropriate for the first range query. It seems less appropriate for the second range query, because the same polygon may overlap multiple cells, and we don't want to report the same polygon multiple times. One solution would be to use a std::set<polygon_t*> container to collect the pointers to polygons that are delivered by a query. However, let's assume I mistrust std::set in the sense that it will do too many memory allocations even if I reuse the same container for multiple queries. (This mistrust may be unfounded, so I should definitively try this first.)

I wonder whether the problem can be solved more efficiently, if I replace the polygons by their "grid aligned" bounding boxes. During a range query, the knowledge of the lower left point of the bounding box should be sufficient for determining whether the polygon corresponding to the box has already been reported. But even in this case, the complexity of a query returning $m$ polygons won't be $O(m)$, because some work is done for every cell intersecting the bounding box of the polygon. I wonder whether creating three additional lists with the polygons whose bounding box starts in this cell in "x-direction", "y-direction" and "x- and y-direction" allowing to avoid this additional work would be a good idea. Instead of creating new lists, I could also try to just partition the existing list appropriately.

In general, the coarse uniform grid based data-structures discussed above offer essentially constant lookup time, at the cost of potentially high memory consumption. What is the state of the art regarding such data-structures? Is there a way to avoid the potential memory bloat caused by elements with huge bounding boxes which overlap many grid cells? Also, I don't like the fact that only the simple data-structure can handle polygons directly, while the more efficient data-structures only handle the bounding boxes of the polygons.


Your Answer

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

Browse other questions tagged or ask your own question.