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

One straightforward way to accelerate this query is by constructing the following uniform grid data structure (often called bins) as a preprocessing step: Put an n x n x n (in 3d) grid over your scene and for every cell of the grid store a pointer to all the cuboids intersecting that cell. Now, for a query point you can compute directly in which cell it is in the uniform grid, and then you have to check only the cuboids associated to that cell, and not all the cuboids.

Depending how big the space is and how varying the cuboid sizes are this method might not be very efficient because you it might be difficult to chose a good n resolution to accelerate enough and not need an enormous amount of cells. To overcome this you might want to try to look into more adaptive ways to partition the space, such as kd-trees (kd-trees at wikipedia), which are basically binary trees partitioning the space with axis aligned planes: See for an example here where the red plane divides the box into two parts and then the green in smaller parts, then the blue...

A query using kd-tree would first traverse down to the leaf of the kd-tree where the the query point is located and then check with the local cuboids in that cell. Other space partitioning data structure options can be found here.

Another option would be to use bounding volume hierarchies, which group objects together in bounding volumes, and then group bounding volumes into larger bounding volumes and so on... to get a hierarchy of bounding volumes. These adapt better to a scene and can easier handle scenes where the objects move, but I would think for your setting space partitioning could work well... Anyways, for more details see this book chapter.

Answer 2

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.