Search code examples
data-structuresbinary-treepointregionquadtree

What is a good data structure for finding which region contains a point?

I'm looking for a data structure that supports finding which of "n" regions contains a point "p". I was looking at Quadtree's and R-trees however I don't think they fit exactly what I'm looking for.

In essence I want to be able to add some number of 3 dimensional rectangular regions to this tree, and then be able to test a 3 dimensional point against this tree and return which region most tightly constrains the point. No regions will have overlapping borders.

The naive algorithm I'm currently using is to simply test the point "p" against each dimension of each rectangular region. 

for(region in regionList):
    if(p.x > region.x1 && p.x < region.x2 && p.y > region.y1 && py < region.y2 && p.z > region.z1 && p.z < region.z2)
        return region
end

This runs in O(n) time where n is the number of regions. I'd like the search to take O(log n) as a point Quadtree does for finding 2d points.

Solution

  • I'd suggest a QuadTree which stores regions like a MX-CIF tree. It's essentially a QuadTree based on 2 dimensions (x,y). Once you find an appropriate Node which contains the point in terms of (x,y), you can check to see if it contains the point in all three (x,y,z) dimensions.

    I've done something similar in Java.

    You can also look into Octree which is a 3-dimensional QuadTree.