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

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

Quote:

---

Originally Posted by Salem

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.

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.

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.

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.

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.

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.

Quote:

---

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".

Salem:

Quote:

---

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:

Quote:

---

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.