本節(jié)主要講解了如何將二維多邊形劃分為多個不相交的三角形。
一、畫廊問題 art gallery problem
????????考慮如下場景，在一個尺寸為多邊形的畫廊中放置攝像頭（哨兵），需要放幾個才能完全覆蓋該場景？可以看到下圖至少需要兩個哨兵。
? ? ? ? 如下圖，若多邊形是凸多邊形或星形多邊形，那么只須在中間的核位置放一個即可，此情況為該問題的最小解（下界）：
? ? ? ? 若多邊形不規(guī)則，那么最多n個點，即n多邊形的每個頂點都設(shè)置一個哨兵，就可以將整個多邊形覆蓋，因此問題的最大解（上界）為n。
?????????實際上，對于n個頂點的不規(guī)則多邊形而言，最多只須n/3個點即可覆蓋，如下圖紅點所示：
文章來源：http://www.zghlxwxcb.cn/news/detail-406587.html
因為場景不同導(dǎo)致的情況不同，在數(shù)學(xué)上有證明指出畫廊問題是NP-Hard問題，就是非確定性多項式困難問題文章來源地址http://www.zghlxwxcb.cn/news/detail-406587.html
二、Fisk's Proof
一些概念：
- 扇形：一個有核點的星形多邊形。每個扇形可以由一個點覆蓋整個扇形。
到了這里，關(guān)于計算幾何——三角剖分（Triangulation）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
