有沒有求多邊形的狹窄部分的演算法？

有沒有這樣的演算法：對於任意的多邊形，可以找出其狹窄的區域，在這些區域側邊上的任何一處出發，都能繪製出剛好穿過多邊形且長度小於等於L的線段；或者反過來，不通過這些區域，就無法繪製這樣一條線段？ 見圖：

---

我不知道有沒有現成的解決方案，我想到的方法是兩個步驟：

1. 找出所有邊對滿足：邊與邊之間的最短距離少於L、邊對形成的四邊形位於原多邊形之內。
2. 把邊對的結果（四邊形）合併為多邊形。

對於步驟1，暴力地算每對邊距離就是O(E^2)，位於多邊形內的測試應該要O(E)，合計O(E^3)。如果加上一些空間數據結構，應該可以較快找出少於半徑L內的邊。第2步用一般的幾何庫可實現。

另一個方法是，找到一個邊對後，嘗試擴展它。直至不能擴展，就是一個區域。然後再跳過一條邊繼續搜尋其他邊，看看能否形成其他區域。

---

在邊很零碎的情況下（比如曲線用大量線段表示），精確計算會很複雜。

可以考慮把整個多邊形先柵格化，有可能會一定的加速（我不確定， 就是胡亂猜的）。

---

對每條邊做L半圓和矩形（圖1），對其餘邊截取所在該區域部分，再以截e2所得線段兩端點作圓心作L圓截e1線段，組成區域四邊形（圖2）；最後取所有區域的並集。

另外，題主的「穿過多邊形」要求，只測試不相鄰邊就應該可以了

---

應該可以找出小於L的邊集合，然後從這些邊往外擴展形成區域。

---

可不可以使用軟體將面積畫出來計算呢

---

最近學到定積分……恩我不懂

---

有，以整體面積減去

---

先找多邊形的medial axis,然後從medial axis往兩邊穿，看長度是不是&>L。找medial axis一堆現成的程序，找幾個跑跑看看結果咋樣..

---

推薦閱讀：