计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (2): 185-186.DOI: 10.3778/j.issn.1002-8331.2009.02.054

• 图形、图像、模式识别 • 上一篇    下一篇

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

董秀山,刘润涛   

  1. 哈尔滨理工大学 数学系,哈尔滨 150080
  • 收稿日期:2008-01-04 修回日期:2008-04-21 出版日期:2009-01-11 发布日期:2009-01-11
  • 通讯作者: 董秀山

New algorithm for determining position relation between simple polygon and point

DONG Xiu-shan,LIU Run-tao   

  1. Department of Mathematics,Harbin University of Science and Technology,Harbin 150080,China
  • Received:2008-01-04 Revised:2008-04-21 Online:2009-01-11 Published:2009-01-11
  • Contact: DONG Xiu-shan

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

关键词: 点, 简单多边形, 射线, 算法, 斜率

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