资源描述：
《射线法判断点与包含简单曲线多边形关系的完善》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第34卷第5期测绘科学Vol134No152009年9月ScienceofSurveyingandMappingSep1射线法判断点与包含简单曲线多边形关系的完善江平,刘民士(武汉大学资源与环境科学学院,武汉430079)【摘要】点与多边形关系的判断问题一直是计算机图形学中的基本问题之一,目前判断点与多边形关系的射线法只考虑多边形边界全部由直线组成,而在实际应用中,多边形边界经常包含简单曲线。本文以圆弧为例,在分析已有射线法基础上,提出对射线法的完善算法,解决了点与包含圆弧的复杂多边形关系的正确判定
2、。【关键词】射线法;点;简单曲线;圆弧;多边形【中图分类号】P282【文献标识码】A【文章编号】100922307(2009)0520220203在多变形外。于是本文针对边界存在圆弧的情况,对原有1引言算法进行了完善。点与多边形关系的判断问题一直是计算机图形学中的2简单曲线的概念、数据结构及其在多边形数据基本问题之一,因此也形成了诸多算法来解决这个问题。[1-6][1,7,8]结构中组织归纳起来比较常用的有射线法、转角法、面积判[11-12][13]断法、相关边法和栅格法,而在所有的算法当中定义:我
3、们对简单曲线定义为具有连续的,单一凸凹只有射线法才能解决点与含有孔洞的复合多边形的位置关性的曲线,比较常用的有圆弧,椭圆弧,抛物线,双曲系。射线法的原理是过给定点(P)作任意方向的一条射线线等。(通常应用中使用水平或垂直射线,本文使用水平向右的射数据结构:简单曲线的数据结构用曲线起始点,终止线),求得射线与多边形的边的交点个数,交点个数为奇点坐标以及曲线数学方程进行组织。多变形由曲线构成,数,点在多边形内部,交点个数为偶数,点在多边形外部。曲线是一个抽象类,曲线包括直线段,简单曲线(圆弧,椭然而当射
4、线出现穿过多边形端点的时候(如图1),其判断就圆,抛物线,双曲线等),它们通过一个类别属性(i_会出现异常,针对这些异常,文献[1]提出了以下方法:Type)进行识别。让射线围绕点P作一个无限小的逆时针旋转不改变P与多3射线与圆弧的相交关系分析边形的内外关系,这样,射线就不再穿过端点。因此,若我们想象作了这个无限小的旋转,可以确定:当一条边的如果多边形的某一边界出现圆弧,根据射线与圆弧的两个端点都被射线穿过,则这条边要被忽略,当成没有交交点个数(有一个和两个)以及圆弧端点与射线的位置关系点;当一条边
5、的有且仅有一个端点被射线穿过,则如果该(端点被射线穿过,或是在射线上方,或是在射线下方)将边的另一个端点的Y坐标值大于P的Y坐标值,则这个交射线与圆弧相交的情况划分为两大类,共12种情况。点要被计数,否则,忽略这条边,当成没有交点。这个方311射线与圆弧有且只有一个交点法对于多边形边为直线段是是完全正确,然而,在实际应在这种情况下,又根据射线与圆弧端点的位置关系归用过程中,多边形的边不单单是直线段,也有为圆弧的情纳为以下三种情况。况,在这种情况下,根据文献1的判断方法会出现错误。1)圆弧一个端点严格
6、位于射线上方,另一个端点严格如图2,显然,点P在多边形边内,但根据文献1的方法,位于射线下方,如图3,4所示:PP′与直线段CD有一个交点,PP′与弧段AB的关系不能判断(文献[1]未能明确的定义),假如按照正常计算一个交点,则PP′与多边形共有2个交点,为偶数,错误判断点2)圆弧两个端点严格位于射线的同一方向,如图5,6所示:作者简介:江平(19832),男,江西抚州人,博士生,研究方向为生态评价与土地信息系统。E2mail:jiangp508@sohu1com3)圆弧有且仅有一个端点被射线穿过,
7、如图7,8所示:收稿日期:2008203218312射线与圆弧有且只有两个交点在这种情况下,依据圆弧端点和射线的位置关系可以分为以下三种情况。第5期江平等射线法判断点与包含简单曲线多边形关系的完善2211)圆弧两个端点严格位于射线的同一方向,如图9,合前两节的各种情况,得到这样四条结论:10所示:1)当圆弧有一个端点严格位于射线上方,而另一个端点严格位于射线下方,射线与圆弧有一个交点。2)当圆弧两个端点同时位于射线的同一方向时,则射线与圆弧的交点都被忽略,计零个交点。3)当圆弧有且仅有一个端点被射线
8、穿过,如果圆弧的另一个端点在射线上方,则射线与圆弧的交点只能有一个被计数,如果圆弧的另一个端点在射线下方,则射线与圆2)圆弧有且仅有一个端点被射线穿过,如图11,12弧的交点都要被忽略,计零个交点。所示:4)当两个端点同时位于射线上,则射线与圆弧的交点都被忽略,计零个交点。41112结论证明针对31111节得出的四条结论,分别做出如下证明。证明1:当圆弧有一个端点严格位于射线之上,而另一个端点严格位于射线下方,显然圆弧与射线有且仅有一个交点。结论1得证。3)圆弧有两个
