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

A New Algorithm for Identifying Polygons' Orientation

作　　者：丁健[1] 江南[1] 芮挺[2] 

机构地区：[1]中国科学院南京地理与湖泊研究所 [2]解放军理工大学工程兵工程学院,南京210007

出　　处：《计算机工程》2006年第9期47-50,共4页Computer Engineering

基　　金：中国科学院知识创新工程领域前沿基金资助项目(CXNIGLAS-A02-012)

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

关 键 词：简单多边形 多边形方向 特征点比较法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP391[自动化与计算机技术—计算机科学与技术]