# Geometric search/intersection problem

Page 1 of 1

## 5 Replies - 1651 Views - Last Post: 19 September 2012 - 06:33 AM

### #1 getsmart1

• New D.I.C Head

Reputation: 0
• Posts: 3
• Joined: 17-September 12

# Geometric search/intersection problem

Posted 18 September 2012 - 01:27 AM

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!

Is This A Good Question/Topic? 0

## Replies To: Geometric search/intersection problem

### #2 Salem_c

• void main'ers are DOOMED

Reputation: 1924
• Posts: 3,774
• Joined: 30-May 10

## Re: Geometric search/intersection problem

Posted 18 September 2012 - 02:18 AM

http://cboard.cprogr...on-problem.html
Was This Post Helpful? 0

### #3 getsmart1

• New D.I.C Head

Reputation: 0
• Posts: 3
• Joined: 17-September 12

## Re: Geometric search/intersection problem

Posted 18 September 2012 - 02:36 AM

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

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
Was This Post Helpful? 0

### #4 JackOfAllTrades

• Saucy!

Reputation: 6207
• Posts: 23,951
• Joined: 23-August 08

## Re: Geometric search/intersection problem

Posted 18 September 2012 - 03:11 AM

Moved to Software Development
Was This Post Helpful? 0

### #5 Skydiver

• Code herder

Reputation: 4246
• Posts: 13,582
• Joined: 05-May 12

## Re: Geometric search/intersection problem

Posted 18 September 2012 - 03:51 PM

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

Was This Post Helpful? 0

### #6 getsmart1

• New D.I.C Head

Reputation: 0
• Posts: 3
• Joined: 17-September 12

## Re: Geometric search/intersection problem

Posted 19 September 2012 - 06:33 AM

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.
Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }