寻找多个多边形的公共轮廓

Question

我正在尝试寻找一种算法，用于在多个多边形之间绘制共同的轮廓。我的意思是像这张图片上一样：

我们有两个矩形（在我的情况下它们将不是矩形，而是大部分角度为直角的多边形），我正在寻找共同的轮廓，就像第二部分图像中的红色路径。我看到的最大问题是找到我在第二部分图像中标记为黄色的新点。

多边形永远不会相交或接触自身。我按逆时针顺序将多边形存储为点。

我正在寻找一些提示、资源或甚至关键字，可以使我的任务变得更容易...

编辑：这有点像凸包，但是看着边缘而不是顶点，我想黄点可能位于我看来的边缘的延续线上。

编辑2：好的，我需要在多边形周围绘制给定大小的边框，但是以这样的方式，如果两个多边形距离小于边框大小，它们将具有共同的边框，这是两个没有“内部”部分的边框的总和，这两个多边形将被视为一个形状。因此，我正在尝试找到这个红色多边形，它将用于在其周围绘制此边框。

- Pax0r

---

虽然不完全符合您的要求，但也许凸包可以满足您的需求。有许多算法可用于计算凸包。 - hammar

是的，我正在研究凸包算法，但这会从一个多边形的顶点跳到另一个多边形，而不像我需要的那样保留边缘。 - Pax0r

你想把黄点放在哪里？在你的示例中，你所做的看起来相当随意。你能清楚地说明你想要什么吗？也就是说，“共同轮廓”是什么。 - Howard

@Gareth 确实如此，但在编辑之后，我更加困惑于 OP 到底想做什么。我仍然不明白红色轮廓的属性应该是什么。 - Howard

@Pax0r 一个合适的算法是通过边框大小来扩展每个多边形，并将重叠的大型多边形合并为一个。之后，如果需要，您可以再次将新的多边形缩小相同的量。 - Howard

Answer 1

首先，通过将所有边延伸至无限远，对多边形（黄色部分）的所有边进行剪裁，以添加额外的顶点。

将新的顶点连接到延伸的边上。这将为您提供一个多边形网格。

现在来看一下技巧：

起始条件：

• 选择最左上角的顶点，只能有一个！

• 选择与1找到的顶点相连且向右延伸的斜率最小的边。此边将始终位于最终多边形的周长上。

迭代：

• 从当前边开始，按顺时针顺序沿其他边行走。 当您这样做时，会遇到新的顶点，这些顶点可能连接到多个其他边。始终选择最逆时针的顶点并继续。这将始终使您保持在最终多边形的周长上。

结束条件：

• 一旦再次到达最左上角的顶点，请停止。

恭喜，您刚刚沿着多边形的外边缘行走。

- Nils Pipenbrinck

---

你的算法看起来正是我需要的，但我有一个问题，如何选择“最逆时针”的顶点... - Pax0r

Answer 2

我会搜索“最佳匹配边界框”，例如http://www.comp.nus.edu.sg/~tancl/Papers/DAS06/39-oyuanbuusu.pdf，当然还要递归地查找该文献的参考文献。

- msw

---

谢谢您的回答。看起来链接已经失效了。您能否提供DOI或标题和作者，或者更新链接？虽然已经过去七年了，但我仍然很感兴趣。 - 3244611user