凸多边形

凸多边形（Convex Polygon）可以有以下三种定义：

没有任何一个内角是优角（Reflexive Angle）的多边形。

如果把一个多边形的所有边中，有一条边向两方无限延长成为一直线时，其他各边都在此直线的同旁，那么这个多边形就叫做凸多边形。[1]

凸多边形是一个内部为凸集的简单多边形。简单多边形的下列性质与其凸性等价：1、所有内角小于等于180度。2、任意两个顶点间的线段位于多边形的内部或边上。3、多边形内任意两个点，其连线全部在多边形内部或边上。

凸多边形

所有的正多边形都是凸多边形。[1]

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

凸多边形的内角均小于180°，[3]边数为n（n属于Z且n大于2）的凸多边形内角和为（n－2）×180°，但任意凸多边形外角和均为360°，并可通过反证法证明凸多边形内角中锐角的个数不能多于3个。

凸多边形所有对角线都在内部，边数为n的凸多边形对角线条数为2-1n(n-3)，其中通过任一顶点可与其余n－3个顶点连对角线。[2]

1）角度法：

判断每个顶点所对应的内角是否小于180度，如果小于180度，则是凸的，如果大于180度，则是凹多边形。

2）凸包法：

这种方法首先计算这个多边形的凸包，关于凸包的定义在此不再赘述，首先可以肯定的是凸包肯定是一个凸多边形。如果计算出来的凸多边形和原始多边形的点数一样多，那就说明此多边形时凸多边形，否则就是凹多边形。

3）顶点凹凸性法

利用以当前顶点为中心的矢量叉乘或者计算三角形的有符号面积判断多边形的方向以及当前顶点的凹凸性。

假设当前连续的三个顶点分别是P1，P2，P3。计算向量P1P2,P2P3的叉乘，也可以计算三角形P1P2P3的面积，得到的结果如果大于0，则表示P3点在线段P1和P2的左侧，多边形的顶点是逆时针序列。然后依次计算下一个前后所组成向量的叉乘，如果在计算时，出现负值，则此多边形时凹多边形，如果所有顶点计算完毕，其结果都是大于0，则多边形时凸多边形。

4）辛普森面积法

利用待判别的顶点以及前后两个顶点所组成的三角形，利用辛普森公式计算其面积，如果此三角形面积与整个多边形面积符号相同，那么这个顶点是凸的；如果此三角形面积与整个多边形面积符号不同，那么这个顶点是凹的，即整个多边形也是凹多边形。