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