Hi,
Sounds like a fun problem. If I understand it correctly, you have a list of (in some cases overlapping) rectangles, and from that you want to generate a new list of rectangles that together cover the same area as the rectangles of the original list, but where none of them overlap. Is that correct?
After some paper sketching
here are my initial thoughts about it in pseudo code:
// Pop the largest rectangle from original list
while rect = olist.pop()
// Get rectangles overlapping 'rect' in new list
overlapping = nlist.overlapping(rect)
// For each overlapping rectangle
for each overlap in overlapping
// If 'rect' takes priority over 'overlap'
if rect.stronger(overlap)
segments = overlap.divide(rect) // Divide 'overlap' into segments
nlist.replace(overlap, segments.pop()) // Replace 'overlap' with largest segment
olist.join(segments) // Put remaining segments in original list
else
segments = rect.divide(overlap) // Divide 'rect' into segments
rect = segments.pop() // Set 'rect' to be the largest segment
olist.join(segments) // Put remaining segments in original list
end if
end for each
// If rect hasn't gone away
if rect.size > 0
// Put it in new list
nlist.push(rect)
end if
end while
