How do I determine which cuboids a point is in without iterating over them all?

Question

I have a number of cuboids whose positions and sizes are given with minimum and maximum x, y and z co-ordinates (so they are parallel to the main axes).

e.g. I might have the following 3 cuboids:

10.5 <= x <= 39.4,  90.73 <= y <= 110.2, 90.23 <= z <= 95.87
20.1 <= x <= 30.05,  9.4  <= y <=  37.6,  0.1  <= z <= 91.2
10.2 <= x <= 10.3,   0.1  <= y <=  99.8, 23.7  <= z <= 24.9

If I then give a point (e.g. (25.3,10.2,90.65)), is there a way to quickly determine which cuboid(s) I'm in?

• Obviously I could just iterate over all the cuboids, but there are potentially millions of them, and I need this to go faster than simple iteration (something O(log n) or better would be great).

• This sounds to me like a "fuzzy matching" type problem, and I notice that Apache Lucene supports range queries, but this seems to work the opposite way round (finding a point in a cuboid rather than a cuboid containing a point).

• To slightly complicate matters further, the number of dimensions might be larger than 3 (it could be up 20); i.e. I might be looking for "hypercuboids" rather than cuboids.)

Answer 1

you verging into the territory of "Binary Space Partitioning" and "Collision Detection"; essentially the ideas are basically storing the cuboids into a tree type structure, which divides the space they occupy into neat little boxes. The decision about which "part of space" each cuboid occupies is made during the insertion into the tree strucutre.

Do a google search on Octrees.

Efficently dividing 3D space, and the objects contained within that space is quite a big portion of computer science; mostly used in the development of computer games. Some of the algorithms take into consideration a time factor, i.e. that the objects move between partition spaces.