如何簡化包圍多邊形？

01-05

給定一個n邊簡單（凹）多邊形P，求一個m邊多邊形Q（m&
進一步最好能處理 polygon with holes：

---
補充一些相關參考（按年分排列）
[1] Dori, Dov, and Moshe Ben-Bassat. "Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition." Computer Vision, Graphics, and Image Processing 24.2 (1983): 131-159.
[2] Aggarwal, Alok, Jyun-Sheng Chang, and Chee K. Yap. "Minimum area circumscribing polygons." The Visual Computer 1.2 (1985): 112-117.

哎……不知道的別瞎說，給你個六十邊形，讓你用三角形蓋，還保留j條邊呢，保留你妹啊。說減量的，當然可以，不過也當然不是最優。

可惡的 @Yong He 居然在答案裡面@我，我只好隨便說說。我說的是求精確解，近似解另行討論。

這個問題很難，我也只是說在我認為成立的hypothesis下的演算法。我現在沒時間證明，intuitively我覺得是對的，有空更新吧。

假設多邊形有向面積為正。

首先看不考慮洞的情況。

在最終答案構成的多邊形裡面，我猜想不存在連續兩條邊只包含一個原多邊形頂點，只包含一個頂點的情況當且僅當在最優解的多邊形中前後兩條邊的有向角大於pi，所以不可能連續出現，否則在往前後兩個角度rotate epsilon後定有一個面積更小。

因
此candidate頂點一共有如下兩種：作所有過兩個頂點，且所有兩點之間的鏈均在連線的左側或者線上，所有這樣的直線的交點且在多邊形外部的這部分頂
點。這樣的頂點一共有O(n^4)個。另一類是對於有向角大於pi，且其向內延長線不穿過多邊形內部的任意兩條邊，經其中鏈上的第三點在等腰三角形位置所
生成的點。考慮到第三點的唯一性，這類點一共O(n^2)個。

至此就可以dp了，因為上述兩類點之間全序，維護一個右鏈，每次加入一個新點，轉一圈即可。

最後是挖洞問題，這個其實不難。假設洞都是非退化洞，按上述做法維護左鏈，然後求得所有用k(&>2,&

修改: 好神奇, 有個一模一樣的問題2年前在cstheory上被問了呢... 兩年前在cstheory上的回答...

這個問題很可能是open的.

如果只要求Q是convex的話有各種好處(比如可以寫成一個LP). Q凸多邊形可以看Minimum area circumscribing Polygons O(n^2 log n log m)的演算法.

Eppstein提到了另一個如何improve到O(n^2 log m)的演算法. http://mathoverflow.net/questions/11580/minimum-area-bounding-quadrilateral-algorithm

謝邀。感覺這個問題有非常多種情況需要單獨處理才能做到高效。我對計算幾何演算法不太熟悉，邀請演算法大神 @Yan Gu 回答一下。

關鍵詞：

包圍體？

Bounding volume

正好研究過這個問題，也曾完整實現過[ACY85]（即題目中的參考文獻[2]）里的演算法，所以可以來聊一下。

對於凸多邊形, 文獻[ACY85]已經解決得很完美了（雖然後來作者又進一步改進演算法優化掉了一個log(n), 但這不是重點）, 這裡也要贊一下 @Yan Gu 的思路, 一下就找到了切入點, 不過其後提到的"第三點在等腰三角形位置..."是不對的, 正確的關係應該是第三點(support point)應該是這條「懸空」的邊(non-flushed edge)的中點, 而且一定存在最優解使得這樣的邊至多只有一條。

但是對於一般的簡單多邊形, 這裡所提到的所有方法都失效了。在[CY84]中提到了一個O(n^3logk)的演算法，但網上可下載的PDF少了幾頁因此不得詳請, 推測應該也是只針對凸多邊形, 其他幾篇類似的文獻也大抵如此。既然谷大爺幫不上忙，下面不妨談談我自己關於這個問題的分析（以下內容為腦洞大開無根據亂扯）:

在一般簡單多形邊中，最優解的邊仍然不外乎這兩種類型：

類型1. 包含了原多邊形的兩個或者更多頂點.

類型2. 只包含了原多邊形的一個頂點，而且原多邊形頂點一定正好是該邊的中點，否則可旋轉一個epsilon得到一個更優解。

而與凸多邊形不同的地方, 或者說問題的難點在於：

1. 類型2的邊不再最多只有一條, 它可以出現多條甚至連續出現。連續出現的情況相當棘手，因為這類似於求Midpoint polygon的逆(Kasner"s problem), 更麻煩的是Kasner"s problem的解可以有無窮多個, 每一個解都是局部最優的，在這種情況下怎麼找到全局最優解?

2. 在凸多邊形的情況下因為有Interspersing Lemma[ACY85]的存在使得DP成為可能，在凹多邊形下如果沒有類似的性質則意味著只能暴搜?

至此，我已沒有能力繼續深入了，所以在實際應用中只是引進了凸多邊形的簡化。如果誰知道更多的信息請一定告訴我。

[CY84] Chang, J. S., and C. K. Yap. "A Polynomial Solution For Potato-Peeling And Other Polygon Inclusion And Enclosure Problems." Foundations of Computer Science, 1984. 25th Annual Symposium on. IEEE, 1984.

不包圍的話可以用道格拉斯演算法，opencv里有實現，挺好用的

每兩個邊+一條新邊做個連線，計算所有兩條邊減成一條邊的面積增加量。取最小的一個。

挨著計算，直到n縮減成m

問題定義不是很明確，首先如果m是輸入條件，問題好難。

如果m是輸出，只是要求m小於n，分兩種，一是輸出多邊形沒要求的話，直觀來看應該就是找個面積最小的凹進去的三角「填平"就行，問題不難。洞也不是大問題。

如果輸出多邊形要求是凸多邊形，那應該就是求最小凸包。