[comp.misc] Problem/Challenge: Overlapping rectangles.

jde@Unify.Com (Jeff Evarts) (09/25/90)

Hello!

	I have a (hopefully) interesting problem that I figure _someone_ must
have a good algorithm for.

	* I have a set of N rectangles specified by opposite corners.
		(upper left, lower right)

	* Some number of them will overlap corners, butt or overlap
	  on edges, etc.

What I want to do is this:

	For each set of rectangles that overlap, I want to create a larger
	rectangle that includes all of them, thus giving a new set of
	rectangles that do not overlap that "contain" all the rectangles
	in the original set.

	Rectangles that share an edge (but no common ground) should be
	included only if the edges butt perfectly.

	Example: Rectangles (X,Z,Y,A,B,C,D) => Rectangles (1,2,3,4)

	+--------------------------+       +--------------------------+
	|                    AAAA  |       |                    2222  |
	|  XXXXXXXXX         AAAA  |       |  111111111111111   2222  |
	|  XXXXXXZZZZZZZZ    BBBB  |  ==>  |  111111111111111   2222  |
	|  XXXXXXZZZZZZYYY         |       |  111111111111111         |
	|  XXXXXXXXX   YYY  CCCDD  |       |  111111111111111  33344  |
	|                   CCC    |       |                   333    |
	+--------------------------+       +--------------------------+

Does anyone have an algorithm to do this? I have one that is real brute-force,
but if anyone has ever tackled anything like this before, I`d appreciate it
if they would respond. (Brute-force also welcome, for comparison to my own)

Thanks in advance, netland.
================================================================================
-Jeff Evarts                                                 Fax: (916) 920-5306
--jde@unify.COM                                             Phone:(916) 922-1177
================================================================================

colin@nbc1.nbc1.ge.com (Colin Rafferty) (09/27/90)

In article <r2s13w1@Unify.Com> jde@Unify.Com (Jeff Evarts) writes:
>   For each set of rectangles that overlap, I want to create a larger
>   rectangle that includes all of them, thus giving a new set of
>   rectangles that do not overlap that "contain" all the rectangles
>   in the original set.
>
>   Example: Rectangles (X,Z,Y,A,B,C,D) => Rectangles (1,2,3,4)
>
>   +--------------------------+       +--------------------------+
>   |                    AAAA  |       |                    2222  |
>   |  XXXXXXXXX         AAAA  |       |  111111111111111   2222  |
>   |  XXXXXXZZZZZZZZ    BBBB  |  ==>  |  111111111111111   2222  |
>   |  XXXXXXZZZZZZYYY         |       |  111111111111111         |
>   |  XXXXXXXXX   YYY  CCCDD  |       |  111111111111111  33344  |
>   |                   CCC    |       |                   333    |
>   +--------------------------+       +--------------------------+
>

The problem with your problem statement is that it doesn't deal with
this case:

    +------------------------+        +------------------------+
    |              YYYYYYYY  |        |              22222222  |
    |              YYYYYYYY  |        |              22222222  |
    |  XXXXXXXXX   YYYYYYYY  |        |  11111111111122222222  |
    |  XXXXXXXXX   YYYYYYYY  |  ==>   |  11111111111122222222  |
    |  XXXXXXXXX             |        |  11111111111111        |
    |  XXXXXZZZZZZZZZ        |        |  11111111111111        |
    |       ZZZZZZZZZ        |        |  11111111111111        |
    |       ZZZZZZZZZ        |        |  11111111111111        |
    +------------------------+        +------------------------+

Here you don't have Y overlapping with X or Z, but you can't create a
box around X and Z without overlapping it with Y.

What this means is that you need to either recognize this condition,
or do the reboxing iteratively until there are no more overlaps.

The best solution, given that you have to figure out the overalpping
yourself would probably be a variation on getting the convex hull of a
set of points.

Of course, if you've already figured out the overlapping rectangles,
then getting the new ones is a snap.  Since a rectangle is defined as
{ (x0, y0), (xf, yf) } for the upper left and lower right points, then
given the set of rectangles, the enclosing one is just:
        { (MIN(x0), MIN(y0)), (MAX(xf), MAX(yf)) }
over all rectangles.

But I think you need to deal with the problem I pointed out first.
--

  //=====================================\/==============================\\
  ||       Colin Owen Rafferty           ||  "Life is so complex, parts  ||
  ||        colin@nbc1.ge.com            ||   of it must be imaginary."  ||
  || {philabs,crdgw1,ge-dab}!nbc1!colin  ||               -Tim Thiel     ||
  \\=====================================/\==============================//
-- 

  //=====================================\/==============================\\
  ||       Colin Owen Rafferty           ||  "Life is so complex, parts  ||
  ||        colin@nbc1.ge.com            ||   of it must be imaginary."  ||