多邊形平滑

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