Detect overlapping of rectangular prisms

Question

Given a 3D coordinate system and rectangular prisms with a non-negative starting point and a non-negative size (e.g. starts at (0, 2, 5) and has a size of (9, 20, 5)): how can I best check if another rectangular prism intersects with one of the prisms already in the coordinate system? Eventually, the goal would be to perform this check for all prisms present, being able to test one should be sufficient to complete this task.

Info: starting points and sizes are 3-tuples of non-negative longs. I am looking for an elegant solution that is moderately fast.

My project is in java, but any math formula, pseudo code or description is more than enough.

Answer 1

Nice algorithmic approach for large data sets

Store your prisms in an R-Tree. For rectangular co-axial prisms, the search and insertion should be in the order of log(n).

There are some Python packages for R-Trees. Using Rtree 0.6.0, your code would be as simple as:

>>> from rtree import Rtree
>>> idx = Rtree()
>>> minx, miny, maxx, maxy = (0.0, 0.0, 1.0, 1.0)
>>> idx.add(0, (minx, miny, maxx, maxy))
>>> list(idx.intersection((1.0, 1.0, 2.0, 2.0)))
[0L]
>>> list(idx.intersection((1.0000001, 1.0000001, 2.0, 2.0)))
[]

Practical yet fast approach

Store your data in a sqlite database, which can be created in a file or in memory using very few lines of code (there are many java implementations). Create table called, say, prisms, whose columns would be id, min_x, min_y, min_z, max_x, max_y, max_z. Index each row.

Insertion is O(1), and checking for intersection follows Magnus Skog's approach, Given new_min_x, new_min_y, new_min_z, new_max_x, new_max_y, new_max_z:

SELECT COUNT(*) FROM prisms
   WHERE (new_min_x BETWEEN min_x and max_x OR new_max_x BETWEEN min_x and max_x)
   AND   (new_min_y BETWEEN min_y and max_y OR new_max_y BETWEEN min_y and max_y)
   AND   (new_min_z BETWEEN min_z and max_z OR new_max_z BETWEEN min_z and max_z)

Answer 2

Lets say you have two prisms A and B. If B intersects A it's the negation of not being completely to the right, left, up, down etc.

if not (B.x > A.x+A.dx or B.x+B.dx < A.x or
        B.y > A.y+A.dy or B.y+B.dy < A.y or
        B.z > A.z+A.dz or B.z+B.dz < A.z)
        // B intersects A

Answer 3

The prism that starts at (0, 2, 5) and has a size of (9, 20, 5) is ending at (9, 22, 10).

To check for overlapping prisms (A and B), use the start and end points of these. The two prisms have to overlap in all dimensions.

To check overlapping in X dimension, use this:

If (A.startX <= B.endX) and (B.startX <= A.endX) 

Therefore:

If 
      (A.startX <= B.endX) and (B.startX <= A.endX) 
  and (A.startY <= B.endY) and (B.startY <= A.endY) 
  and (A.startZ <= B.endZ) and (B.startZ <= A.endZ) 
Then
    (A and B overlap)

The above check will result True when the two prisms have even only one point in common. If you don't want that and you want the overlapping space to be more than just a point or a line segment or a rectangular surface, but a prism, then replace <= with < .