一种改进的点定位算法

摘要：

通过对传统的点定位算法——奇偶法则算法的分析,提出了一种改进的奇偶法则的实现算法.在改进算法中,从待判定点引出的射线定义为与x轴平行且与其同向,对射线与区域边界边的相交情况进行了分类处理.通过分析射线与边界边的位置关系,只有少数情况需要计算其交点,而大部分情况只需简单比较即可得出相交情况.当射线穿过两条相邻边界边的交点时,根据定义的法则,只进行一次相交情况的判定.因此,改进算法减少了计算交点的次数,提高了点定位的效率.最后通过实际应用,对传统算法与改进算法在同样条件下的处理时间进行了比较.

关键词：点定位、奇偶法则、平面区域

所属期刊栏目：17

分类号：TP391(计算技术、计算机技术)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：65-67