Algorithm to search and sort cubic area

Question

I'm trying to figure out an algorithm that would sort cubic area (ex the area defined by (0, 0, 0) to (1, 1, 1) and would be as fast as possible to return the area when given coordinates.

ex: data structure contains area: (0, 0, 0) to (100, 100, 100), (1000, 1000, 1000) to (1010, 1010, 1010) and (-50, -50, -50) to (60, -60, 60)

thus searching for 10, 10, 10 would return area 1, (1001, 1001, 1001) would return area 2 etc

Sort, add, remove time can be long. I need a fast search time we can assume its only integers that will be searched and the solution of making a 3d grid and filling every cell contained within the area with a reference to the area is NOT an acceptable solution, i don't have 3TB of ram to dedicate to this :P. We can also assume that areas will NOT be overlapping, if that helps anyone

If anybody has an idea I'd be glad to hear it

Thanks guys

-Olivier-

Edit: using a structure that holds minX, minY, minZ, maxX, maxY, maxZ to represent an area and place all those area in a list where you search one by one (by checking if the coordinates is bigger then minX but smaller then maxX, and same for every coordinates ) is still too slow O(N)

at the moment I'm exploring the idea to sort then using a n-ary tree, sort by x, then by y, then by z but i do not know if it will be a good one

Answer 1

This is a simple bounding box problem.

Linear search:

Each of your regions is defined by a minimum corner (x_min, y_min, z_min) and a maximum corner (x_max, y_max, z_max). If you are searching for a particular target point (target_x, target_y, target_z), you can just loop through all the regions. If you find a region where:

x_min <= target_x <= x_max
y_min <= target_y <= y_max
z_min <= target_z <= z_max

then the region that you're searching for is the one defined by {(x_min, y_min, z_min), (x_max, y_max, z_max)}.

If N is your number of bounding regions, this algorithm will run in O(N). If you collect a list of regions that match your target, you can also handle overlapping regions as well.

Octree spatial subdivision:

If you have a very large number of regions, you can create a pre-computed hierarchy also known as an octree:

An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree, but note that it is normally written "octree" with only one "t". Octrees are often used in 3D graphics and 3D game engines.

So, at every level of this hierarchy, you subdivide the space into eight sub-cubes.

If one of those sub-cubes does not have any search regions inside it, it becomes an empty leaf node (i.e., you can say "nope, nothing in here, move along").

If a sub-cube has a sufficiently small number of search regions within it (i.e., some number M where M << N) you can apply the above linear search algorithm to that target number.

If a sub-cube still has a relatively large number of search regions within it, continue the subdivision process on that sub-cube.

If you're willing to spend the time to compute the octree, this will produce a search algorithm that has performance on the order of O(logN) + O(M).

Answer 2

You don't want to "sort" the cubic area, you want a spatial indexing structure such as a k-d tree, octree, or otherwise. K-d trees are an especially good choice because you're already talking about shapes (sub-cuboids) with axis-aligned surfaces which do not overlap. It may be worth looking up methods for broad phases in computer games as they often use data structures for which detecting arbitrary intersections of aligned boxes with existing aligned boxes is very fast. (e.g. The Bullet physics engine.)

Most of the spatial indexing techniques mentioned above are O(log n) for performing point queries. There's many implementations of K-d trees already in existence.

Answer 3

I would start by implementing a simple Box collision method. Then you'd just run this against each of your areas.

My question would be what if the search spans multiple areas

Answer 4

You should choose from one of algorithms, listed here. If your data allows it, you may try integer sorting algorithms, which have lower theoretical iteration count, then comparison-based ones.