凸多邊形

凸多邊形（Convex Polygon）可以有以下三種定義：

沒有任何一個內角是優角（Reflexive Angle）的多邊形。

如果把一個多邊形的所有邊中，有一條邊向兩方無限延長成為一直線時，其他各邊都在此直線的同旁，那麼這個多邊形就叫做凸多邊形。

凸多邊形是一個內部為凸集的簡單多邊形。簡單多邊形的下列性質與其凸性等價：1、所有內角小於等於180度。2、任意兩個頂點間的線段位於多邊形的內部或邊上。3、多邊形內任意兩個點，其連線全部在多邊形內部或邊上。

所有的正多邊形都是凸多邊形。

所有的三角形都是凸多邊形。

凸多邊形的內角均小於或等於180°，邊數為n（n屬於Z且n大於2）的凸多邊形內角和為（n－2）×180°，但任意凸多邊形外角和均為360°，並可通過反證法證明凸多邊形內角中銳角的個數不能多於3個。

凸多邊形所有對角線都在內部，邊數為n的凸多邊形對角線條數為2n(n-3)，其中通過任一頂點可與其餘n－3個頂點連對角線。

1）角度法：

判斷每個頂點所對應的內角是否小於180度，如果小於180度，則是凸的，如果大於180度，則是凹多邊形。

2）凸包法：

這種方法首先計算這個多邊形的凸包，關於凸包的定義在此不再贅述，首先可以肯定的是凸包肯定是一個凸多邊形。如果計算出來的凸多邊形和原始多邊形的點數一樣多，那就說明此多邊形時凸多邊形，否則就是凹多邊形。

3）頂點凹凸性法

利用以當前頂點為中心的矢量叉乘或者計算三角形的有符號面積判斷多邊形的方向以及當前頂點的凹凸性。

假設當前連續的三個頂點分別是P1，P2，P3。計算向量P1P2,P2P3的叉乘，也可以計算三角形P1P2P3的面積，得到的結果如果大於0，則表示P3點在線段P1和P2的左側，多邊形的頂點是逆時針序列。然後依次計算下一個前後所組成向量的叉乘，如果在計算時，出現負值，則此多邊形時凹多邊形，如果所有頂點計算完畢，其結果都是大於0，則多邊形時凸多邊形。

4）辛普森面積法

利用待判別的頂點以及前後兩個頂點所組成的三角形，利用辛普森公式計算其面積，如果此三角形面積與整個多邊形面積符號相同，那麼這個頂點是凸的；如果此三角形面積與整個多邊形面積符號不同，那麼這個頂點是凹的，即整個多邊形也是凹多邊形。