1 Attachment(s)

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. Please feel free to move it to the appropriate forum if needed (I have also asked the same question in dreamincode.net and devshed.com)

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!Attachment 11980