寻找多个多边形的共同轮廓
我试图找到一种在多个多边形之间绘制公共轮廓的算法。 我的意思就像这张图片上的那样：
我们有两个矩形（在我的情况下，它们不会是矩形，但大多数角度为直角的多边形），我正在寻找共同的轮廓，例如图像第二部分上的红色路径。我认为最大的问题是找到新的点，我在图像的第二部分将其标记为黄色。 多边形永远不会相交或接触自身。我按逆时针顺序将多边形存储为点。
我正在寻找一些线索、来源甚至关键字，我应该在谷歌上搜索，这可以使我的任务变得更容易......
编辑：它类似于凸包，但查看边缘而不是顶点，黄点可能位于当我看着它时，边缘的延续。
编辑2：好的，我需要在多边形周围绘制给定大小的边框，但是这样的话，如果两个多边形比边框大小更接近，它们将具有公共边框，这是两个边框的总和，没有“内部”部分它和这两个多边形将被视为一个形状。所以我试图找到这个红色多边形，它将用于在其周围绘制边框。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
首先向多边形（黄色的）添加额外的顶点，方法是将所有边与延伸到无穷大的所有其他边一起剪切（例如，将边变成无限线）。
将新顶点连接到延伸边。这将为您提供一个多边形网格。
现在来了技巧：
开始条件：
选择最左上角的顶点，只能有一个！
选取与 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:
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:
Congratulations, you just walked around the outer edge of your polygon.
我会寻找“最适合的边界框”，如 http://www.comp.nus.edu.sg/~tancl/Papers/DAS06/39-oyuanbuusu.pdf，当然，还有参考书目，递归地。
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.