简单多边形方向及顶点凹凸性的快速判定

A Rapid Identification for the Orientation and Vertices Convexity-Concavity of Simple Polygon

基于简单多边形方向与顶点凹凸性的内在联系,采用极值点性质判定多边形方向,通过多边形顶点坐标判定其拓扑映射点之间的位置关系,结合以上两方面对顶点的凹凸性作出判断。对基于拓扑映射的多边形顶点凹凸判别算法作出有效的改进,避免了原算法中大量的重复计算。实践证明,有效的减少计算次数,提高了效率。

This algorithm uses extremity vertices to identify the orientation and use coordinates of polygon vertices to identify the relationship between its mapping points. By combining the two ideas above, convexity or concavity of a vertex can be determined. An effective improvement about algorithm to check convexity or concavity of polygon vertices is given and a lot of repeat computation in original algorithm is avoided. Experiment results prove the computing times ＆ efficiency of this algorithm.