Merging and splitting overlapping rectangles to produce non-overlapping ones

Posted by uj on Stack Overflow See other posts from Stack Overflow or by uj
Published on 2010-05-02T23:36:47Z Indexed on 2010/05/02 23:58 UTC
Read the original article Hit count: 155

Filed under:

algorithms

|

rectangles

|

computer-graphics

|

mathematical-optimization

|

computational-geometry

I am looking for an algorithm as follows:

Given a set of possibly overlapping rectangles (All of which are "not rotated", can be uniformly represented as (left,top,right,bottom) tuplets, etc...), it returns a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

It seems simple enough at first glance, but prooves to be tricky (at least to be done efficiently).

Are there some known methods for this/ideas/pointers?

Methods for not necessarily minimal, but heuristicly small, sets, are interesting as well, so are methods that produce any valid output set at all.

© Stack Overflow or respective owner

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More

Related posts about rectangles

Move 3 rectangles up in their X but keep order of rectangles

as seen on Stack Overflow - Search for 'Stack Overflow'
I have 3 rectangles being rendered here. Let's say i wanted to move them all above the line yet keep their order, how would i go about that? I tried subtracting the Y and height rather than adding the Y it but as expected, the lower rectangle goes at the top, middle stays in the middle and top goes… >>> More
Triangle - Rectangle Intersection in 2D

as seen on Game Development - Search for 'Game Development'
I had previously asked this for 3D but now I changed my strategy and would like to do the intersection in 2D. The Rectangle is axis aligned and will always be in a fixed position, and has a constant shape and size, basically I want to clip the red areas of the triangles that extend outside the bounds… >>> More
Ray-plane intersection to find the Z of the intersecting point

as seen on Game Development - Search for 'Game Development'
I have a rectangle in 3d space (p1, p2, p3, p4) and when the mouse rolls over it I need to calculate the exact Z of the point on the rect, given the mouse coordinates (x, y). Would a Ray-plane intersection find the Z of the intersecting point? Edit: Would this one-liner work? .. it returns the… >>> More
Algorithm to reduce a bitmap mask to a list of rectangles?

as seen on Game Development - Search for 'Game Development'
Before I go spend an afternoon writing this myself, I thought I'd ask if there was an implementation already available --even just as a reference. The first image is an example of a bitmap mask that I would like to turn into a list of rectangles. A bad algorithm would return every set pixel as a 1x1… >>> More
Algorithms for positioning rectangles evenly spaced with unknown connecting lines

as seen on Game Development - Search for 'Game Development'
I'm new to game development, but I'm trying to figure out a good algorithm for positioning rectangles (of any width and height) in a given surface area, and connecting them with any variation of lines. Two rectangles will never have more than one line connecting them. Where would I begin working… >>> More