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.
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).
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?
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.
