Algorithm for finding polygon vertices for a given set of overlapping rectangles

Question

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?

Answer 1

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.