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

摘要

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