判断点与简单多边形位置关系的新算法

New algorithm for determining position relation between simple polygon and point

基于射线法提出了一种新的判断点与简单多边形位置关系的算法。该算法是通过查找简单多边形所有顶点在确定区域内中斜率最小点,以此点确定一条射线,使得这条射线不穿过简单多边形的顶点。此算法不但保持了原来射线法相对其它方法有容易理解、计算简单等优势,并在此基础上排除了射线法中特殊的射线与简单多边形的顶点相交或射线过简单多边形边的特殊情况,大大地降低了算法的时间复杂度,提高了检测速度。

This paper proposes a new algorithm for determining the position relation between a simple polygon and a point,in which the point where the minimum slope is achieved is fixed by searching the slopes at all points in the fixed arrange in order to find a ray so that the ray don＇t pass through any vertex of the polygon.The algorithm not only keeps the other ray algorithm＇s advantages such as the easiness to be understood,being simple to computing,but also excludes the special cases that the ray passes through the vertices or the edges of the polygon so that the time complexity of the algorithm is reduced greatly and the test speed is enhanced.