多边形平滑

Question

我想“平滑”多边形，以使它们保持大部分“外部”外观，但是没有“内部走廊”。

把它放到上下文中：下图显示了一组多点创建的多边形。下面的多边形大致代表一个房间，每个多边形的内部部分都是门和其他东西。 现在我想重新改进这些多边形，所以它们再次看起来像房间。

我的问题是：什么（一组）算法符合我的需求？创建一个凸包或缓冲多边形不是我想要的（尽管我尝试过）。缓冲区多边形不保留多边形的外观，并且凸包不会去除这些向内的部分。

这就是它看起来像： 这是一个很糟糕的photoshop图像，我想它看起来像。 注意小内部走廊被删除。

编辑：常用的简化也将无法正常工作，可能是。这就是我的多边形如何与Douglas Peucker一起简化的样子。距离容差已经很激进，但内部凹痕仍然没有消失。这并不令人感到意外，因为内部的凹陷很长，所以也是相当值得期待的。

编辑2：

这就像我想删除这个例子中的内凹痕：

Answer 1

什么你正在寻找的短语多边形简化下进，其中有大量的文献。 开始可以找到at this link, 从中复制下面的图像。

---

 

---

有旨在实现特定优化标准， 许多调查了 Handbook of Discrete and Computational Geometry许多复杂的算法。

Answer 2

删除“凹痕”（如在您的“编辑2”中）可以通过称为“数学形态学”的每像素级别的方法来完成。维基百科网页[1]很好解释，特别看看开幕和关闭操作，可能适合您的需求。

[1] https://en.wikipedia.org/wiki/Mathematical_morphology