New algorithm for determining position relation between simple polygon and point
Runtao Liu · Computer Engineering and Applications Journal · 2009
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.