2
$\begingroup$

I have N (~100M) points in 2D and M (~10k) non-overlapping axis-parallel rectangles. I'm looking for an algorithm to assign each point to a rectangle it is contained in (or say that it is outside of any rectangle). I'm looking for a solution that works faster than bruteforce.

In 1D, it is achievable in N * log(M) using binary search. is something like that possible in 2D?

I care about practical performance. Two or more points can and often would be in the same rectangle, but the opposite never happens as rectangles are non-overlapping.

$\endgroup$
  • $\begingroup$ Do you have any requirements on the assignment, like that no two points can be in the same rectangle? Or can you assign each point independently to any rectangle it is contained in? Do you care more about practical performance or theoretical worst-case asymptotic running time? $\endgroup$ – D.W. Jun 4 at 0:07
  • $\begingroup$ Are your rectangles all axis-parallel, or can they be rotated? In the former case, orthogonal range searching is probably the best approach, but in the latter something like point location might be nessecary. In any case, you will likely need to construct some data structure on top of either the points or the rectangles. Is your data static, or is it dynamic? (i.e. do the points or rectangles change often in your application?) $\endgroup$ – Discrete lizard Jun 4 at 5:59
  • $\begingroup$ (Searching sounds appropriate for query problems. I read the question to describe a *set problem.) Is bruteforce checking every (point, rectangle) pair, or do you consider a line sweep using brute force for the representation of current rectangles and search therein bruteforce, too? $\endgroup$ – greybeard Jun 4 at 7:15
  • $\begingroup$ Replying to the comments: I care about practical performance. Two or more points can and often would be in the same rectangle. Rectangles are axis-parallel. Data is static. Line sweep would not be considered bruteforce, and it does sound interesting. $\endgroup$ – Maxim Imakaev Jun 4 at 11:41
  • $\begingroup$ Please edit the question to incorporate all relevant information in the post itself, so people don't have to read the comments to understand what you're asking, and so that the question reads well for someone who encounters it for the first time. $\endgroup$ – D.W. Jun 5 at 2:07
2
$\begingroup$

Most spatial indexes should be good, especially if your rectangles are axis aligned.

Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$. Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$.

For rectangles, the simplest index is probably a quadtree (but may not scale as well with larger $M$). R-Trees such as the R*Tree (R-Star-Tree) are harder to implement but probably better than plain quadtrees. You could also look into STR-Trees (sort-tile-recurse-loaded R-Trees), they take longer to build but have faster lookup.

In case you are using C++, have a look at libSpatialIndex or the Boost R-Tree. If you are using Java, have a look at my TinSpIn library. In the case of Java I can also strongly recommend the PH-Tree (disclaimer: self advertisement).

| cite | improve this answer | |
$\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.