Determining Convexo-Concave Vertices of Polygonby Dynamic Distinct Partition
基于动态分区的多边形顶点凹凸性判别

基于判别顶点对应的边，对平面进行动态分区，形成全正区、全负区和非全正负区，将顶点凹凸性判别转化为后继顶点所在区域位置判别。而全正区、全负区情况只需通过简单判别即可确定顶点的凹凸性，避免乘法运算，其复杂度按概率为(n／4)次乘法(n为多边形顶点数)。试验结果表明，该算法速度快，稳定可靠。