algorithm - 寻找多个多边形的共同轮廓

Question

我试图找到一种在多个多边形之间绘制共同轮廓的算法。我的意思是在这张照片上：

两个多边形来寻找轮廓

我们有两个矩形（在我的情况下，它们不是矩形，而是大多数角度为直角的多边形）并且我正在寻找共同的轮廓，例如图像第二部分的红色路径。我看到的最大问题是找到我在图像的第二部分标记为黄色的新点。多边形永远不会相交或接触自身。我以逆时针顺序将多边形存储为点。

我正在寻找一些我应该用谷歌搜索的线索、来源甚至关键字，这可能会使我的任务变得更容易......

编辑：它有点像凸包，但看边缘而不是顶点，当我看它时，黄点可能在边缘的延续上。

EDIT2：好的，我需要在多边形周围绘制一个给定大小的边框，但是如果两个多边形比边框大小更近，它们将有共同的边框，这是两个没有“内部”部分的边框的总和它和这两个多边形将被视为一个形状。所以我试图找到这个红色多边形，它将用于在它周围绘制这个边框。

score 3 · Accepted Answer

首先将额外的顶点添加到您的多边形（黄色的），方法是将所有边与延伸到无穷大的所有其他边相剪裁（例如，将边变成无限线）。

将新顶点连接到扩展边。这将为您提供多边形网格。

现在来了诀窍：

开始条件：

迭代：

从您当前的边缘，按顺时针顺序沿着其他边缘走。执行此操作时，您会遇到新的顶点，这些顶点可能会连接到多个其他边。始终选择最逆时针方向的一个并继续。这将始终使您保持在最终多边形的周边。

结束条件：

恭喜，您刚刚绕过多边形的外边缘。

score 0 · Accepted Answer

我会在http://www.comp.nus.edu.sg/~tancl/Papers/DAS06/39-oyuanbuusu.pdf中寻找“最合适的边界框” ，当然还有递归的参考书目.

2 回答 2