Xref: utzoo comp.misc:10281 comp.graphics:13687
Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!uwm.edu!wuarchive!usc!julius.cs.uiuc.edu!apple!voder!pyramid!prls!philabs!nbc1!nbc1!colin
From: colin@nbc1.nbc1.ge.com (Colin Rafferty)
Newsgroups: comp.misc,comp.graphics
Subject: Re: Problem/Challenge: Overlapping rectangles.
Message-ID: <COLIN.90Sep27121315@nbc1.nbc1.ge.com>
Date: 27 Sep 90 16:13:15 GMT
References: <r2s13w1@Unify.Com>
Sender: colin@nbc1.ge.com (Colin Rafferty)
Distribution: usa
Organization: National Broadcasting Company, New York City
Lines: 62
In-Reply-To: jde@Unify.Com's message of 24 Sep 90 20:15:15 GMT

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