（计算机应用技术专业论文）空间矢量数据的叠置算法研究.pdf

河南大学硕士研究生学位论文第1 页 摘要 空间分析是空间信息系统的核心和关键功能之一，也是评价一个空间信息系 统功能强弱的重要指标。叠置分析是空间分析的基本功能之一，也是众多空间分 析方法的基础。根据不同的数据模型可将叠置分析分为栅格叠置分析和矢量叠置 分析两种。栅格叠置分析较容易实现，但其精度往往不能满足用户的要求；与其 相反，矢量叠置能达到很高的精度，但需要处理大量的矢量空间数据。由于空间 数据量较大，常规算法难以满足用户对于时间的要求。因此，如何快速准确地完 成矢量叠置运算是空间分析中的关键技术之。 本文的主要工作如下： l 、线与多边形叠置，其核心算法是多边形对线的裁剪，即线裁剪。本文提出 一种适用于一般多边形的快速的线裁剪算法，该算法先利用快速排斥试验排除了 大量与被裁剪线段明显不相交的多边形窗口的边，然后利用多边形的边对被裁剪 线段的跨立试验进一步排除了不跨立被裁剪线段的边。从而减少了大量的不必要 的求交运算，提高了裁剪的速度。 2 、多边形与多边形叠置，其核心算法是多边形裁剪。w e i l e r - a t h e r t o n 算法是 经典的多边形裁剪算法，本文对之进行了改进。改进后的算法采用数组存储被裁 剪多边形和结果多边形的顶点，采用单链表存储裁剪多边形的顶点，简化了数据 结构，进而使得算法易于实现，并且具有更高的效率。 在多边形求交的过程中，引用本文提出的新的线裁剪算法，加快了多边形求 交速度，另外，在求得交点的同时获取了被裁剪多边形上构成结果多边形的边， 提高了结果多边形的生成速度。 3 、作为对所研究算法的实际工程应用测试，将其用于旱涝风灾害预防决策支 持系统，提高了矢量数据叠置分析的速度，满足了用户对时间的要求，为系统中 的其它分析提供了可靠依据，增强了决策系统空间分析的能力。 关键词：信息系统；空间分析；叠置分析；多边形叠置；矢量数据 第1 i 页河南大学硕士研究生学位论文 a b s t r a c t s p a t i a la n a l y s i si st h ec o r eo fs p a t i a li n f o r m a t i o ns y s t e ma n do n eo ft h ek e y f u n c t i o n so fs p a t i a li n f o r m a t i o ns y s t e m ，a n di sa l s oa ni m p o r t a n ti n d i c a t o rt oe v a l u a t e i t sf u n c t i o np e r f o r m a n c e o v e r l a ya n a l y s i si st h eb a s i sf o rm a n ys p a t i a la n a l y s i sm e t h o d s a n do n eo ft h eb a s i cf u n c t i o n so fs p a t i a la n a l y s i s a c c o r d i n gt od i f f e r e n td a t am o d e l s ，i t c a nb ed i v i d e di n t o 鲥do v e r l a ya n a l y s i sa n dv e c t o ro v e r l a ya n a l y s i s g r i do v e r l a y a n a l y s i sm o r ee a s i l ya c h i e v e d ，b u ti t sa c c u r a c yo f t e nc a l ln o tm o e tu s e rr e q u i r e m e n t s ； o nt h ec o n t r a r y , v e c t o ro v e r l a yc a na c h i e v eh i 曲a c c u r a c y , b u ti tn e e d st oh a n d l eal a r g e n u m b e ro fv e c t o rs p a t i a ld a t a b e c a u s eo fl a r g ea m o u n to fs p a t i a ld a t ai nt h i so p e r a t i o n , t h ec o n v e n t i o n a lm e t h o dc a nn o tm e e tt h er e q u i r e m e n t so fu s e r sf o rt h et i m e ；t h e r e f o r e ，i t i sc r i t i c a lt e c h n i q u eh o wt or e a l i z es p a t i a lo v e r l a ya n a l y s i sq u i c k l y 、析mh i g h e ra c c u r a c y t h em a i nw o r ko ft h i sp a p e ri sa sf o l l o w s ： f i r s t ，l i n ec l i p p i n ga l g o r i t h mi st h ec o r ea l g o r i t h mo fl i n e - i n p o l y g o no v e r l a y a n a l y s i s t h i sp a p e rp r o p o s e saf a s tl i n ec l i p p i n ga l g o r i t h mw h i c ha p p l i e st og e n e r a l p o l y g o n t h ea l g o r i t h me f f e c t i v e l yr u l eo u tt h ew i n d o w b o u n d a r i e st h a to b v i o u s l yd on o t i n t e r s e c tw i t ht h el i n eu n d e rt h eq u i c kr e j e c t i o nt e s t ，a n dt h e ne x c l u d et h ew i n d o w b o u n d a r i e st h a td on o ts t a n dt oc l i p p e dl i n ea c c o r d i n gt ot h et e s to ft h ep o l y g o na n dt h e l i n e t h u st h ea l g o r i t h mr e d u c e st h ea m o u n to fu n n e c e s s a r yi n t e r s e c t i o no p e r a t i o n ，a n d t h u si n c r e a s e st h es p e e do fc l i p p i n g s e c o n d ，p o l y g o nc l i p p i n gi st h ec o r ea l g o r i t h mo fp o l y g o n o n - p o l y g o no v e r l a y a c l a s s i c a lp o l y g o nd i p p i n ga l g o r i t h mi sw e i l e r - a t h e r t o na l g o r i t h mw h i c hw i l lb e i m p r o v e di nt h i sp a p e r a r r a y i su s e da st h ed a t as t r u c t u r et os t o r et h ev e r t e xo ft h e c l i p p e dp o l y g o na n dt h ei n t e r s e c t i o no fp o l y g o n ，a n ds i n g l yl i n k e dl i s ts t o r e st h ev e r t i c e s o ft h ec l i p p i n gp o l y g o ni nt h i sa l g o r i t h m t h ea l g o r i t h ms i m p l i f i e st h ed a t as t r u c t u r e ， m a k e si te a s yt oi m p l e m e n t ，a n dh a sh i g h e re f f i c i e n c y t h es p e e do ft h ep o l y g o ni n t e r s e c t i o ni nt h ea l g o r i t h mi sa c c e l e r a t e db yr e f e r e n c e t ot h en e wl i n ec l i p p i n ga l g o r i t h mi nt h ep r o c e s so fp o l y g o ni n t e r s e c t i o n i na d d i t i o n , t h e g e n e r a t e ds p e e do f t h ei n t e r s e c t i o no f p o l y g o ni si n c r e a s e db ya c c e s st ot h ee d g e sw h i c h i st h ee d g e so ft h ei n t e r s e c t i o no fp o l y g o ni nt h ec l i p p e dp o l y g o na tt h es a m et i m et h e i n t e r s e c t i o n 河南大学硕士研究生学位论文 第1 ii 页 t h i r d ，硒t h ea c t u a la p p l i c a t i o no ft h ea l g o r i t h mt e s t i n g , t h ea l g o r i t h mi sa p p l i e dt o t h e p r o j e c t “d r o u g h t s f l o o d w i n d s d i s a s t e rp r e v e n t i o nd e c i s i o n - m a k i n gs u p p o r t s y s t e m s , a n di m p r o v e s t h e s p e e d o fv e c t o rd a t ao v e r l a y a n a l y s i s ，m e e t s t h e r e q u i r e m e n t so fu s e r sf o rm et i m e ，a n de n h a n c e st h ec a p a c i t yo fs p a t i a la n a l y s i so f t h e s y s t e m k e y w o r d s ：i n f o r m a t i o ns y s t e m ；s p m i a la n a l y s i s ；o v e r l a ya n a l y s i s ；p o l y g o no v e r l a y ； v e c t o rd a t a 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。，：j ，i ? 。“。：豫磬+ i彬j 霉疆i ， 学位，哮请i - , 敬：蹲住论吏作者，签名。：至垫塑 g ：t ；j x ，蛳也，弘j i 囊j ：i ；i 蠢。j 熙，：；t 麓 j 箩。亳：_ 秀 警? 膨妻手歹，惫日 爹震。蠡爹兰黎妻二萎| | | i | 黎爱，曼甏 鬟关予学位论文著作权使用授权书，；霉 瓷泌“甏，娄秘毯，麓臻萼。龟爹 本人经河角大学审核批准授子硬，士喾住：作为学位论文的作者，本人完全 了解并同意河南大学有关保留。、7 使用学位论文的要求，即河南大学有权向国家 图书馆、科研信，、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公焱检索、奎阎，：；本入授权河赢犬学出于宣扬、展览学校 学术发展和进行学术交流等臂妁可泓采取影印，、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容番勺学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名：圭垫亟 2 q o 年6 琵f 箩a 学位做特撕箍巡 矾f o 年6a 莎日 河南大学硕士研究生学位论文第1 页 第1 章绪论 空间信息系统( s p a t i a li n f o r m a t i o ns y s t e m ，s i s ) 是地球空间信息科学的技术 系统，它是基于计算机技术与网络通信技术来解决与地球空间信息有关的数据的 获取、传输、存储、管理、分析和应用等问题的信息系统。而它的空间分析、预 测预报与辅助决策的能力，是其研究的核心。地理信息系统( g e o g r a p h i ci n f o r m a t i o n s y s t e m ，g i s ) 是指在计算机软硬件支持下，运用系统工程与信息科学的理论和方法， 综合地、动态地获取、传输、存储、管理、分析和利用地理信息的空间信息系统， 它是地理信息科学的技术系统。可以说g i s 是空间信息系统的典型代表1 1 5 。一般 在不造成混乱的情况下，g i s 和s i s 两个术语是可以互相代用。 1 1 研究背景和意义 空间分析是空间信息系统区别于一般信息系统、计算机地图制图系统与数据 库管理系统的主要功能特征，也是评价一个空间信息系统功能的主要指标之一憎1 。 空间分析是基于空间对象的位置和形态特征的空间数据的分析技术，其目的在于 提取和传输空间信息( 特别是空间隐含信息) 。利用空间分析技术通过对原始数据 模型观察与实验，用户可以获得新的经验与知识，并以此作为空间行为的决策依 据。空间分析在城市规划与管理、水污染监测、洪水灾害分析、地震灾害和损失 估计、矿产资源评价、地形地貌分析、道路交通管理和军事领域等领域都有广泛 应用“。1 。例如，可将地理信息与土壤、大气、噪声、水等环境要素的监测数据结 合在一起对区域环境质量现状进行评价，利用空间分析功能，对整个区域的环境 质量现状进行客观与全面的评价，以反映区域受污染的空间分布情况和污染程度。 可以预见，空间分析技术必将在构建和谐社会的过程中发挥越来越重要的作用。 叠置分析是一种重要的空间分析方法，也是众多空间分析方法的基础。叠置分析 是指将同一地区、同一比例尺的两组或多组专题图层进行叠置，产生一个具有多 重属性的新的数据层的操作，其属性综合了参与叠置的两层或者多层地图要素的 属性，从而满足用户的需求和协调决策的一种方法睁1 。例如，通过叠置分析，可 以提取某区域内的大气污染分布图和噪声分布图；将空间连续变化的雨量信息降 雨专题图和行政区划图叠置，可以得到各行政区划内的平均或者最大降雨量图； 将不同时间序列的海岸线图层进行叠置，可观察海岸线的沉陷、位置偏移等。 根据不同的数据模型可将空间叠置分为栅格叠置和矢量叠置两种钔。栅格叠置 第2 页河南大学硕士研究生学位论文 较容易实现，但其精度往往不能满足用户的要求；与其相反，矢量叠置能达到很 高的精度，但需要处理大量的矢量空间数据n 引。由于空间数据量较大，常规算法难 以满足用户对于时间的要求，因此，如何快速准确地完成矢量数据的叠置运算是 空间分析中的关键技术之一。 矢量数据的叠置分析有两步：几何求交与属性分配。几何求交过程是叠置分 析的关键，本课题主要对叠置分析的几何求交过程进行研究，并将研究结果应用 于旱涝风灾害预防决策支持系统中，使理论和实践有机的结合，在实践中验证理 论。 1 2 研究现状 空间分析的研究一直滞后于空间数据库与空间数据结构以及自动绘图技术和 地图数字化的研究，它是建立在对空间数据的有效管理之上的妇1 。特别是在2 0 世 纪9 0 年代以后，基于因特网技术和数据库技术的并行处理技术有了跨越式发展， 但空间分析在理论上和技术上都没有根本性的突破。由于空间分析在实际应用中 的重要作用，在1 9 9 8 年，美国u c g i s 把空间分析列为当前g i s 界十大重点问题 之一，而且将其作为当今世纪g i s 的1 9 个研究方向之一，主要包括空间数据的采 样和内插，空间统计学地理数据的空间统计分析，空间数据体系中地理边界及地 图比例尺的作用，g i s 数据结构与空间统计计算之间的关系等。 叠置分析是空间信息系统中使用非常频繁的一种空间分析方法，是非常有效 的提取空间隐含信息的工具之一。矢量数据的叠置分析分为：点与多边形的叠置、 线与多边形的叠置、多边形与多边形的叠置。 点与多边形的叠置实际上是计算多边形对点的包含关系，常用的方法是射线 法和转角法。 线与多边形的叠置的核心算法是多边形的线裁剪。目前，对于矩形窗口线裁 剪已经得到深入的研究，并且提出了许多有效的算法，如经典的c o h e n s u t h e r l a n d 算法n 钉，i 妇s p r o u l l 和s u t h e r l a n d 提出的便于硬件实现的中点分割法n 引，我国学者梁 友栋和b a r s k y 提出的参数方法 。对于凸多边形窗口线裁剪，一个著名算法是由 c y r u s 和b e c k 提出的n8 。该算法通过直线的方向矢量与窗口边内法矢量的内积来判 断线段是否可见。上述这些算法都不适用于凹多边形窗口线裁剪，对凹多边形窗 口的线裁剪目前还未出现公认的有效算法，但其意义很重要，有着广泛的应用前 景。在线与多边形的叠置分析中，由于地图数据中的多边形可能是凸多边形、凹 河南大学硕士研究生学位论文第3 页 多边形甚至有洞的多边形，所以，只有适用于一般多边形的线裁剪算法才在线与 多边形的叠置中具有使用价值。近年来，许多学者对此进行了研究并提出了一些 裁剪算法蚺1 。 多边形与多边形叠置的核心算法是多边形对多边形的裁剪。对于矩形多边形 的裁剪有几种有效的算法：s u t h e r l a n d h o d g e m a n t 3 。 , f o l e y 1 、梁- b a r k y b 、m a i l l o t b 引、 a n d e r e e v l 3 刮等。而在实际应用中，只有对于一般多边形裁剪才具有普遍意义，才更 实用。r e p p a p o r t ，m o n t a n i 和r e ，s e c h r e s t 和g r e e n g b e r g 等人提出了对于一般的多边 形的裁剪算法，以及近几年出现了一些改进算法b 洲1 ，其中有些算法还允许多边形 有洞。在这类算法中最有代表性的是w e i l e r - a t h e r t o n 算法h 5 1 、g r e i n e r - h o r m a n n 算法 m ，它们可在合理的时间内处理一般的情况。其中，w e i l e r - a t h e r t o n 算法使用树形 数据结构，而g r e i n e r - h o r m a n n 算法使用双线性链表数据结构。 1 3 论文的主要内容及组织结构 本文的主要研究内容有三部分： 1 、在分析和研究现有线裁剪算法的基础上，提出一种适用于一般多边形的快 速的线裁剪算法。此算法通过快速排斥试验和跨立试验排除了大量与被裁剪线段 不相交的裁剪多边形的边，减少了不必要求交运算，从而保证了算法的快速、高 效。 2 、对w e i l e r - a t h e r t o n 算法进行改进。改进算法采用数组存储被裁剪多边形和 结果多边形的顶点，采用单链表存储裁剪多边形的顶点，简化了数据结构。在多 边形求交的过程中，引用上面提出的新的线裁剪算法，加快了多边形求交速度， 另外，在求得交点的同时获取了被裁剪多边形上构成结果多边形的边，提高了结 果多边形的生成速度。 3 、将提出的线裁剪算法和改进的多边形裁剪算法应用于旱涝风灾害预防决策 支持系统中，实现叠置分析功能。 论文的组织结构如下： 第一章，主要介绍了论文研究的背景和意义、研究现状以及研究内容。 第二章，本文所涉及到相关基础知识进行介绍。 第三章，提出一种适用于一般多边形的快速的线裁剪算法。首先分析算法的 思想，然后讲述算法的实现过程，概括了该算法实现过程中的特殊情况，并给出 了解决方法。最后，进行算法分析比较及仿真实验。 第4 页河南大学硕士研究生学位论文 第四章，主要讲述改进算法的数据结构、主要思想、结果多边形生成、以及 算法分析与比较。 第五章，介绍本文研究内容的实例应用旱涝风灾害预防决策支持系统。 介绍了系统的设计和主要功能，详细阐述了本文所研究的矢量叠置算法在该系统 中的应用。 最后，对本文的主要工作进行了总结，并对下一步的工作进行了展望。 河南大学硕士研究生学位论文第5 页 第2 章叠置分析相关概念和算法 叠置分析是空间信息系统中常用的一种空f 叫分析方法是非常有效的提取空 间隐含信息的工具之一。本章将介绍空间数据的表示、空间分析的基本方法、计 算几何的基础算法和叠置分析的研究内容。 21 空间数据的表示 空间数据的表示，就是指把以图形模拟的空间物体表示成计算机所能接受的 数字形式。空间数据的内容包括空间实体的位置、非几何属性、时间特征及其之 间的关系。计算机对于空间数据内容的描述，主要差别在于对空间实体的位置及 其关系的表达上，对于非几何属性的记录，一般采用关系表的形式。 对空间实体的位置及其关系的描述，计算机采用显式和隐式两种形式”。显式 表示就是通过给栅格中的像元一定的编码、数值、颜色或符号来表示空间实体的 位置和其关系。隐式表示就是用一些坐标点或给定了起点和终点的线或某种连接 关系的矢量柬描述。从数据结构的角度，般称显式描述为棚格数据结构，隐式 描述成为矢量数据结构。 栅格数据结构是一种简单、直观的空间数据结构，又称网格结构或象元结构。 它是指把地表面划分为大小均匀、紧密相邻的网格阵列，每个网格作为一个像素 或像元，由行列号定义”。该网格包含一个代码，表示其属性值或指向其属性记录 的指针。因此，栅格数据结构就是用规则的阵列表示空间宴体和现象分布的数据 组织形式，栅格中的数据表示的是空间实体和现象的非几何属性。 图2 - l 点、线、面数据和其栅格表示 在栅格结构中，点、线、面数据的表示如图2 1 所示。一个栅格单元可表示一 个点，线是用沿着其走向的标记其属性的一组相邻的栅格单元来表示；面是用标 汜有面属性的栅格单元的集合表示的。 一熏 !；萋 第6 页河南大学硕士研究生学位论文 另一种很常见的空间数据结构是矢量数据结构。它是通过记录空间数据的坐 标的方式来精确的表示点、线、多边形等空间实体，坐标空间设为连续的，可允 许任意长度、位置、面积的精确定义。实际应用中，其精度受数字化设备的精度 及数值记录字长的限制。 矢量数据的空间位置信息是用坐标表示的，点用一对x 、y 坐标表示，线是用 一组有序的x 、y 坐标表示，面用一组首位相同的坐标表示。矢量数据的属性信息 存放在属性表中。同一个空间实体的空间位置信息和属性信息是通过唯一的标识 码关联起来的。如图2 2 所示，其中图( a ) 是道路图，图( b ) 是道路的空间坐标，图( c ) 是道路的属性信息。从图2 2 中可见：同一空间实体的坐标表示和属性表示之间共 享的是同一标识码。 标识码x , y 坐标对 ( a ) 道路图( b ) 道路的坐标 ( c ) 道路的属性 图2 - 2 空间实体及其坐标表示和属性表示 2 2 空间分析 空间分析是基于空间对象的位置和形态特征的空间数据分析技术他1 。它是从一 个或多个空间数据图层中获取信息( 特别是隐含信息) 的过程。空间分析的内涵 极为丰富，这里从空间查询、空间量测、叠置分析、缓冲区分析、网络分析、空 间统计分类分析等几个方面，简单介绍空间分析的基本方法叶1 。 1 空间查询 空间查询主要有两种类型：第一种是通过属性信息查询空间位置，也即是通 过s q l 在属性数据库中查询对象，然后根据查询结果，再利用图形与属性的对应 河南大学硕士研究生学位论文第7 页 关系，在地图数据库中找到该对象，并在地图上用指定的显示方式将结果显示出 来。第二种是根据对象的空间位置查询其属性信息。这种查询通常分为两步，首 先借助空间索引，在图形数据库中检索出被选中的空间实体，然后再根据空间实 体与属性的连接关系查询属性数据库，找到该空间实体的相关属性信息。 2 空间量测 对线状地物求长度、方向、曲率；对面状地物求面积、周长、曲率、形状等； 求几何体的质心；空间实体之间的距离等。 3 叠置分析 叠置分析是将两层或多层地图要素进行叠置产生一个新的要素层的操作，其 结果是将原来的要素通过分割或合并等生成新的要素，新要素综合了原来两层或 多层要素所具有的属性叠置分析不仅包含空间关系的比较，还包含属性关系的比 较。常见的有：点与多边形叠置、线与多边形叠置、多边形与多边形叠置。 4 缓冲区分析 缓冲区分析是对点、线、面实体自动建立其周围指定宽度范围以内的缓冲区 多边形。缓冲区的产生分为点目标的缓冲区，线目标的缓冲区和面目标的缓冲区 三种情况。 5 网络分析 在s i s 中，网络分析的主要目的是对于基础设施网络( 如供排水管线、各种网 线等) 、地理网络( 如交通网络、河网等) 进行地理分析和模型化。研究和筹划一项 工程如何安排才能达到最好的运行效果是网络分析的根本目的，如两地运输的费 用最低、资源的最佳分配等。其基本思想是人类活动总是趋向于按照一定的目标 选择来达到最佳效果的空间位置。网络分析主要的分析方法有：资源分配、路径 分析、地址匹配。 6 空间统计分类分析 空间统计分类分析主要用于综合评价和数据分类两个方面。数据分类在大多 数情况下的操作方法是，先将未分类处理的数据输入信息系统数据库中，再按用 户给定的分类算法，获得所需要的信息。分类评价中常用方法有：判别分析、层 次分析、聚类分析、主成分分析。 2 3 计算几何算法基础 s i s 已经发展成为个具有独特的理论体系与方法的学科，同时它也是一个综 第8 页河南大学硕士研究生学位论文 合性的边缘学科。除了地理相关学科以外，s i s 的研究与实践也借鉴了计算机图形 学、计算几何、数据挖掘技术、计算机视觉、数据库技术等多个领域的学科的知 识、方法与成果，同时s i s 的发展也推动了这些学科的研究与实践，使其在解决 新的难题中不断发展。 计算几何是计算机理论科学的一个重要分支。自2 0 世纪7 0 年代末从算法设 计与分析中独立出来起，该学科已经有了巨大的发展，产生了一系列重要的理论 成果，并在地理数据库、计算机图形学、统计分析和其他许多领域中得到了广泛 的应用1 。 2 3 1 点与直线段的位置 设平面内有只( 而，y 。) ，最( x ：，y ：) 两点，判断另一点只( x ，y ，) 相对于直线段p i p 2 的位置，即点在直线段的左侧、右侧或者是直线段所在的直线上。矢量的叉积 鼻曼e b 是一个标量，其符合反映了两矢量之间的顺逆时针关系，如图2 3 所示， 叉积公式见公式( 2 1 ) 。 如 图2 - 3 点与直线段的位置 c = 再巧i 巧= ( x 2 一x 。) 魄一m ) 一( 黾一而) 执一乃) ( 2 - 1 ) 按右手法则可知： i c 0 p 3 点位于线段p i p 22 礅 a c 0 厶c 木f 0 i 缸幸鲋= 0 2 3 2 判断两直线段是否相交 两点在线段p ，p 2 的同侧 两点在线段p i p 。的异侧( 2 4 ) 至少有一点在直线p - p 2 上 分两步来确定两条直线段是否相交： 1 ：快速排斥试验 快速排斥试验就是判断各条线段的最小外包矩形( m i n i m u mb o u n d i n g r e c t a n g l e ，m b r ) 之间是否相交。线段的m b r 是指以线段的两端点为对角线的 矩形，如图2 5 所示。 尸 ( a ) 末通过快速排斥试验( b ) 通过快速排斥试验 图2 - 5 快速排斥试验 如果m b r 不相交，则两条线段肯定不相交，如图2 - 5 ( a ) 所示：如果相交，如 图2 - 5 ( b ) 所示，则还需再进行跨立试验才能确定两线段是否相交。 有两条线段l i 、l 2 ，l l 的两端点为只( 五，y ，) 和b ( x 2 ，y 2 ) ，l 2 的两端点为 第1 0 页河南大学硕士研究生学位论文 只( x 3 ，y 3 ) 和只( ，y 4 ) ，判断它们的m b r 是否相交。 设 而m 。= m a x ( x 1 ，x 2 ) ，m 麟= m a x ( y l ，奶) 五岫= m i n ( x 1 ，x 2 ) ，乃m j n = m m ( y l ，y 2 ， x 2 m 料= m a x ( x 3 ，x 4 ) ，儿姻= m a x ( y 3 ，y 4 ) ( 2 - 5 ) 屯m i i l = m i n ( x 3 ，) ，y 2 曲= m i n ( y 3 ，y 4 ) 若西m 戥 屯。i 。或乃一 y 2 。i n 或x 2 m 戤 j c l m i n 或y 2 m 娃 - 0 ( 2 。6 ) 同理判断q ，q ：跨立1 1 p 2 的依据是： 河南大学硕士研究生学位论文第1 1 页 ( q 。- p 1 ) ( p 2 - p i ) ( p 2 一p 1 ) ( q ：一p ；) = 0 ( 2 7 ) 在实际应用中，一般是选择至少有一个端点在对方的m b r 内的线段来进行 判断，如图2 - 6 所示，判断线段q ，q ：的端点q l 、q 2 是否跨立线段e p 2 ，而不是判 断线段e p 的端点p l 、p 2 是否跨立线段q ，q ：。如果此试验成功，则两线段相交， 否则线段不相交。 2 3 3 两直线段的交点 设有两直线段s 和最，s 的两个端点为毋( 毛，y 1 ) 和昱( 而，儿) ，& 的两个端点 为只( 黾，y 3 ) 和e , ( x 4 ，y 4 ) ，其中而x 2 , y 1 y 2 ，x 3 x 4 ，y 3 y 4 ，根据两点式公式： 世：三1 ( 2 8 、) 乃一咒恐一五 得到两直线段所在直线的方程为： 等：墨 p 9 ， 其中 ia 1 = y 2 一y 1 ，b 1 = 五一x 2 ，c 1 = x 2 y l x l y 2 【a 2 = y 4 一y 3 ，b 2 = 工3 一礼，c 22x , s y 3 一x 3 y 4 ( 1 ) 当a ，b ：= a ：b ，时，两条直线平行或重合。 当b 。b ，b ，c ，时，两条直线平行，没有交点。 当b ，c ，= b ，c ，时，两条直线重合。 ( 2 ) 当a ，b 2 a 2 8 1 时，两条直线相交。 两直线的交点为： x ：刍鱼二垒刍 予宝：一呼刍 ( 2 1 0 ) 、，- 生刍二鱼刍 卜 。 4 b ：一4 骂 判断交点( x ，y ) 是否在直线段s 和s 上，若在这两条直线段上，则该交点是直 线段s 和s ，的真实交点，否则这两条直线段不相交。 2 4 叠置分析的研究内容 叠置分析是空间信息系统中使用非常频繁的一种空间分析技术。依据数据结 构，地图叠置有栅格叠置和矢量叠置两种类型的操作。栅格叠置就是一个简单的 在每个地图像素上的布尔算术操作；矢量叠置是通过几何运算来求得叠置结果。 矢量叠置一般有点与多边形叠置、线与多边形叠置和多边形与多边形叠置三类。 栅格叠置容易实现，但其精度往往不能满足用户要求；与之相反，矢量数据能达 到很高的精度，但需处理大量矢量空间数据引。由于空间数据量较大，常规的算法 第1 2 页河南大学硕士研究生学位论文 不能满足用户对时间的要求。因此，如何快速的完成矢量数据的叠置运算是s i s 空 间分析中的关键技术之一。 2 4 1 栅格地图叠置 栅格地图的叠置，有时也称为栅格数据的信息复合。它是指不同图层的栅格数 据逐个网格的按一定逻辑判断或者数学法则进行运算，从而获得新的栅格数据图 层的方法1 6 1 。其主要有两种类型：算术运算和函数运算。 算术运算方法是指两层以上的对应网格值经加、减运算得到新的栅格图层的方 法。这种复合分析法的应用范围很大。图2 7 给出了栅格数据的算术运算的示例。 a l i t 1 b l l 1 l ， 1 l l l l 1 l 1 t t l c 弘狙一b | f f f i d - e 图2 - 7 栅格数据的算术运算 函数运算是指两个以上栅格图层以某种函数关系作为复合分析的依据逐个网 格进行运算，从而获得新的栅格图层的方法。这种复合叠置分析方法在遥感数字 图像处理、环境质量评价、地学综合分析等领域被广泛地应用。 2 4 2 矢量地图叠置 矢量叠置分析涉及到点、线、多边形分别于多边形叠置m 1 ，下面分别介绍它们 的基本思想及方法。 1 、点与多边形叠置 点与多边形叠置就将一个点图层叠置到一个多边形图层上，以确定每个点落在 哪个多边形中，如图2 8 所示。点与多边形的叠置是通过点在多边形内的判别完成 河南大学硕士研究生学位论文第1 3 页 的，通常得到一张新属性表如图2 8 ( f ) 所示。该属性表除了点图层原有的属性外， 还含有点所落在的那个多边形的属性。 ( a ) 点图层 ( c ) 多边形图层 p o i n t l d p o i n tn a m e 测站1 测站2 测站3 测站4 ( b ) 图( a ) 的属性表 ( d ) 图( b ) 的属性表 n e wo l dp o i n t p o l y l dp o l y p o i n t i d p o i n t i dn a m en a m e 11 测站i 1a 22测站22b 33测站32b 44测站44d ( e ) 点层叠置上多边形层( f ) 叠置后生成的新的属性表 图2 8 点与多边形的叠置 判定点是否在多边形内的算法主要有两种：射线法和转角法。 ( 1 ) 射线法 射线法就是由所需要判断的点向某个方向作一条射线，然后计算该射线与多 边形的交点，根据交点的个数确定点是在多边形区域内还是在区域外n 3 ，如图2 9 所示。若交点个数是奇数，则该点在区域内，若为偶数，则在区域外。 ( 2 ) 转角法 转角法就是由需判断的点与多边形中的任意一顶点的连线开始，逐个遍历多 边形中的其他顶点，分别进行角度计算并叠加，连线旋转到起点结束1 。如果角度 的总和是3 6 0 。，则该点在多边形内，若总和是0 。，则在多边形外( 如图2 1 0 所示) 。 完成点与多边形几何关系的计算后，还要进行属性信息的处理。最简单的方 第1 4 页河南大学硕士研究生学位论文 式是把多边形的属性信息叠加到其中的点上，然后通过查询新的属性，获得点与 多边形叠置的需要信息。例如将一个全国矿产分布图( 点集) 和一个中国行政区域图 ( 多边形) 叠置，并且将行政区域图有关的属性加到矿产属性数据表中，然后通过查 询新的属性表，可以得到指定省份有哪些矿产、产量有多少等，而且还可查询某 类矿产分布在哪些省里等信息。 ， 图2 9 射线法 鼍。咖l 图2 1 0 转角法 2 、线与多边形叠置 线与多边形叠置和点与多边形叠置类似，就是将线图层叠置在多边形图层上， 以确定每条线落在哪个多边形内。与点与多边形叠置不同的是，一个线目标往往 跨越多个多边形，因此，需先进行线和多边形边界的求交，并根据交点将线目标 进行切割，形成一个新的线目标的图层，并生产新图层的属性表。该属性表包含 了原来线目标的属性和多边形的属性。如图2 1 1 所示线状目标1 与多边形b 、c 的边 河南大学硕士研究生学位论文第15 页 界相交，因而它被切成两个目标。建立新的线目标的属性表，包含原来线状目标 的属性和被叠置的面状目标的属性。 图2 1 1 线与多边形的叠置 线与多边形叠置，是比较线上坐标和多边形坐标的关系，判断线是否在多边 形区域内。其中，线与多边形交点的计算是算法的关键，只要相交，就产生结点， 这些结点将原线打断成若干条子线段。子线段的属性信息是原线段和多边形的属 性信息的综合。叠置的结果产生了一个新的线目标的图层，同时产生一个相应的 属性表。根据叠置的结果可确定每条子线段落在哪个多边形区域内，可查询指定 多边形区域内的指定线段穿过的长度。如果线状目标为河流，叠置的结果可以查 询任意多边形区域内的河流长度，进而计算其河流密度等；如果线状目标为道路， 叠置的结果可得到每个多边形区域内的公路里程、内部交通流量、进入或者离开 各个区域的交通量以及相邻区域之间的相互交通量等。 3 、多边形与多边形叠置 多边形与多边形叠置比前面两种叠置要复杂得多。它需要计算出两个图层的多 边形边界的全部交点，并以此交点将原叠置多边形要素分割成新的多边形要素。 新要素综合了原来两层多边形要素的属性。可以把多边形叠置归结为多边形与多 边形的交、并、差的问题。 2 5 本章小结 本章首先简要介绍了空间数据的表示方法、空间分析的基本方法；然后详细介 第1 6 页河南大学硕士研究生学位论文 绍了基础的计算几何算法，如判断点与直线段的位置关系、判断两直线段是否相 交及两直线段的交点计算；最后分别介绍了栅格和矢量叠置分析的内容，为后几 章做理论基础。 河南大学硕士研究生学位论文第1 7 页 第3 章线与多边形叠置算法研究 线与多边形叠置，是比较线上坐标和多边形坐标的关系，判断线是否在多边 形区域内。线与多边形叠置的核心算法是多边形的线裁剪。本章将先对两种典型 的线裁剪算法进行分析，并提出一种适用于一般多边形的快速的线裁剪算法；然 后进行算法的分析比较及仿真实验。新算法利用快速排斥试验和跨立试验，排除 了大量不与被裁剪线段相交的多边形窗口的边，从而极大的减少了复杂的求交运 算，保证了算法的快速、高效。其中，快速排斥试验和跨立试验是计算几何中判 断两直线段是否相交的有效的算法，本文2 3 2 节有介绍。需要说明的是本文所说 的一般多边形是指凸多边形、凹多边形或带洞的多边形，不包括边自相交的多边 形。 3 1 两种典型的线裁剪算法 l 、c y r u s b e c k s g 法 设一个凸多边形区域s 有n 条边，v i 是每条边上取定的点，n i 是s 边界上在v i 处 的内法矢量，被裁剪线段为p l p 2 ，线段p l p 2 的参数方程为 p ( r ) = 互+ ( 一异) 掌f( 0 ，1 ) 对于暑只上的任一点尸( f ) 有： 哆【尸o ) 一v 】 0 点尸o ) 在s 内 = 0 点尸( f ) 在s 边界上 0 ，为下限组，d 0 ，为上限 组。然后求出上限组里的最小值f u 和下限组里的最大值吒，则从p ( 吒) 至p ( 乞) 的线 段位于窗口内，是可见线段。 由于c y r u s b e c k 算法是根据直线段的方向矢量和窗口的边法矢量的点积的符 第1 8 页河南大学硕士研究生学位论文 号而将所有的交点分为上下两组。然后，分别取上组的最小交点和下组的最大交 点，即是线