（运筹学与控制论专业论文）gis中基于空间物体的缓冲区构建技术研究.pdf

山东科技大学硕士学位论文摘要 摘要 本文是针对当前缓冲区分析的研究现状，在吸取三维计算机图形学、计算几何、地 理信息系统、o p e n g l 等的先进理论和技术成果的基础上，对空间目标的缓冲区构建算 法进行了研究和探讨。 在分析了已有的缓冲区生成算法后，本文提出了一种基于凸角圆弧法和目标的拓扑 空间关系的快速的缓冲区自动生成算法。它解决了角平分线法的不等宽性问题，也回避 了凸角圆弧法的失真现象，以统一的形式实现了缓冲区边界的自动生成。该算法不仅可 以对任意点、线、面以及复合目标求缓冲区，而且还可以对目标本身自交，目标内含有 若干孔洞的情况求缓冲区。在对复合目标的缓冲区重叠合并过程中，对多边形的交、并 作了改进。它是基于计算几何和集合的基本理论，可以解决任意两多边形交、并的一种 矢量算法。同时本文还提出一种改进的扫描线填充算法，它是基于从下到上，从左到右 的思想进行填充，可以对任意图形( 包括含有孑l 洞的复杂边界图形) 进行填充。 本文还提出一种基于三维空间物体的缓冲区构建算法，该算法主要是借助于目标的 拓扑空问关系、缓冲区上的特殊点以及对三角形面片和四边形面片剖分算法来生成目标 的三维缓冲区。详细论述了点，线，面和凸体的三维缓冲区生成过程。最后，本文介绍 了利用o p e n g l 实现缓冲区的三维空间动态浏览和真实感图形绘制。 关键词：地理信息系统，三维缓冲区，凸角圆弧法，拓扑空间关系，填充算法 剖分，o p e n g l 山东科技大学硕士学位论文 摘要 a b s t r a c t b a s e do nt h ep r e s e n tr e s e a r c ho nb u f f e ra n a l y s i s ，t h i sp a p e rm a i n l ys t u d i e st h ea l g o r i t h m o fb u f f e rz o n e sg e n e r a t i o nf o rs p a c eo b j e c t s t h e s es t u d i e sa r eb a s e do nt h ea d v a n c e dt h e o r i e s a n dt e c h n i c a la c h i e v e m e n t so fs o m e i n t e r d i s c i p l i n e s u c ha s3 d c o m p u t e rg r a p h i c s ， c o m p u t a t i o n a lg e o m e t r y , g e o g r a p h i c a li n f o r m a t i o ns y s t e m ( g i s ) a n do p e n g l w i t he x i s t i n ga l g o r i t h m so fb u f f e rz o n eg e n e r a t i o na s s e s s e d ，t h ep a p e rp r o p o s e san e w a l g o r i t h mo fa u t o m a t i cb u f f e rz o n ec r e a t i o nb a s e do nm e t h o do fc i r c u l a ra r c f o rc o n v e x v e r t e xa n dt o p o l o g i cs p a c er e l a t i o n s h i p so fo b j e c t s t h ea l g o r i t h ms o l v e st h ep r o b l e mo f u n e q u a lw i d t hc a u s e db ym e t h o do fa n g u l a rb i s e c t r i xa n da v o i d st h ed i s t o r t i o np r o b l e m c a u s e db ym e t h o do fc i r c u l a ra r cf o rc o f l v e xv e r t e x i tn o to n l yc a ng e n e r a t eb u f f e rz o n e sf o r p o i n t ，l i n e ，p l a n es u r f a c ea n dc o m p o u n do b j e c t s ，b u ta l s oc a ng e n e r a t eb u f f e rz o n e sf o rt h e s p e c i a lo b j e c t sw i t hs e l f - i n t e r s e c t i n ga n dc o n m i n i n gs e v e r a lh o l e s i nt h ep r o c e s so fm e r g i n g o v e r l a pb u f f e rz o n e sf o rc o m p o u n do b j e c t s ，a ne f f i c i e n t v e c t o ra l g o r i t h mo fg e t t i n gt h e i n t e r s e c t i o ns e ta n du n i o ns e to ft w oc o m p l e x p o l y g o n si sp r o p o s e d ，w h i c hi sb a s e do n c o m p u t a t i o n a lg e o m e t r ya n ds e tt h e o r y a tt h es a l d _ et i m e ，a ni m p r o v e df i l l i n ga l g o r i t h mo f s c a n n i n gl i n ei sp u tf o r w a r di nt h ep a p e r ，b a s e do n s u c hi d e aa s , f r o md o w nt ou p ，f r o ml e f tt o r i g h t t h em e t h o dc a nf i l la n yg r a p h ，i n c l u d i n gt h ec o m p l i c a t e db o u n d a r yg r a p hw i t hs e v e r a l h o l e s aa l g o r i t h mo f3 db u f f e rz o n e s , g e n e r a t i o nf o rs p a c eo b j e c t si sp r e s e n t e di nt h ep a p e r t h ea l g o r i t h mi sb a s e do nt h et o p o l o g i cs p a c er e l a t i o n s h i p so fo b j e c t s ，t h es p e c i a lp o i n t so f f b u f f e rz o n ea n ds u b d i v i s i o nm e t h o do ft r i a n g u l a rf a c e t sa n dr e c t a n g u l a rf a c e t st og e n e r a t e3 d b u f f e r t h ep r o c e s s e so f3 db u f f e rc r e a t i o nf o rp o i n t ，l i n e ，f a c ea n dc o n v e xp o l y h e d r o na r e i n t r o d u c e di nd e t a i li nt h ep a p e r a tl a s t ，t h ep a p e ri n t r o d u c e sd y n a m i c a le x p l o r i n ga n d r e a l i s t i ci m a g ed r a w i n gt e c h n o l o g yo f3 db u f f e ru s i n go p e n g l k e y w o r d s ：g e o g r a p h i c a li n f o r m a t i o ns y s t e m ( g i s ) ，3 db u f f e rz o n e ，m e t h o do f c i r c u l a ra r cf o rc o n v e xv e r t e x ，t o p o l o g i c s p a c er e l a t i o n s h i p ，f i l l i n ga l g o r i t h m ， s u b d i v i s i o n ，o p e n g l 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交 于其它任何学术机关作鉴定。 硕士生签名： 日期： a f f 工r m a t l 0 n 浩毙率 渺咕t0 f o 1d e c l a r et h a tt h i sd i s s e r 七a 七i o n ，s u b m i t t e di n f u lf il l m e n to ft h e r e q u i r e m e n t sf o rt h ea w a r do fm a s t e ro fs c i e n c ei ns h a n d o n gu n i v e r s i t y o fs c i e n c ea n dt e c h n o l o g y ，i sw h o l ym yo w l w o r ku n l e s sr e f e r e n c e do f a c k n o w l e d g e t h ed o c u m e n th a sn o tb e e ns u b m i t t e df o rq u a i f i c a t i o na t a n yo t h e ra c a d e m i ci n s t i t u t e s i g n a t u r e 两峒 d a t e ：溉，i o 山东科技大学硕士学位论文 绪论 1 绪论 1 1 缓冲区问题的提出及意义 缓冲区分析是地理信息系统中使用非常频繁的一种空间分析，是对空间特征进行度 量的一种重要方法。单个要素的缓冲区是指距该要素的距离小于等于给定缓冲区半径 的点的集合；复合要素的缓冲区则是单个要素缓冲区的并。在地图与地理信息系统 ( g e o g r a p h i c a lo fi n f o r m a t i o ns y s t e m ，简称g i s ) 信息处理中缓冲区的确定是一个重要手 段。交通沿线或河流沿岸的地物有其独特的重要性，公共设施( 商场、邮局、影院、银 行、医院、汽车站) 的服务半径，大型水库建设所引起的搬迁，铁路、公路以及航行河 道对其所穿越区域经济发展的重要性等，均是一个缓冲区问题。对此我们可作的归纳： 缓冲区是地理目标或工程规划项目的一种影响范围或服务范围( 临近度问题) ，是地图信 息检索与综合处理和g i s 空间分析的重要功能。缓冲区信息处理在现实生活中有广泛的 应用 2 】： ( 1 ) 在环境与生态保护中的应用：在公路穿越地区，噪音与废气是重要的污染源， 其中废气对森林生态的危害随着林块远离公路而减弱；飞机场跑道区域的噪音污染引起 对附近居民的赔偿。在林业方面，木材的砍伐被限制在距河流一定的范围之内。在对野 生动物栖息地的评价中，许多动物生活区域距它们生存所需要的水源或栖息地的距离都 在一定的范围之内。在土地评价中，要根据离开交通线或繁华区的远近，进行地价估算 等。在地震带，要按断层线的危险等级，确定沿其两侧不同宽度的地带作为警戒区。 ( 2 ) 在规划和决策中的应用：在道路规划中所涉及的地形带，地下管线铺设时的施 工地带，微波通信山头站之问的断面条形地带，这些地带地区中的有关地理与专题信息 是规戈与决策的重要依据。此外，综合考虑多种因素是景观规划时的重要手段，例如， 公园和疗养地的选址是辗转实施诸如“靠近交通线”、“沿河流或濒临湖泊”、“包含林块 和绿地”等有关缓冲区操作的综合决策。 ( 3 ) 在地理数据结构化自动处理中的应用：地图与地理信息处理的实质是综合性分 析与评价，借此赋以地理实体相应的重要性，为管理与规划决策提供依据和为它们的多 比例显示奠定基础。然后，地图的地理信息的综合评价必须在信息结构化的基础上进行， 对于简单的数字化面条数据是难以进行有效的分析和处理的。例如，河网树结构，地形 1 堂墨燮奎兰堡主兰堡堡茎 堕塑 线( 山脊线与谷底线) 的结构化( 树结构的自动建立) 都在递归地执行缓冲区操作。边 防城镇、沿海港e l 和地形等信息有其独特的不言而喻的重要性，这些都是借助缓冲区操 作而实现的。 综上所述，缓冲区分析在现实生活中有如此广泛的应用，所以，对缓冲区算法的研 究非常的有必要。 1 2 缓冲区问题的研究现状 根据物体对周围空间作用性质的不同，一般分为静态缓冲区分析和动态缓冲区分析2 种类型嘲。静态缓冲区是指空间物体与邻近对象只呈单一的距离关系，缓冲区内各点地 位相等，其所受影响度并不随距离空间物体的远近而有所改变。例如，工业区选址时。 为减少水质污染必须远离某一湖泊2 k m ，则为此湖泊建立一个宽度为2 k m 的缓冲区，在 此缓冲区内的各点都不能作为工业区地址。动态缓冲区是指空间物体对邻近对象的影响 度随距离变化而呈不同强度的扩散或衰减。例如，要分析某一湖泊周围农田的灌溉便捷 度，就需要对此湖泊建立动态缓冲区，缓冲区内与空间物体距离不同的地方，灌溉便捷 度不同，离湖泊越远，便捷度越差。 动态缓冲区生成是针对两类特殊情况提出的：一类是流域问题，另一类是污染问题 ”j 。在流域问题中，从流域上游的某一点出发沿流域下溯，河流的影响半径或流域辐射 范围逐渐扩大；而从流域下游的某一点出发沿流域上溯，河流的影响半径或流域辐射范 围逐渐减小，类似问题还有参数动态变化的运动目标之影响范围分析。在污染问题中， 污染源对邻近对象的影响程度随距离的增大而逐渐缩小，类似问题还有城市辐射影响分 析、矿山开采影响分析等。 。 对于流域问题，可以基于线目标的缓冲区生成算法，采用分段处理的办法分别生成 各流域分段的缓冲区，然后按慕种规则将各分段缓冲区光滑连接；也可以基于点目标的 缓冲区生成算法，采用逐点处理的办法分别生成沿线各点的缓冲圆，然后求出缓冲圆序 列的两两外切线，所有外切线相连即形成流域问题的动态缓冲区。 针对污染问题，黄杏元等根据物体对周围空间影响度的变化性质，分别给出了以下 三种动态缓冲区分析模型”】： ( 1 ) 物体对周围空间的影响度耳随距离r 呈线性式衰减( 图1 1 ) ( 1 ) 物体对周围空间的影响度e 随距离r 呈线性式衰减( 图1 1 ) 山东科技大学硕士学位论文 篇搿 【0 i i ( 2 ) 物体对周围空间的影响度e 随距离r 呈二次形式衰减( 图1 2 ) e 例= f o ( 1 - r 。f r l o s 1 ( 3 ) 物体对周围空间的影响度日随距离r 呈指数形式衰减( 图1 3 ) f = ，0 1 。 1r 。= 邓d i i d ，o 图1 1 线性衰减模式 f i g l1 l i n e a rd e c a ym o d e l i 【】_ 0 图1 2 二次衰减模式 f i 9 1 2q u a d r i cd e c a ym o d e l 图1 3 指数衰减模式 f i 9 1 3e x p o n e n t i a ld e c a ym o d e l ( 1 2 ) ( 1 3 ) 以上各式中，如为参与缓冲区分析的一维空间实体的综合规模指数，一般需经最大值标 准化后参与运算；d o 表示该物体的最大影响距离；西表示在该物体最大影响距离内的某 点距该物体的实际距离。 按照以上公式，将所设定的各点的正带人以上各式，可算出各等距离带内的值e ， 但这些值具有不可预测性，故按d 。建立缓冲区内的属性值是否满足用户的需求难以控 3 坐查鲨拦堡主兰焦垒茎 堕堡 制。据此，黄杏元建议作某种变换。 d i ：d n ( 1 一些) ( 1 4 ) 。 m 矗 这样，便可根据需要来设定e 的值，再由e 的值求得相应的d ，根据d 。建立的缓冲 区内的属性值便与事先设定的需求值相一致。 静态缓冲区的生成有栅格和矢量两种基本算法。栅格方法又叫点阵法，它将点、线、 面矢量数据转化为栅格数据，进行像元加粗，然后作边缘提取；在原理上较简单，容易 实现，但受精度的限制；并且内存开销大，所能处理的数据量受到机器硬件设备的限制。 而矢量方法原理复杂，不易实现，但在机器精度范围内不降低原始精度嘲 坨1 。缓冲区生 成的矢量算法，特别是线缓冲区的生成算法，在文献中常见的矢量方法是角平分线法和 凸角圆弧法，角平分线法由画逐个线段的简单平行线，尖角光滑矫正和自相交处理三步 构成。角平分线法的缺点是难以最大限度的保证平行曲线的等宽性，由于异常情况多， 矫正过程复杂，不易完备的实现 2 1 。缓冲区生成的另一个直观的矢量算法是凸角圆弧法， 是逐个求得每个线段单独的缓冲区，然后用多边形叠置算法依次合并。算法所生成的缓 冲区边界，轴线转角尖锐的转折点的平行线交点随缓冲距的增大将会迅速远离轴线，这 就会出现尖角和凹陷的失真现象嘲。而且失真现象有十多种，每一种的补救程序都比较 复杂。 不管是静态缓冲区还是动态缓冲区，都不可能是孤立存在的，经常有多个空间物体 的缓冲区相互重叠 7 1 。一方面，同一影响度等级的缓冲区可能存在重叠；另一方面，动 态缓冲区不同影响度等级的缓冲区也可能存在重叠。这就要求对两个或多个、同一影响 度等级或不同影响度等级的重叠缓冲区进行合并。对于栅格数据格式，把缓冲区内的栅 格赋上一个与其影响度值唯一对应的值。若两重叠缓冲区具有相同的影响度，则取任一 值，若影响度值不同，则影响度小的服从影响度大的，对于矢量数据格式，有多种算法 1 1 1 ： 1 ) 数学运算法 矢量数据格式的缓冲区多边形均由边界弧段组成，由于缓冲区重叠，缓冲区多边形 的边界线段必然相交，求它们的最直观的方法就是进行所有多边形的所有边界线段之间 两两求交运算，生成所有可能的多边形，再根据多边形之间的拓扑关系和属性关系，去 除某些多余的多边形，这种数学运算法计算量大，效率低。并且由于存在不同影响度等 级，如果分开合并，则合并后不同影响度等级之间还可能存在重叠；若统一合并，则不 山东科技大学硕士学位论文 同影响度等级的缓冲区可能被合并在一起，所以这种方法很难解决问题。 2 ) 矢栅转换法 考虑到矢量数据格式的缓冲区合并比较困难，栅格数据格式的缓冲区合并比较容易， 而矢量栅格两种数据结构之间转换的理论基础比较完善，于是想到先把矢量数据格式转 换成栅格数据格式，合并缓冲区后，再把栅格的合并结果转换成矢量数据格式。在进行 缓冲区生成之前，开一块存放栅格矩阵的内存，将其所有成员赋值为零，生成缓冲区后， 给缓冲区内的每个栅格赋上与缓冲区影响度唯一对应的值，若有不同影响度的缓冲区重 叠，贝0 影响度小的服从影响度大的，然后，应用栅格数据转矢量数据的算法分别提取各 影响等级的缓冲区边界。这种矢栅转换法原理比较简单，但是经过两次数据转换，精 度低，造成缓冲区变形大。 3 ) 混合算法 对矢量数据进行数学运算结果比较精确，但运算量大；采用栅格法精度又太低，如 果把这两种算法结合起来，各取所长，可以得到一种比较合理的算法。这里把各等级缓 冲区分开合并把缓冲区的矢量数据转换成栅格数据，形成合并后的含有多个等级的动态 缓冲区，再对各个等级缓冲区的栅格边界分别进行扫描，在扫描过程中，提取扫描线上 缓冲区边界的矢量数据，也就是提取所有构成最后缓冲区多边形的必要线段，然后再对 它们进行求交运算，这样所有的数学运算都是必要的、有效的，并且是基于矢量的算法， 结果也比较精确。 但迄今为止，各种g i s 软件中提供的缓冲区分析功能均是建立在平面上的，有关文 献中介绍的缓冲区构建技术也毫无例外的均是基于平面的，通常是在某一给定的投影平 面上构建。尽管这种基于平面的缓冲区可以满足大多数应用要求，但随着g i s 应用的日 趋广泛与深入，我们会发现它的使用是有条件的，一旦超越给定的条件，将得不到准确 地分析结果，这一点必须引起g i s 用户的足够重视。 1 3 1 论文的内容 1 3 论文的内容和结构安排 本论文是针对当前缓冲区分析的研究现状，在吸取三维计算机图形学、计算几何、 地理信息系统、o p e n g l 等的先进理论和技术成果的基础上，对空间目标的缓冲区构建 些查型苎盔兰堡主兰些笙苎 堑堕 算法进行了研究和探讨。本文所作的主要工作： ( 1 ) 提出了一种基于凸角圆弧法和目标的拓扑空间关系的快速的缓冲区自动生成算法； ( 2 ) 在对复合目标的缓冲区重叠合并过程中，对多边形的交、并作了改进； ( 3 ) 提出一种改进的扫描线填充算法； ( 4 ) 对特殊目标如：目标自交、目标内部含有若干孔洞的情况求缓冲区； ( 5 ) 借助于目标的拓扑空间关系、缓冲区上的特殊点以及对三角形面片和四边形面片剖 分算法来生成点、线、面、凸体的三维缓冲区； ( 6 ) 利用o p e n g l 实现缓冲区的三维空间动态浏览和真实感图形绘制。 1 3 2 论文的结构安排 论文共分六部分： ( 1 ) 绪论，提出研究课题； ( 2 ) 介绍本论文所涉及到的一些基本图形算法； ( 3 ) 提出了一种基于凸角圆弧法和目标的拓扑空间关系的快速的缓冲区自动生成算法； ( 4 ) 详细介绍了在三维空间中，点、线、面、凸体目标的缓冲区生成算法； ( 5 ) 利用o p e n g l 实现缓冲区的三维空间动态浏览和真实感图形绘制； ( 6 ) 进行总结与展望。 6 山东科技大学硕士学位论文基本图形算法 2 基本图形算法 在本课题中，将用到大量的图形计算，本章就简单介绍一下常用的基本图形算法。 本文对部分算法( 如多边形的并、交、差运算) 作了一些改进，以便提高效率，减少空 间占用。 2 1 两点间方向角的计算 若已知两点只( ，y 。) 和p 2 ( x 2 ，y ：) ，点b 相对于点只的方向角口( 号最的连线与水平 线的夹角) 为： 口= a r c c o s 掣 o 口万 ( 2 1 ) 或口= 2 z r a r c c o s 掣 石口2 石 ( 2 2 ) d 其中为d 两点间的距离：d = ( 恐一玉) 2 + ( _ ) ，2 一y 1 ) 2 由于a r c c o s 函数返回的值甜在0 石之间，而两点间的方向角的取值范围在0 2 万之 间，所以当方向角在万一2 石之间时( y ：一y l o ) ，由( 2 2 ) 式计算。 2 2 1 两直线段的交点 2 2 交点计算 设有两直线段s 和是，s ，的两个端点为最( ，y 。) 和p 2 ( x 2 ，y 2 ) ，& 的两个端点为 ( 而，y 3 ) 和只( ，y 4 ) ，根据两点式公式： 羔二! ! = 兰二玉 y 2 一) t lx 2 一 得两直线方程为： 鼢4 x + 聃b i y + g g = 兰其中协撒麓：箍三篙麓 ( 1 ) 当a 1 8 2 = a 2 8 1 ，两条直线段平行或重合，不再进行求交计算； 山东科技大学硕士学位论文 基本图形算法 cz ，当a b ：如b ，得两直线的交点为1 b i c 2 - b 2 q ：，显然如果两条直线段相交的 2 2 2 直线段与圆弧的交点 ( x - - x o ( x 一屯) 0 ( 工一而) ( x 一矗) 0 ( y y z ) ( ) ，一y 2 ) 0 ( y y 3 ) ( y y 4 ) 0 ( 2 3 ) 设给定的直线段的两个端点为只( ，咒) 和b ( 毛，y z ) ，圆弧给定的是圆一0 , p o ( x o ，y o ) ， 半径r ，起始角只，终止角岛，且岛 0 时( 即d r ) d l t = 讲f fh = ( 一，+ d l t ) 1 2 ei = ( 一，一d l t ) 2 e 【y a = 一( 础。+ c c )【y b = 一( a a x + c c ) 当d l t = 0 时( 即d = ，) 8 默= 一c a ，d l t = r 2 - ( x x x o ) 2 12 捌12 x x l y a = ) b + d n【y b = y o d l t j 矗2 x x l y a = y o 并求出它们的圆心角幺和岛。如果直线段和圆弧有交点，则应该满足点既在直线段 l ( h 一 ) ( 一x 2 ) 0f ( 一玉) ( 一鼍) 茎0 ( y a m ) ( ) i 一y 2 ) 0 和 ( y 口一m ) ( y 口一y 2 ) 0 【鼋 以 易【日 岛 岛 2 2 3 两圆弧的交点 设有两段圆弧a 和b ，圆弧a 的圆心坐标为( x a ，y a ) ，半径为，起止角q ，终止角， 圆弧b 的圆心坐标为( ，y 。) ，半径为白，起止角届，终止角屈。设两圆心之间的距离为 d = ( h x b ) 2 + ( ) ， 一y b ) 2 ，贝0 ( 1 ) 当d = 0 时，两圆心重合； ( 2 ) 当d = r + 时，两圆相外切； ( 3 ) 当d = i _ 一l 时， 两圆相内切； ( 4 ) 当i ，：i 一i d + 白时，两圆相离。 如果两圆相交或相切，求出两个交点p a ( x a ，y a ) 和b ( 如，y 。) ，并且求出各交点的圆 帆耗卢满足镶黥扣表h 月是两圆弧的斌 9 山东科技大学硕士学位论文 基本图形算法 2 3 1 点的包含性检验 2 3 关系判别 点的包含性检验是指：判断一个点是否包含在某一个区域内，在这里我们把这个区 域定义为一个多边形0 1 。 任意给定点p 和平面多边形q ，它们之间的关系可以通过射线法求交点数来进行判 定。即过点p 作水平射线l ，如果f 与q 的边界不相交，则p 在q 的外部；否则f 与q 的 边界相交，计算交点数并依据交点数的奇偶性可以判定点p 是否在q 的内部，具体地说， 当射线与多边形q 的交点个数为偶数时，则点p 在q 外，因为只要存在一进人多边形内 的交点，就同时存在一离开多边形的交点。若交点数是奇数，则表明进入多边形的交点 数小于离开多边形的交点数，因而点p 在q 内。如图2 1 中( a ) 有一个交点。( b ) 有三个交 点。这两种情况均表明点在多边形内部。 ( a ) ( d ) ( c ) 岛 图2 1 几种特殊情况 f i 9 2 1s e v e r a lp e c u l i a rc o n d i t i o n s 一岛 一种特殊情况是多边形的顶点或边在水平射线上，对于这种情况，解决方法是从点p 出发依次向四个方向作射线并进行判断，如果四个方向上所作的射线均有特殊情况发生， 1 0 坐查燮查兰堡圭兰垡堕壅苎查望丝茎望 则将点p 平移- - b 段距离，再作射线，只要点p 不移人或移出多边形，也就是说，不改 变点p 的属性( 在多边形的外部或内部) 即可。对于( c ) ( d ) 这两种情况，射线刚好穿过多 边形q 的一个顶点，这时可以依次向其它三个方向作射线，我们可以看到，对于( c ) 来说， 作射线f 】发现有一个交点，表明点在多边形内部；对于( d ) ，作射线发现无交点，则说 明点不在多边形内部。对于情况( e ) 这种情况，判定射线f 与多边形边重合后，可以依次 向其它三个方向作射线，1 2 ，1 3 ，发现均为特殊情况，这时将点p 向下平移一小段距离 作射线，与多边形有一个交点，说明点在多边形内部。 2 3 2 判断两线段是否相交的方法 此设 有两条线段l l ( p 1 ，p 2 ) ，l 2 ( p 。，风) ，欲求它们的交点，需要先判断它们是否相交，为 x 1 一= m a x ( p 1 x ，p 2 x ) ，y 1 。= r n 丑 x ( p 1 y ，p 2 y ) x 2 z = = m a x ( p 3 工p 4 曲，y 2 。= m a x ( p 3 y ，碑y ) x 1 i = m i n ( p 1 x ，p 2 z ) ，y 1 一= m i n ( p l ，y ，p 2 y ) x 2 “。= m i n ( p 3 x ，p 4 x ) ，y 2 m = m i n ( p 3 y ，p 4 y ) 若x 1 一 x 2 。或y l 。