陈金林，刘谢进，李宁

(淮南师范学院 数学与计算科学系,安徽 淮南 232038)

引言

在计算几何、计算机图形学等领域常用简单多边形来描述几何形体，很多情况下运算处理的对象是简单平面多边形[1]。判别多边形是否为简单多边形以及简单多边形内外点的判别算法就很重要，因为这些算法是许多算法的基础[2]。迄今为止，对判断点与多边形位置关系算法的研究比较多。经典的算法有叉积判断法[3]，射线法[4，5]，有向三角形面积之和的符号法[6]，有向回路法和网格法[7]等。其中叉积法只适用于凸多边形，并且对所有边都需叉积运算，运算量大。文献[8]所涉及到有向回路法本质上是非零环绕数规则法，但它只适用于凸多边形，空间复杂度较大，本质上是一种以空间换取时间的算法。射线法通常需要求交点，虽然在文献[8]对射线法进行了改进，但也只是减少求交点数量。在文献[9]中所提及的射线法不需要求交点，但对关联集合求解判别增加了空间复杂度。

点与相关边的判别法[10-14]是扫描与点关联性（密切边[11]、单调性[12]）最大的边，在多边形中这样的边可能不唯一，判别测试点与此相关边的位置关系，确定点与多边形的位置关系。此类算法计算速度快，稳定性高，但是查找到的相关的边通常不唯一。本文提出了基于点与角的最短距离的一种新的方法，扫描与点距离最小时关联的边，这样的边在多边形中可能不止一个，但扫描过程结束后只保留一个作为判断依据，在多边形中，有两个角共有这条边。……