Objects inside a volume

Question

I have a problem, that I need a very efficient way of finding objects inside a given volume. One can imagine, that the objects are represented as boxes with a X-min, Y-min, Z-min and X-max, Y-max, Z-max values. There can be millions of such objects in space, and the problem is to find the objects inside an arbitrarily given user supplied volume. The user inputs min,max of the X,Y and Z values of the box.

Currently, I have all those objects in an Oracle Database table which are range indexed for X, Y, and Z values. Any query, to find the objects then involves comparison of the given X,Y, & Z values with that of the objects values. I find the performance is not satisfactory, and thinking of an in-memory algorithm to solve this. Also, required is to find the objects that are fully-in, partially-in.

Thanks Ey

Answer 1

There's a relatively rapid way of finding whether your axis-aligned bounding boxes fall within, partially within, or without the specified bounding volume. Basically, you can assign a bitmask for values of bound comparison, and determine the intersection of the bounding boxes by ANDing the bitmasks. It's precisely what you want, and it's a very efficient method; I remember seeing it many years ago (seriously, like 15 years ago); I'll post the reference and more data about the method when I find it.

Update: Okay, I think the original method I remembered wasn't for this precise situation, but this has a relatively quick solution. Taking the single-dimensional case (from which you can generalize the other dimensions), you want the object to be disqualified if both the points of the box in that dimension are less than the box min or if they're both greater than the box max. Repeat for each of the dimensions, and that'll give you what you want.

Answer 2

Not a very elegant solutions, but I hope it is efficient.
It has an initialization part that will take some time, but then it should pay off, the queries will hopefully be fast.
First create a space partitioning data structure, with which you can search for points in a queried container, you'll be able to find the boxes this way.
It will be a tree with 8 children per node. There are other alternatives, take a look at k-d trees

Find the smallest enclosing container that contains all the boxes.
Divide this container in 8 equally sized containers.
For each point in your set find the container that it belongs to.
Repeat this process for each container that has more than one point in it.
You'll end up with the leaf containers having a single point.

Using this structure say you want to find all the points in a queried container.
Start from top of the tree and traverse all branches/containers that intersect with the queried container.
There will be 3 cases:
1) a container is completely enclosed within the queried container => all the points in this sub-tree are in the queried container.
2) a container is outside the queried container => you don't traverse it. (this is where you should get the efficiency)
3) a container is intersecting the queried container => you'll have to repeat the process for all it's children.
There are some edge cases you'll have to figure out.

To find the boxes you'll have to put each of their 8 corners in that data structure.
The corners should link back to the boxes. So when you find a corner you'll know which box it belongs to.

To find which boxes are completely enclosed in the queried container you have to test each one of the found boxes