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: 182
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