2
$\begingroup$

I have a set of axis aligned rectangles. When two rectangles overlap (partly or completely), they can be merged into their common bounding box. This process works recursively.

Detecting all overlaps and using union-find to form groups, which you merge in the end will not work, because the merging of two rectangles covers a larger area and can create new overlaps. (In the figure below, after the two overlapping rectangles have been merged, a new overlap appears.)

enter image description here

As in my case the number of rectangles is moderate (say $N<100$), a brute force solution is usable (try all pairs and if an overlap is found, merge and restart from the beginning). Anyway I would like to reduce the complexity, which is probably $O(N^3)$ in the worst case.

Any suggestion how to improve this ?

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Represent rectangle $R^i$ as $[x_m^i,x_M^i]\times[y_m^i,y_M^i]$, then $R^i$ and $R^j$ overlap iff their $x$-range and $y$-range overlap. From there, maintain a sorted list of the $x_{m/M}$ and $y_{m/M}$ values, and loop over your collection of rectangles.

When you process $R^i$, find every other rectangles that overlap its $x$ or $y$ range. If you find an actual overlap with rectangle $R^j$, merge it on the spot $R^i \gets \text{merge}(R^i,R^j)$ and update the sorted list with the new values of $x/y^i_{m/M}$. Continue until $R^i$ does not overlap any of the remaining rectangles. As $R^i$ grows through merges, $x^i_m$ can only decrease so in the worst case you have to compare it to other $x$ values $2N$ times. Likewise for the other bounds. "Processing $R^i$" is overall a linear procedure in $N$ and gives you a rectangle $R^i$ that does not overlap any of the remaining rectangles.

Repeat this "processing" on every rectangle that has not been "processed" yet. If at some point, an overlap with an "already-processed" $R^i$ is created, it should be detected and handled at the creation of that overlap, so in the end there are no overlap remaining. Overall we obtain an $O(N^2)$ complexity, which is hopefully better than "probably $O(N^3)$".

Off-topic.

  • I legitimately don't know what the actual complexity of your initial procedure is.
  • Do you know if the merge order matters for the end rectangles, and do you have a proof of it available?
$\endgroup$
0
$\begingroup$

I think a line sweep algorithm will perform well.

The state of the sweep is a set of disjoint rectangles, initially empty.

When you see a rectangle, merge it with the rectangles in the list.

If you need, you can keep the list ordered by $y_{\min}$.

$\endgroup$
5
  • $\begingroup$ The difficulty with a sweep line is that a merge can cause an already swept rectangle to become overlapped. $\endgroup$
    – user65203
    Commented Feb 6, 2018 at 11:30
  • $\begingroup$ @YvesDaoust, yes, I see that point, which you already made in the question. That's unavoidable. But a sweep line will tend to keep complexity down for most scenes. I haven't tested it, though. $\endgroup$
    – lhf
    Commented Feb 6, 2018 at 11:33
  • $\begingroup$ I fear that this phenomenon completely breaks the sweeping trick. Because you don't know when you can remove a rectangle from the list. $\endgroup$
    – user65203
    Commented Feb 6, 2018 at 11:36
  • $\begingroup$ @YvesDaoust, you remove a rectangle for the queue when it's first seen and merged into the list. Or perhaps we're talking about different problems. Anyway, it's just an idea. $\endgroup$
    – lhf
    Commented Feb 6, 2018 at 11:38
  • $\begingroup$ Yep, so unmerged rectangles stay forever. $\endgroup$
    – user65203
    Commented Feb 6, 2018 at 12:43

You must log in to answer this question.