0

Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping

Nice explanation, Gareth. What I am trying to figure out is how to achieve the reverse of the solution, i.e. how to start with the set of rectangles and lead up to the polygon.

My solution works in all cases except where parts or whole edges of two or more rectangles overlap each other.

How do I get rid of the points that make up the overlapping edges?

1 Answer 1

0

Per the linked question, I'm going to assume that the rectangles are axis-aligned and that they have pairwise disjoint interiors. Decompose each rectangle into four line segments, oriented clockwise. Repeat the following procedure for the horizontal and vertical segments.

Partition the horizontal segments by y. For each y, each segment gives rise to two events: a start event for the tail and a stop event for the head. Sort the events by x (note that the stop event for a segment oriented left comes before the corresponding start event). Initialize a variable sign = 0, then iterate through, performing sign += 1 on each start event and sign -= 1 on each stop. Whenever sign goes from 0 to 1, begin an oriented segment with its tail at the current sweep location. Whenever sign goes from 1 to 0, end that segment with its head at the current sweep location, discarding it if it's degenerate. Similarly, whenever sign goes from 0 to -1, begin an oriented segment with its head at the current sweep location. Whenever sign goes from -1 to 0, end that segment with its tail at the current sweep location, discarding it if it's degenerate.

2
  • Thanks, David. I shall try and see if this works with my problem.
    – Manish
    Sep 10, 2014 at 20:47
  • David, I was just able to get back to the problem. Your solution assumes that the rectangles have pairwise disjoint interiors. I have a bunch of intersecting rectangles. Also, I have to consider two adjacent rectangles (edges touch but theoretically do not intersect) as belonging to the group.
    – Manish
    Sep 24, 2014 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.