Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Your example still has unnecessary vertices in the output. $\endgroup$– orlpApr 21, 2019 at 0:31
-
$\begingroup$ Welcome! As the question asker, you can upvote and/or accept an answer. If you find it helpful, please upvote. If it solved your problem or was the most helpful in finding your solution, accept it. That is the basic protocol. Have you checked what to do when someone answers? In fact, upvoting is not just about your questions. When a question or an answer helps you, why not upvote? (This comment will be deleted upon feedback) $\endgroup$– John L.May 15, 2020 at 6:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
- 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.
answered Apr 21, 2019 at 2:52
-
-
$\begingroup$ 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. $\endgroup$ Apr 22, 2019 at 10:40
-
-
$\begingroup$ 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? $\endgroup$ Apr 22, 2019 at 14:52
-
$\begingroup$ 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? $\endgroup$ Apr 22, 2019 at 14:59