一种多边形方向识别的新算法

A New Algorithm for Identifying Polygons' Orientation

针对传统经典叉积法在识别任意简单多边形方向时不能解决奇异情形的问题,提出了多边形方向识别的特征点比较法,用列举法作了几何证明。算法中的运算主要是整数之间的大小比较,因而速度较快,并且有效地解决了奇异情形下的方向识别问题。分析表明,该算法能对所有简单多边形作出正确的方向判断,具有较好的通用性和鲁棒性,可以发展成为独立的方向判断算法。实验表明,该算法比叉积法具有更高的执行效率。

Cross product algorithm is the classical and traditional algorithm for identifying polygons＇ orientation, it faces the difficulty in cases when the included angle between two neighboring edges near 0 or 180 degrees, the value of cross product is close to 0, and this may lead to wrong result. A new algorithm for identifying polygons＇ orientation based on comparing feature points is presented; the geometric proof for the algorithm is given. The main computation in the new algorithm is integers＇ comparison, this makes it execute faster. Analyses show that the new algorithm is robust. Experimental results show an improved performance on the identification of orientation in comparison with the cross product algorithm is achieved.