简单多边形方向识别的健壮算法

Robust Algorithm for Identifying the Orientation of Simple Polygons

极值顶点前后相邻边矢量叉积法是识别任意简单多边形方向的最优算法 该算法存在的问题是 :当极值顶点前后相邻边夹角接近 0°或 180°时 ,叉积结果接近 0 ,因此存在二义性 ,会导致错误的方向识别 针对现有算法对奇异情形方向判别解决不彻底的问题 定义了多边形极值顶点奇异情形 ,对相邻边夹角接近 0°和 180°两种奇异情形给出了判定方法 ;提出了极点前后点坐标比较法和极点序号大小比较法 ,有效地解决了所有奇异情形下的方向识别问题 ,它们都可以发展成为独立的方向判断算法 实验结果表明 ,该算法简单高效 ,健壮性强 ,时间复杂度为O(n)

Traditional cross product method faces the difficulty in identifying the orientation of simple polygons in the case that the included angle between two neighboring edges is near 0 or 180 degree, with their cross product close to 0, so that a wrong result may be generated. In this paper, a new method in distinguishing 0 degree case from 180 degree case is given, and a novel orientation identification algorithm is presented. In the case of 0 degree,the extreme vertex serial number comparison method is used to get the orientation. And in the case of 180 degree, the coordinate value comparison method is used to get the orientation. Experimental results show that the new algorithm is robust, and an improvement on the identification performance is achieved in comparison with the cross product method.