射线法判断点与包含简单曲线多边形关系的完善.pdfVIP

第 34卷第 5期 测绘科学 Vol34 No5 2009年 9 月 Science of Su rveying and M app ing Sep 射线法判断点与包含简单曲线多边形关系的完善 江 　平 , 刘民士 (武汉大学资源与环境科学学院 ,武汉 　430079) 【摘 　要 】点与多边形关系的判断问题一直是计算机图形学中的基本问题之一 , 目前判断点与多边形关系的射线 法只考虑多边形边界全部由直线组成 , 而在实际应用中 , 多边形边界经常包含简单曲线 。本文以圆弧为例 , 在分 析已有射线法基础上 , 提出对射线法的完善算法 , 解决了点与包含圆弧的复杂多边形关系的正确判定 。 【关键词 】射线法 ; 点; 简单曲线 ; 圆弧 ; 多边形 【中图分类号 】P282　　　　 【文献标识码 】A 　　　　 【文章编号 (2009) 在多变形外 。于是本文针对边界存在圆弧的情况 , 对原有 1　引言 算法进行了完善 。 点与多边形关系的判断问题一直是计算机图形学中的 2　简单曲线的概念 、数据结构及其在多边形数据 基本问题之一 , 因此也形成了诸多算法来解决这个 问题 。 [ 1 - 6 ] [ 1, 7, 8 ] 结构中组织 归纳起来比较常用的有射线法 、转角法 、面积判 断法 、相关边法 [ 11 - 12 ] 和栅格法 [ 13 ] , 而在所有的算法当中 　　定义 : 我们对简单曲线定义为具有连续的 , 单一凸凹 只有射线法才能解决点与含有孔洞的复合多边形的位置关 性的曲线 , 比较常用 的有 圆弧 , 椭 圆弧 , 抛物线 , 双 曲 ( ) 系 。射线法的原理是过给定点 P 作任意方向的一条射线 线等 。 (通常应用中使用水平或垂直射线 ,本文使用水平向右的射 数据结构 : 简单曲线的数据结构用曲线起始点 , 终止 ) 线 , 求得射线与多边形的边的交点个数 , 交点个数为奇 点坐标以及 曲线数学方程进行组织 。多变形 由曲线构成 , ( 数 , 点在多边形内部 , 交点个数为偶数 , 点在多边形外部 。 曲线是一个抽象类 , 曲线包括直线段 , 简单曲线 圆弧 ,椭 ( ) ) ( 然而当射线出现穿过多边形端点的时候 如图 1 , 其判断就 圆 , 抛物线 , 双 曲线等 , 它们通过一个类别属性 i_