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

#1 getsmart1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.

Attached Image

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  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1575
  • View blog
  • Posts: 2,997
  • 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  Icon User is offline

  • New D.I.C Head

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

Re: Geometric search/intersection problem

Posted 18 September 2012 - 02:36 AM

View PostSalem_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  Icon User is online

  • Saucy!
  • member icon

Reputation: 5954
  • View blog
  • Posts: 23,220
  • 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  Icon User is online

  • Code herder
  • member icon

Reputation: 3168
  • View blog
  • Posts: 9,581
  • 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  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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