[getsmart1]

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 as shown in different colors in the figure. 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!

[Salem_c]

http://cboard.cprogr...on-problem.html

[getsmart1]

Salem_c, on 18 September 2012 - 09:18 AM, said:

http://cboard.cprogr...on-problem.html

Sorry, I should have mentioned that I also posted the question in the devshed.com and cprogramming.com forums. Didn't mean to flood the forums, I just thought I would get different answers this way. Cheers

[JackOfAllTrades]

Moved to Software Development

[Skydiver]

You can form a bounding box for your region or volume, you can do a quick rough check for a point being outside. But once you have a candidate, you should go back to your quad or oct trees if you already have those structures prepared. My gut feel is that you maybe able to increase the probability of a hit by using k-d trees within that bounding box instead of straight quad or oct trees, but gut feel can only be proven out by having real performance numbers.

This post has been edited by Skydiver: 18 September 2012 - 03:52 PM

[getsmart1]

Hi. Forming a bounding box around the region won't work because most likely the region wont resemble a square. I've tried this and in practice I end up overestimating the candidates way too much. Then, the search would take almost as long as doing the detailed search from the begginning.