Fast hiding of intersecting rectangles

Question

I'm working on an efficient algorithm to "hide" all the pairs of intersecting rectangles laid out in 2D in a set of N rectangles (axis aligned). All the rectangles have the same width and height.

Suppose my starting set of rectangles laid out in 2D is R={r_1,r_2,...,r_n} where r_i are all the rectangles, r_i has the boolean attribute visible.

I want to find the subset S of R such that for every r_i, r_j belonging to S r_i,_r_j don't intersect.

A first trivial solution is the brute force-maximal independent set approach. First I iterate over N(N-1)/2 rectangles (a given rectangle doesn't intersect with itself) and check if they intersects or not. Contemporaneously I also put all the rectangles in the set R as the nodes of a graph G=(V,E). Edges in that graphs are represented by the pairs of intersecting triangles.

The set of non intersecting rectangles is then one maximal independent set of the graph.

I think this is not the fastest approach, although correct. I've read in some discussion for example how sorting in advance the list of rectangles by their x coordinate would speed up the computation of intersecting rectangle pairs to O(nlog(n) ) (rather than brute force O(n^2).

Now I'm asking, do someone know a better algorithms for such problem (both for the computation of intersecting pairs in a set of rectangles and for the filtering of those rectangles?)

Reformulating the problem as SAT problem can also be interesting, although this idea just came up to my mind. The problem would be here to find that permutation of visible attributes such that no visible rectangle intersects another one.

score 3 · Accepted Answer · answered Mar 19 '12 at 15:01

3

Yes you should sort the rectangles by x.
Since your rectangles are on the same x axis and are the same height, after you sort them, you should be able to find the intersection in linear time. The algorithm you're looking for is called scan line.

You move a scan line over all your rectangles (jump from their x coords in the set you just sorted) and see which ones intersect at current x location. Load all the x coord overlapping rectangles into a datastructure and check if they intersect (based on y coord).

answered Mar 19 '12 at 15:01

Adrian

5,603
8
53
85

Well, I'll try that. The real problem is indeed how to find the permutation of rectangles such that given their pairwise intersection, there are no intersecting rectangles in the original set. Are there faster approaches than mine with maximal independent set? – linello Mar 19 '12 at 15:34
I'm not sure what you mean by permutations of rectangles. Are you creating rectangles by doing permutations on some seed values? I don't believe there are other ways to do rect intersection other than pairwise. Maybe you can use rectangle area/region of space it occupies (if you know how to mark it) and add that to a map. Then loop through all rects again and see if they "match" any area in that map (other than their own area). – Adrian Mar 19 '12 at 16:12
Pairwise is not necessary once the list is sorted. You can exploit this property to write a O(N log(N) ) collisions checking! It works well, I've implemented it in the spirit of scan line algorithm. This is the logic: i=0, S={}, N=|R| while (i – linello Mar 20 '12 at 08:31
@linello that's exactly how it should be done; but I see you are doing pairwise as well... unless I don't understand correctly what pairwise means. You are comparing the rectangles one by one to see if they intersect. Isn't this "the pair" or rectangles? – Adrian Mar 20 '12 at 14:34
yes, this is pairwise in fact, but in this way I can avoid a double nested for loop, by exploiting the fact that rectangles are sorted on their x coordinate. Pairwise comparison is difficult to avoid. – linello Mar 20 '12 at 15:01
Hi, I probably found that this problem is named MISR (maximal independent set of rectangles) and is quite known in literature. – linello May 21 '12 at 12:06

score 2 · Answer 2 · answered Mar 19 '12 at 15:41

2

There may not be only one subset S. For example, consider the following layout of rectangles:

     +-----+
     |     |
     |  A  |
+----|    +-----+
|    +----|     |
|  D  |   |  B  |
|     |--- +    |
+-----+    |----+
     |  C  |
     |     |
     +-----+

Both {A,C} and {B,D} are valid answers. So, the problem is somewhat ill-defined. Are you looking for the maximal cardinality subset?

answered Mar 19 '12 at 15:41

Kaganar

6,540
2
26
59

1

I know there are many solution. I take one of maximal independent subsets with a simple randomized algorithm, because finding the maximum independent subset is too computationally heavy for this task and I don't need it. – linello Mar 19 '12 at 15:54
@Adrian: in this case the valid permutation of rectangles to be all "non-intersecting" are or {A,C} or {B,D} – linello Mar 20 '12 at 08:36

score 1 · Answer 3 · answered Apr 26 '12 at 16:40

Testing all pairwise combinations is a good idea, but being O(n^2) it helps to find ways to speed it up.

Partition the space into a coarse grid, like a checkerboard, with each cell having a list of rectangles it owns. This means the center point of a rectangle is in the cell. This assigning of rectangles to cells is O(n).

The cells must be comfortably larger than the size of a rectangle, perhaps twice that, and the whole space needs to be divided into "several" rows and columns - say a dozen, hundreds, however many makes sense for the number of rectangles and the size of the area they inhabit. At least five rows and five columns, though, or else you won't gain much efficiency.

Then test all pairwise combinations within each cell. This will eliminate a bunch of overlapping pairs. For each cell, you must also test all pairwise combinations involving the eight neighboring cells - the ones sharing a side or corner - since a rectangle can overlap up to four cells. Be careful not to double count pairs, of course.

Execution time is saved because you'll never test any pairs where one rectangle is way over here and the other is over in yon faraway area.

This technique is general and could apply to any shapes, and resembles techniques used by physicists in simulating huge systems of particles such as stars in galaxies.

Fast hiding of intersecting rectangles

3 Answers3

Linked