Xref: utzoo comp.misc:10226 comp.graphics:13517
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!tut.cis.ohio-state.edu!ucbvax!ucdavis!csusac!unify!jde
From: jde@Unify.Com (Jeff Evarts)
Newsgroups: comp.misc,comp.graphics
Subject: Problem/Challenge: Overlapping rectangles.
Message-ID: <r2s13w1@Unify.Com>
Date: 24 Sep 90 20:15:15 GMT
Distribution: usa
Organization: Unify Corporation, Sacramento, CA, USA
Lines: 41

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
================================================================================