基于动态分区的多边形顶点凹凸性判别

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

Determining Convexo-Concave Vertices of Polygonby Dynamic Distinct Partition

Polygonal vertices convexo-concave determining is one of the fundamental issues in Computer Graphics. In this paper, plane space is separated into 2 region defined as positive region and negative region based on the direction and the stretched of the line segment. Accordingly transform identification of convexity or concavity of the next vertices into identification of the region position. Consequently the operation of multiplication can be averted. In order to do the best in practical determining, 3 areas is separated of the plane space, whereas not thesame as earlier. These area are based on two horizontal lines, two vertical lines and two 45°diagonal lines through the vertices of the line segment. Because the partition is based on the polygon vertices and it has dynamic, therefore it's a dynamic distinct partition. These areas are defined as positive area, negative area or mixed area. In the case of the positive area or the negative area, we can confirm the convexity or concavity of the vertices through simple distinguishing. The result of test indicates it is a simple, highly efficient and reliable algorithm with high speed requires only (n/4) multiplication and(12n) comparisons.