0
$\begingroup$

I am trying to find a reasonable data structure for representing a partition of an (axis aligned) rectangular domain into a set of (axis aligned) rectangles.

I need to be able to look up for a given point which (unique) rectangle contains it.

So far I have taken a look at Quadtrees, and this seems reasonable to me - where I recursively subdivide the domain into patches.

People have also mentioned RTrees, but I do not see how these can help me in such single point queries.

$\endgroup$
1
$\begingroup$

Quadtrees sounds like a good choice.

How about the k-d tree of 2 dimension, which is also explained in a course note and at geeksforgeeks?

Each of the 2-dimensional versions of interval tree, range tree and segment tree may have a fair chance to solve the question efficiently.

I have used all above data structures to solve the same or similar or more complex queries. Depending on your situation, you may want to make some adjustment.

If the number of given points is much smaller than the number of possible points in the given rectangle domain, such as 22000 points in a $10^{18}$ by $10^{18}$ square, then some other choice might be even better. I once used a red-black tree, whose leaf nodes is another red-black tree and whose internal nodes of the same parent represent a partition of the contiguous rows represented by their parent into disjoint contiguous set of rows. The red-black tree at each leaf node stores the points in one particular row. In this way (and with a bit more technique), my final answer is able to run the fastest among all solution to the problem. Of course, my example may not be useful to your situation at all. Well, I hope that might encourage you to develop your own data structure that fits your situation more.

$\endgroup$
0
$\begingroup$

As mentioned in the other answer, quadtrees are a good choice.

R-Trees should also work well, they often cope better with clustered data but they tend to be slower to build or update. If you dataset changes, check out the R*tree, if you can bulk load it (no changes afterwards), check out the STR-Loaded R-Tree. If your R-Tree does not support point queries, just query for a rectangle which represents a point (all corners have the same coordinate).

If you are using Java, check you my PH-Tree. It's a bit like a quadtree, but copes better with clustered data. For containment queries it's speed depends on the average number of rectangles that contain a search-point. If there are usually few (less than 5-10) rectangles that contain your point, then it may be the fastest three you can find. If you expect 100 or 1000 of rectangles to overlap with your point, R-Trees may be better.

If you want to implement the structure yourself, quadtrees and kd-trees are probably simplest, R-Trees are harder, PH-Tree may be even more difficult to get right. Quadtrees are harder to get right than they look, because for large/clustered datasets you may quickly run into precision problems.

If you are using Java, have a look at my implementations of quadtree, R*Tree, STR-Tree and PH-Tree here (there is also a kd-tree, but it doesn't suppor rectangle entries, only points).

$\endgroup$

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.