Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?

• Your example still has unnecessary vertices in the output. – orlp Apr 21 '19 at 0:31

• Form a list of the $$4n$$ edges making up the $$n$$ rectangles.
• Delete every edge that appears twice.

The edges that remain describe the outside of the polygon. If you want to list these edges in clockwise or anticlockwise order, that's easy enough to do -- just pick an arbitrary starting vertex and find one of the two edges it is incident on, then find the other edge that the other vertex of that edge is incident on, repeating this until you hit the original vertex again. If you encounter two edges in the same direction, you might want to turn them into a single, longer edge as you go.

• The problem is there are more than two edges that are incident on. For example link On this point the algorithm doesn't know which edge to take. – Anubitum Apr 22 '19 at 9:49
• I don't understand -- the black rectangle shows where exactly two edges were (the bottom edge of the square above it, and the top edge of the square below it), and they have been correctly deleted. I don't know what you're trying to show with the pink rectangle -- that single edge should remain, and it seems that it does. – j_random_hacker Apr 22 '19 at 10:40
• Ok maybe I explained badly. Here is an better example. In one point of the algorithm its not clear which incident edge to take since they have same distance. link – Anubitum Apr 22 '19 at 11:30
• I appreciate the effort, but I'm still confused. The top row in your linked image seems to label vertices, not edges. Maybe the root cause is that the input is not being presented in the way I had assumed. I was thinking that your input is a set of rectangles (there are 5 in your linked image), given by, for example, their top-left and bottom-right co-ordinates. I further assumed that whenever two edges from two rectangles overlap at all, they are actually identical (in the images you have shown so far, they are; but actually this assumption can be relaxed if need be.) Is this correct? – j_random_hacker Apr 22 '19 at 14:52
• Here is a diagram showing the number of times that each edge appears, in my understanding of the problem: ibb.co/qDCP2Pc Basically, imagine each square is a thin metal frame. Cut each frame at each of the four corners. Now count the number of metal strips lying in each position. Does it make sense now? – j_random_hacker Apr 22 '19 at 14:59