Finding common outline of multiple polygons

问题:

Im trying to find an algorithm for drawing a common outline between multiple polygons. What I mean is like on this picture:

We have two rectangles (In my case they will not be rectangles, but polygons with most of their angles as right angle) and Im looking for common outline like a red path on second part of image. The biggest problem as I see it is finding new points which I marked yellow on the second part of image. The polygons will never intersect or touch itselfs. Im storing a polygon as points in counter-clockwise order.

Im looking for some clues, sources or even keywords on which I should google, which could make my task little easier...

EDIT: its kind like in convex hull but looking at the edges not at the vertices, yellow point are probably on the continuaion of the edges as I look at it.

EDIT2: Ok, I need to draw a border of given size around polygons, but in such way that if two polygons are closer than the border size they will have common border which is kind of a sum of two borders without 'inner' part of it and this two polygons will be treated as a one shape. So Im trying to find this red polygon which will be used to draw this border around it.

回答1:

Start by adding extra vertices to your polygons (your yellow ones) by clipping all edges against all other edges extended to infinity (e.g. turn your edges into infinite lines).

Connect the new vertices to the extended edges. This will give you a polygonal mesh.

Now comes the trick:

Start-condition:

• Pick the most top-left vertex, there can be only one!

• Pick the edge with the least slope that connects to the vertex found by 1 and extends to the right. This edge will always be on the perimeter of your final polygon.

Iteration:

• From your current edge, walk along the other edges in clockwise order. You will encounter new vertices as you do this, and these vertices may connect to multiple other edges. Always pick the most counter-clockwise one and continue. This will always keep you on the perimeter of your final polygon.

End Condition:

• Stop as soon as you reach the top-left vertex again.

Congratulations, you just walked around the outer edge of your polygon.

回答2:

I'd look for "best-fit bounding box" as in http://www.comp.nus.edu.sg/~tancl/Papers/DAS06/39-oyuanbuusu.pdf and of course, the bibliography of that, recursively.