Thread: Geometric search/intersection problem

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    4

    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!Geometric search/intersection problem-polygon1-png
    Last edited by getsmart1; 09-18-2012 at 03:42 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    As a matter of good form, it's important that you tell people where you've also cross-posted.
    Geometric Search/intersection Problem - C And C++ | Dream.In.Code

    Otherwise, people are potentially going to go over the same ground over and over.

    See also
    How To Ask Questions The Smart Way
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Sep 2012
    Posts
    4
    Quote Originally Posted by Salem View Post
    As a matter of good form, it's important that you tell people where you've also cross-posted.
    Geometric Search/intersection Problem - C And C++ | Dream.In.Code

    Otherwise, people are potentially going to go over the same ground over and over.

    See also
    How To Ask Questions The Smart Way
    Sorry, you're right. I've posted the same question in dreamincode.net and devshed.com. I'll edit the posts to address this.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Some questions.

    1. How large is the "world" compared to the shape?
    If your shape covers say 10x10 in a world which extends to 1000x1000, then a random distribution of points would most likely be outside the shape.

    2. What is the distribution of points? Are they biased to be expected to be inside the shape to begin with (more than say random distribution in the world say).

    3. How static is the shape? Is it fixed for a large number of points?
    Is it worth the cost of pre-calculating the perimeter?

    Whilst the "point inside a polygon" test is simple enough, the fact that your polygon now has several million vertices might be.

    4. The test for a point inside a rectangle is just 4 comparisons. Even if you have a million such rectangles, if they're stored in a BSP tree, you should be able to efficiently remove large numbers very quickly.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Sep 2012
    Posts
    4
    Thanks for the answer,

    1. The "world" and the shape are of similar size. Lets say shape ~2x2 and world ~10x10 (depending on the problem)

    2. The points are not exactly random. They come from different grids (think finite element grids) but they are not biased to be expected inside or outside the shape to begin with. For the purpose of this, we could assume they are distributed randomly.

    3. The shape is fixed. It could be worth pre-calculating a perimeter. That could possibly lead to a big overestimation of the points lying inside the perimeter though.

    4. Yes. I have already implemented a search based on quadtrees (similar to a BSP tree) and its very efficient in going through the different boxes (obviously discarding large groups of boxes while running). But if possible I want something even faster. Let me explain why.

    The final purpose of the code is to form a list of the points that lie inside each of the boxes. The code runs in serial mode using this tree search and is very efficient in finding points and forming the lists. I'm happy with that.
    Now, I need to parallelize the code. As a first attempt, each processor is assigned a number of boxes and points and performs the local tree search. After that, each processor communicates with other processors, and performs searches on remote points.

    This works, but is obviously not parallel efficient in terms of speed since each processor will still search through the entire "world". What I was thinking is ways of generating a big region to cover every single box in processor 1 for example. Proc1 will then check if points in Proc2 lie inside the big region and vice-versa. This way when performing the final remote "detailed" search using the search trees, I have already discarded most of the points. In the end each processor would search through its local points, plus only some of the points of the other processors.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    How about BSP partitioning the world and the points?

    Lets say for 2 cores:
    All points with +y and all rectangles with a +y edge go through core 1
    All points with -y and all rectangles with a -y edge go through core 2

    So each core has only half the world, and half the points to deal with.

    This readily extends to 4 cores by doing +/- x as well.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I'll preface this by saying that I did most of my drinking at home, not at the University..

    Two idea's for you:

    1) Knuth's Dancing Links, is a coloring problem solver, that has general problem solving applications -- and the larger the problem, the more it excels given a few tweaks.

    I don't know a lot about it, except that it can be used to solve Sudoku, and with it's tricky use of double linked lists, it is very fast. Wikipedia and Google have some interesting write up's on it. Sudoku programming forum has the programmers who know it far better than I do (quite bright).

    http://www.setbb.com/sudoku/index.php?mforum=sudoku

    2) I like to take problems like this, and solve them by hand a few times. Get the pattern I would use, worked out. Then use that pattern as the basis for the program.

    Just peeking at your boxes here, I'm thinking of an array of x and y values (or x,y&z values), as structs. These could the sorted through an index, (so the points don't move), for values, and if the 4 sided figures are "set straight" (their sides are either vertical or horizontal), then it's easy to see where the overlapped portions extend beyond the original box. Any value greater than the current x or y or z value, is an extension, and becomes the new current "side" value in that direction.

    Of course, there are surely optimized algorithms for this. Are you using one of them, already?

    Interesting problem.
    Last edited by Adak; 09-18-2012 at 09:36 AM.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In the values for x, y, etc., there's no need to go through the list of points values. If the boxes are "set straight", then the greatest x in the list, is the x, the greatest y is the y, etc., so a detection of the max value for x, and another for y, is all that you need.

  9. #9
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    All of the boxes overlap with at least another box, meaning its a closed region with no holes.
    How do you know there's no holes? What about 4 elongated rectangles each touching two others at the ends, with a big hole in the middle?

    Obviously you must have thought of creating one big rectangle for the initial comparison (lowest x, highest x, lowest y, highest y). Although the way you've described it, it sounds like this rectangle will cover most of the space. I guess this is what you mean by "precalculating a perimeter" and it "leading to a big overestimation of the points lying inside".
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  10. #10
    Registered User
    Join Date
    Sep 2012
    Posts
    4
    Salem:
    How about BSP partitioning the world and the points?
    I could use this type of partitioning, but the solution needs to be general for any kind of partitioning. Actually, the code needs to be able to accept previous partitions that won't adhere to the +y/-y idea.

    Adak:

    Even though each of the boxes can be "set straight", the union won't be. I'm not sure I understand your suggestion very well, but a simple min, max XY will overestimate the points.

    oogabooga:

    How do you know there's no holes? What about 4 elongated rectangles each touching two others at the ends, with a big hole in the middle?
    Because of the nature of the problem, there cant be any holes. The boxes are generated from FiniteElement meshes. Yes, that is what I meant by an overestimation.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 09-29-2011, 04:23 AM
  2. Arithmetic/Geometric/Harmonic
    By DJ_Steve in forum C Programming
    Replies: 12
    Last Post: 08-23-2009, 08:34 PM
  3. (C#) Ray->Box intersection
    By Devils Child in forum Game Programming
    Replies: 6
    Last Post: 12-18-2008, 01:02 AM
  4. Program for average, geometric mean, harmonic mean
    By Northstar in forum C Programming
    Replies: 5
    Last Post: 11-07-2007, 11:33 AM
  5. Geometric Libraries and Coordinate planes
    By Unregistered in forum Windows Programming
    Replies: 4
    Last Post: 11-11-2001, 02:46 PM