Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (2): 185-186.DOI: 10.3778/j.issn.1002-8331.2009.02.054
• 图形、图像、模式识别 • Previous Articles Next Articles
DONG Xiu-shan,LIU Run-tao
Received:
Revised:
Online:
Published:
Contact:
董秀山,刘润涛
通讯作者:
Abstract: 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.
Key words: point, simple polygon, ray, algorithm, slope
摘要: 基于射线法提出了一种新的判断点与简单多边形位置关系的算法。该算法是通过查找简单多边形所有顶点在确定区域内中斜率最小点,以此点确定一条射线,使得这条射线不穿过简单多边形的顶点。此算法不但保持了原来射线法相对其它方法有容易理解、计算简单等优势,并在此基础上排除了射线法中特殊的射线与简单多边形的顶点相交或射线过简单多边形边的特殊情况,大大地降低了算法的时间复杂度,提高了检测速度。
关键词: 点, 简单多边形, 射线, 算法, 斜率
DONG Xiu-shan,LIU Run-tao. New algorithm for determining position relation between simple polygon and point[J]. Computer Engineering and Applications, 2009, 45(2): 185-186.
董秀山,刘润涛. 判断点与简单多边形位置关系的新算法[J]. 计算机工程与应用, 2009, 45(2): 185-186.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2009.02.054
http://cea.ceaj.org/EN/Y2009/V45/I2/185