Geometric search/intersection problem

Hello guys.

I decided to post this in the C forum since its what I use, but its really a general problem.

I need to find if a any given point in space (2d/3d) is inside an irregular region formed by rectangles (or cubes in 3d).

I have several different boxes with its coordinates. All of the boxes overlap with at least another box, meaning its a closed region with no holes. I want to form one big region from all these boxes and then try to find if points lie inside or outside.

I have already developed an implementation that uses search trees (quadtrees) and is efficient in looking through each of the boxes to see if the points are there. Now, some of the problems I want to solve have millions of boxes and millions of points, so I'm looking for ways of say having one big region. In 2d this could be a polygon for example which is not hard to do, but not for 3d.

Basically what I would like in the end is to form a big region where I can quickly get candidate points, which I can then process in detail with my search trees algorithms.

I've been developing the search tree algorithms for the last few days so my head is pretty biased towards that at the moment and I need some external thinking.

Any ideas?
Thanks a lot in advance!

Cross-posted here and here

Sorry. Yes, I forgot to mention I also posted the question in the dreamincode.net and cprogramming.com forums. Didn't mean to flood the forums, I just thought I would get different answers this way. Thanks for pointing it out.

Don has written about three fifths of The Art of Computer Programming by Knuth. If he's addressed geometrical algorithms this would be quite a good reference. The programs would be written in MIX or in MMIX which could be a bit challenging at first to follow---just because these are low level languages.

Robert Sedgwick's books are more accessible.

Are your boxes convex? It's easier if they are.

Maybe you could sort the nodes in each dimension (storing all n, after all, memories are large and cheap these days) and use successive binary searches. 3D FFT time goes to heck on the third dimension because the cache hit rate sinks to nil.

With an ordered convex polygon,
I expect you know that
for plane vectors

Where signum returns the sign of, and cross represents an inorder cross product
P is in triangle ABC if
signum((B-C)cross(P-C))==signum((A-B)cross(P-B))==signum((C-A)cross(P-A))
otherwise you wouldn't attempt this algorithm.
Which I'm sure can be written as the determinant of some matrix.

In 3D, I'd check signs of dot products of face normals against the vector from center of face to P. Since the face could be warped, this would only work for volumes composed of planar surfaces. Triangles. So it would work for all tetrahedra (the case that interests me most often) and a constrained set of other volumes.

Check with Sedgwick.

I believe the standard reference for this type of problem is "the Dutch book," i.e., Computational Geometry: Algorithms and Applications by de Berg, Cheong, van Kreveld, and Overmars. (I just searched Google to get the exact title and authors, forgetting that the actual book was on the table in front of me!)

Anyway, it doesn't seem that the OP's problem is reducible to a single convex polyhedron. However, the Dutch book does state that while the problem of efficient point location in a general subdivision in high-dimensional space is open, efficient solutions exist for rectangular subdivisions, which they don't define but I'm guessing are similar or identical to what the OP is trying to do. The references they give are:

• "Two- and three-dimensional point location in rectangular subdivisions," by de Berg, van Kreveld and Snoeyink (J. Algorithms, 1995)
• "Rectangular point location in d dimensions with applications," by Edelsbrunner, Haring, and Hilbert (Comput. J., 1986)