5

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.

Samuel
  • 18,286
  • 18
  • 52
  • 88

4 Answers4

5

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).

R-Tree (wikipedia)

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)
Community
  • 1
  • 1
Adam Matan
  • 128,757
  • 147
  • 397
  • 562
  • +1 Samuel is using java though, but shouldn't be a problem to find an implementation of this in the java world. – rtn May 15 '11 at 13:05
  • +1 But in my case i cannot use external libraries, the quantities of prisms is very limited and performance wise this piece can live with a slower algorithm. So in my case i think i am gonna go with an easier implementation, keeping in mind though that this implementation will outperform it in large data sets, and it's a cool new thing to have learned about! – Samuel May 15 '11 at 13:24
  • @Samuel: To use or not R-trees is up to you and how big your data set is (and how fast or if it changes, too). – ypercubeᵀᴹ May 15 '11 at 13:35
  • Also note that R-trees are used in spatial databases, so that is an option too (store objects in a spatial db and let the db answer your queries). – ypercubeᵀᴹ May 15 '11 at 13:35
  • 3
    @ypercube True, but I thought something like PostgreSQL+PostGIS would be a very long shot for this question. – Adam Matan May 15 '11 at 13:48
  • @Adam: Either @Magnus or my condition is simpler than your (last 3 lines) complex condition with `OR`s and `BETWEEN`s. – ypercubeᵀᴹ May 15 '11 at 13:48
  • @ypercube: I think Magnus Skog's formula is incorrect: consider A=[(0,0,0), (1,1,1)], B=[(1.5, 10, 10), (2.5, 20, 20)]. These prisms do not intersect – Adam Matan May 15 '11 at 15:00
  • Even if Magnus Skog's approach was what i needed right now, I want to thank you for your large and interesting contribution – Samuel May 15 '11 at 16:42
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
rtn
  • 127,556
  • 20
  • 111
  • 121
  • Checking for each existing prism might not be efficient with large data sets. – Adam Matan May 15 '11 at 12:40
  • @Adam: I hear you :) It's a trade off of course. The complexity of your algorithms increase with increased demands of efficiency. – rtn May 15 '11 at 13:04
  • I explained my decision in my comment to adam, i am just wondering from a stackoverflow point of view should i take this as an answer because i will use it, or do i take adam's answer as an answer for future users who look at this question? – Samuel May 15 '11 at 13:26
  • @Magnus Skog didn't mean to nitpick, the tradeoff is correct. – Adam Matan May 15 '11 at 13:31
  • @Adam: I didn't take it as nitpicking. Np :) – rtn May 15 '11 at 13:33
  • 1
    @Samuel: Personally I'd pick the answer that I'd use since it would solve my specific problem. If alternate answers are just as correct or provide more information they will most likely have many upvotes and that information is still here for other readers to use as they please :) – rtn May 15 '11 at 13:39
1

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 < .

ypercubeᵀᴹ
  • 113,259
  • 19
  • 174
  • 235
0

The same way you'd do to check segments on a line. If the start or end of B is between the start and end of A, they overlap.

The only difference is that they have to overlap in all three dimensions.

SJuan76
  • 24,532
  • 6
  • 47
  • 87
  • *`If the start or end of B is between the start and end of A, they overlap`* : This is correct but the other direction is not true! If they overlap then the start or end of B does not have to be between the start and end of A. – ypercubeᵀᴹ May 15 '11 at 12:04