（计算机应用技术专业论文）gis缓冲区和叠加分析.pdf

摘要 空间分析是地理信息系统的核心和关键功能之一。随着空间信息 及其处理能力极大丰富和加强，要求增强g i s 空间分析能力的呼声越 来越高，论文主要对空间分析中叠加分析和缓冲区分析两类重要方法 进行研究。 缓冲区分析是g i s 一种重要的空间操作。缓冲区生成分为点、线 和面三种类型，其中线目标的缓冲区生成是关键和基础，线目标的缓 冲区生成分为单个线目标的缓冲区独立生成和所有线目标的缓冲区 重叠合并两个阶段。在缓冲区分析角平分线算法和凸角圆弧算法基础 上，本文提出并实现一种新的缓冲区半径旋转生成算法。另外，新算 法对缓冲区生成过程中出现的特殊情况进行了处理，并采用递归方法 管理和存储缓冲区边界的自相交多边形。 叠加分析是g i s 进行空间分析时常用的一种空间操作，包括点、 线和多边形分别与多边形叠加三种类型。由于空间数据量较大，如何 快速准确地完成空间叠加分析运算是比较关键的技术。在叠加分析 w e i l e r 算法和g r e i n e r - h o r m a r m 算法基础上，本文提出并实现一种快速 的多边形叠加分析优化算法，其中多边形既可是简单多边形，也可是 复杂多边形。改进算法使用单线性链表数据结构来组织叠加后的多边 形，减少了遍历多边形顶点链表的次数，并有效减少求取交点的时间， 具有占用存储空间少和处理速度快的特点。另外，在求取交点前引入 预处理操作，避免了大量不必要的求交运算，降低了算法的时间复杂 度。 关键词地理信息系统，空间分析，缓冲区分析，叠加分析，算法 a b s t r a c t s p a t i a la n a l y s i si so n eo fs e v e r a li m p o r t a n tf u n c t i o n si ng e o g r a p h i c a l i n f o r m a t i o ns y s t e m ( g i s ) w i t ht h ee n r i c h m e n to fs p a t i a ld a t aa n dt h e i m p r o v e m e n to fc a p a b i l i t yt od e a lw i t ht h e m ，p e o p l er e q u e s tb e t t e rs p a t i a l a n a l y s i sm e t h o d s t h i sp a p e rm a i n l yd o e ss o m er e s e a r c h e so no v e r l a y a n a l y s i sa n db u f f e ra n a l y s i sw h i c ha l ei m p o r t a n ti ns p a t i a la n a l y s i s b u f f e ra n a l y s i si so n eo ft h es e v e r a li m p o r t a n ts p a t i a l a n a l y s i s f u n c t i o n so fg i s b u f f e rc r e a t i o nc a nb ed i v i d e di n t ot h r e et y p e s ：f o r p o i n t s ，l i n e sa n dp o l y g o n s ，t h eb u f f e rc r e a t i o nf o rl i n e si st h ek e ya n d b a s i s t h ep r o c e d u r eo ft h eb u f r e rc r e a t i o nf o rl i n e si sd i v i d e di n t ot w o s t e p s ：i n d e p e n d e n t l yc r e a t i n gt h eb u f f e rf o re a c hl i n e sa n dm e r g i n gt h e b u f f e r sc r e a t e di nt h ep r e v i o u ss t e p t h i sp a p e rp r e s e n t sa n dr e a l i z e sa n e wk i n do fb u f f e rr a d i u s - r o t a t i o nc r e a t i o na l g o r i t h mb a s e do na n g u l a r b i s e c t r i xa l g o r i t h ma n dc i r c u l a ra r ca l g o r i t h m i na d d i t i o n ，s o m es p e c i f i c c a s e s a r er e s o l v e dd u r i n gt h ep r o c e d u r eo ft h eb u f f e rc r e a t i o n ，a n d r e c u r s i o nm e t h o di sa d o p t e dt om a n a g ea n ds t o r et h es e l f - i n t e r s e c t e d p o l y g o n so f t h eb u f f e r sb o r d e r l i n e o v e r l a ya n a l y s i si saw i d e l yu s e ds p a t i a lo p e r a t i o nf o rt h en e e d so f s p a t i a la n a l y s i si ng i s 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 s o p e r a t i o n i ti sac r i t i c a lt e c h n i q u ea b o u th o wt or e a l i z es p a t i a lo v e r l a y a n a l y s i sv e r yq u i c k l yw i t hh i g h e ra c c u r a c y i nt h i sp a p e r , ak i n do f c o r r e s p o n d i n go p t i m a la l g o r i t h m f o r p o l y g o no v e r l a y w h i c hc a l l p r o c e s s e ss i m p l ep o l y g o na n dc o m p l e xp o l y g o no nt h eb a s i so fw e i l e r a l g o r i t h ma n dg r e i n e r - h o r m a r ma l g o r i t h mi sp r e s e n t e da n dr e a l i z e d t h i s a l g o r i t h mr e d u c e st h et i m e st h a tt h e v e r t e xl i s t sa r et r a v e r s e da n d c o n s u m e dt i m eo fc o m p u t i n gi n t e r s e c t i o np o i n t ，i nw h i c ht h e s i n g l y l i n k e dl i s t sa st h ed a t as t r u c t u r ei su s e dt or e s t r u c t u r et h er e s u l tp o l y g o n s ， s ol e s sm e m o r ys p a c ea n dr u n n i n gt i m ea r er e q u i r e d i no r d e rt oa v o i d u n n e c e s s a r yi n t e r s e c t i n go p e r a t i o n ，t h ej u d g e m e n ti sa d o p t e db e f o r e c o m p u t e r i n gi n t e r s e c t i o np o i n ta n d i tr e d u c e st h et i m ec o m p l e x i t y k e yw o r d s g i s ，s p a t i a la n a l y s i s ，b u f f e ra n a l y s i s ，o v e r l a ya n a l y s i s ， a l g o r i t h m u 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特另1 1 ；1 1 以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：型日期：之年兰月兰e t 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：趔导师签名：星勉日期：业旦月生日 中南大学硕士学位论文第章绪论 第一章绪论 地理信息系统( o l s ) 是采集、存储、管理、检索、分析和描述整个或部分 地球表面与空间地理分布数据的空间信息系统1 1 】。空间分析是g i s 的核心和关键 功能之一，随着地理信息系统的不断发展，对空间数据结构的研究也日趋成熟， 空间分析也相应成为人们倍加关注的热点。 1 1 研究内容和重要意义 地理信息系统具有强大的空间分析功能，这是区别于计算机地图制图系统 和数据库管理系统的显著特征之一。利用空间分析技术，通过对原始数据模型 的观察和实验，用户可以获得新的经验和知识，并以此作为空间行为的决策依 据。关于空间分析，r o b e r t 曾给出如下定义：“空间分析是基于地理对象的空 间布局的地理数据分析技术。”；郭仁忠定义为：“所谓空间分析，在现代g i s 领域就是利用计算机对数字地图进行分析，从而获取和传输空间信息【2 】。” 空间分析在水污染监测、城市规划与管理、地震灾害和损失估计、洪水灾 害分析、矿产资源评价、道路交通管理、地形地貌分析和军事领域等领域都有 广泛应用 3 - - 9 1 。例如，在区域环境质量现状评价工作中，可将地理信息与大气、 土壤、水、噪声等环境要素的监测数据结合在一起，利用g i s 软件的空间分析 模块，对整个区域的环境质量现状进行客观和全面的评价，以反映出区域受污 染的程度以及空间分布情况。随着空间分析技术的发展，许多研究工作者都在 各个领域探求增强空间分析功能的各种方法。本论文主要对g i s 空间分析中缓 冲区分析和叠加分析两类重要分析方法迸行研究，缓冲区分析 l o i 是指为了识别 某地理实体或空问物体对其周围的邻近性或影响度而在其周围建立的一定宽度 的带状区。叠加分析【1 0 1 是将两层或多层地图要素进行叠加产生一个新要素层的 操作，其结果是将原来要素分割生成新的要素，新要素综合了原来两层或多层 要素所具有的属性。可以预见，在构建和谐社会的过程中，g i s 和空间分析技 术必将发挥越来越广泛和深刻的作用。例如，通过缓冲区分析，可显示污染源 影响范围；在海岸线、河道和水库周围建立缓冲区，可对缓冲区内社会经济信 息、抢险救灾信息及水利设施信息等要素进行统计，估算缓冲区面积，为抢险 救灾决策提供辅助手段；民宅区远离街道网络的缓冲区的建立；林业规划中按 照距河流一定纵深范围的森林砍伐区的规划等。通过叠加分析，可以提取某区 中南大学硕士学位论文第一章绪论 域内大气污染分布图或噪声分布图；将跨空间连续变化的雨量信息的降雨专题 图与行政区划图叠加，可以形成各行政区划内的平均或最大降雨量图；将不同 时间序列的海岸线图层进行叠加，可观察海岸线的沉陷、位置偏移等。 作为空间分析的两类重要分析方法，缓冲区分析和叠加分析在许多领域均 有应用，但在实际应用过程中均还存在一些不足，仍需改进和完善，因此对这 两种分析方法做进一步研究是非常必要的。缓冲区分析的主要算法是角平分线 算法和凸角圆弧算法，它们在生成缓冲时都有欠缺，特别在处理缓冲区边界的 自相交问题时存在一些不足。叠加分析算法的核心是如何快速有效地完成多边 形求交运算，算法主要通过拓扑数据结构和简单数据结构两种数据模型来表示 多边形图层，而这两种数据模型均存在一些缺点。 本文的研究课题是地理信息系统缓冲区和叠加分析，研究内容主要包括以 下四个部分： 1 、寻找一种新的且更有效的表示多边形图层的数据结构，以提高多边形求 交的速度和效率； 2 、在缓冲区分析角平分线算法和凸角圆弧算法基础上，本文提出并实现一 种新的缓冲区生成算法，特别对角平分线和凸角圆弧算法在处理缓冲区边界的 自相交问题时存在的一些不足进行改进； 3 、在叠加分析w e i l e r 算法和g r e i n e r h o r m a n n 算法基础上，本文提出并实 现一种既适用于简单多边形叠加，也适用于复杂多边形叠加的改进算法，以简 化多边形叠加的流程； 4 、实现叠加分析和缓冲区分析两类重要空间分析功能，并对所提出的新的 数据结构及算法进行验证。 1 2 关键技术及研究现状 古往今来，几乎人类的所有活动都是发生在地球之上，都与地球表面位置 ( 即地理空间位置) 相关，同时计算机技术也日益发展和普及，所以地理信息 系统在人们的生产和生活之中起着越来越重要的作用。据专家估计，在我们经 济建设和日常生活活动所涉及的信息中，8 0 与地理信息密切相关。因此，地 理信息系统被公认为是2 1 世纪的支柱性产业，是信息产业的重要组成部分。近 些年来，随着技术的进步，g i s 在经济建设和人们生活中的重要性日益凸显。 2 中南大学硕士学位论文第一章绪论 1 2 1 空间分析发展与展望 地理信息系统起源于2 0 世纪6 0 年代的加拿大森林管理系统，主要功能是空间 及其属性数据的存储和查询检索。1 9 8 9 年美国成立国家地理信息分析中心，1 9 9 6 年由美国国家科学基金会正式以“地理信息科学”为目标立项开展研究。m o r a a 首次引出空间自相关测度以研究二维或更高维空间随机分布的现象；m a t h e r o n 先后提出了地统计和硒g i n g 技术【1 1 , 1 2 , 1 3 1 ，成为当今地统计学的核心内容；2 0 世纪 7 0 、8 0 年代，空间统计理论体系出现雏形，以c l i f f & o r d 的专著s p a t i a lp r o c e s s ： m o d e l sa n da p p l i c a t i o n s 为主要标志；2 0 世纪8 0 、9 0 年代，当今空间分析的主要理 论趋向成熟，包括s a r 、m a 和c a r 模型，聚焦于空间异质性的局域统计g e t i s g 和l i s a 的出现：空间分析软件的出现，包括与g i s 结合的可视化交互空间数据探 索，s p a c e s t a t ，a r c v i e w - s p l u ss s 和s a g e 等。国外在地球信息科学方面的推动 者主要来源于2 0 世纪6 0 、7 0 年代期间计量地理革命的活跃学者，如老一辈的 t o b l e r 、m a r b l e 、c l i f f h a g g e 仕和中年辈的g o o d c h i l d 、r h i n d 、h a i n i n g 、f i m h e r 、 o p e n s h a w 、b a t t y 、f o t b r i n g l m 等。从2 0 世纪9 0 年代至今，在g i s 技术和海量观 测数据大发展的背景下，具有实际运用价值的地球信息科学理论和方法雏形正在 形成。中国并没有广泛地经历上世纪中叶的计量地理革命，但是中国学者在理论 方面正在作不懈的努力和推动，如陈述彭先生提出地球信息科学和地球信息机理 ( 1 9 9 2 年) 、地球信息图谱( 1 9 9 6 年) 、格网计算( 2 0 0 3 年) 等重要概念：中国 学者学习引进了计量地理、空间信息分析技术、元胞自动机、智能计算等方法； 在空间抽样模型、新型数据结构等多方面的理论成果正在被国际同行引用；国家 自然科学基金委员会和8 6 3 计划资助了空间信息分析领域的研究和交流活动。 作为地理信息系统的核心，随着空间信息及其处理能力极大丰富和加强，要 求增强g i s 的空间分析能力的呼声越来越高，人们渴望利用这些空间信息来认识 和把握地球与社会的空间运动规律，进行虚拟、科学预测和调控，许多研究工作 者都在各个领域探求增强g i s 空问分析功能的多种方法【m 1 7 1 。随着空间分析技术 的不断发展，地理信息系统必将向着能够提供丰富和全面的空间分析功能的智能 型g i s 方向发展。 1 2 2 缓冲区分析基本算法 缓冲区分析是地理信息系统重要和基本的空间操作功能之一。它是在给定空 间实体( 集合) 周围建立一定距离( 缓冲半径) 的带状区( 缓冲区多边形) ，以 确定这些物体对周围环境的影响范围或服务范围( 邻近度问题) 。 中南大学硕士学位论文第一章绪论 对不同类型的目标实体，所产生的缓冲区也不同。如图1 1 所示，点的缓冲 区通常是以点为圆心，一定距离为半径的圆，见图1 - 1 ( a ) ；线的缓冲区通常是以 线为中心轴线，距中心轴线一定距离的平行条带多边形，见图l - 1 ( b ) ：面缓冲区 是由面的边界多边形向外或向内扩展一定距离所生成的新的多边形，见图l - l ( c ) 。 其中线目标的缓冲区的生成是关键和基础。 o ( a ) 点的缓冲区( b ) 线的缓冲区( c ) 面的缓冲区 图1 1 三种目标的缓冲区生成结果 缓冲区的生成有栅格和矢量两种基本方法。栅格方法又叫点阵法，它将点、 线和面矢量数据转化为栅格数据，进行像元加粗，然后作边缘提取；在原理上较 简单，容易实现，但受精度的限制；并且内存开销大，所能处理的数据量受到机 器硬件设备的限制【l ”。而矢量方法原理复杂，不易实现，但在机器精度范围内不 降低原始精度1 1 9 】。在缓冲区生成的矢量算法中，常用的是角平分线算法和凸角圆 弧算法，在此基础上也出现了一些新的或改进算法【2 删。 1 、角平分线算法 角平分线算法是一种以线目标为轴线，并分别在其两侧作距轴线一定距离 ( 缓冲半径) 的平行线来生成缓冲区边界的简便方法，但此法产生异常情况较多。 ( 1 ) 算法原理 在轴线首末点处，作轴线的垂线并按缓冲区半径e 截出左右边界的起迄点； 在轴线的其它各个拐点上，用与该点所关联的前后两邻边距轴线的偏移量为e 的 两平行线的交点来生成两平行边界的对应顶点。因此，该方法也称“简单平行线 法”。 ( 2 ) 角平分线法的缺点 a 难以最大限度地保证缓冲区边界线的等宽性。在尖锐转角处，凸侧生成 的缓冲点将随着角度的进一步变锐而沿角平分线远离轴线顶点。根据图1 2 ，远 离情况可表示为d = e s i n ( b 2 ) ，此式表明，当偏移量e 不变时，d 随着张角b 的减 小而增大，因而在尖角处平行线之间的宽度遭到破坏。 4 中南大学硕士学位论文第一章绪论 图j - 2 角平分线算法的缓冲区生成 b 校正过程复杂。为克服角平分线算法的缺点，文献【2 5 l 曾进行了深刻的分 折与研究，并提出了许多判别方案，较好地解决了所出现的异常情况。 露算法模型欠结构化。算法模型应包括平行线的几何生成和异常情况处理。 首先，几何生成算法欠合理，而大部分异常情况正是由于算法欠合理引起的。由 于异常情况不胜枚举，因而校正措施必然繁杂，模型的逻辑构思不易做到条理清 晰，从而难以实现结构化。 2 、凸角圆弧算法 凸角圆弧算法在一定程度上解决了角平分线算法产生的异常问题，但是此算 法生成缓冲区边界过程相对复杂。 ( 1 ) 算法原理 在钝线首末点处，作轴线的垂线并按缓冲区半宽e 截出左右边界的起迄点； 在轴线的其它各个拐点上，首先判断该点的凹凸特性，在凸侧用圆弧弥合，而在 凹侧用与该点所关联的前后两邻边距轴线的偏移量为e 的两平行线的交点来生成 对应顶点( 图i - 3 ) 。由于在凸侧用圆弧弥合，使凸侧平行边界与轴线等宽。而 在凹侧。平行边界相交在角平分线上。如图l _ 4 所示，交点距轴对应顶点的距离 d = e 怕s ( a ，1 2 ) 或d = f s i n ( b 2 ) 。由此可见，该算法能最大限度地保证平行曲线 的等宽性，排除了角平分线算法所带来的众多的异常情况。 图1 3 凸角圆弧算法原理图1 4 凹侧双线宽度与曲线弯曲程度的关系 ( 2 ) 主要实施步骤 中南丈学硕+ 学位论文第一章绪论 a 直线性判断。对于相邻三点作直线性判断。用以简化计算过程，特别是 当出现相邻三点处于近似共线状态时，可用简化计算过程来代替平行线的求交运 算和圆弧连接等。 b 折点凹凸性的判断。轴线顶点处的凹凸特性的判断是非常重要的一环， 因为它能确保何处需要用圆弧连接和何处需要用直线求交。这个问题可转化为两 个矢量的叉积，即把相邻两个线段看成两个矢量，中间点为所需判定凹凸的顶点， 其方向取为坐标点顺序方向。若前一个矢量以最小的角度扫向第二个矢量时呈逆 时针，则为凸顶点。反之，为凹顶点。 c 圆弧的嵌入。圆弧上布点的多少，取决于计算步长( 以角度计) 。步长y 由近似表示缓冲区的正n 边形的边数决定( ，= 2 n ) 。 d 左、右侧缓冲区边界的生成与自相交问题处理。以矢量数据格式表示的 曲线是具有方向性的，最自然的方式就是取曲线坐标串的方向为曲线前进方向。 当缓冲区边界的生成基线( 轴线) 被取定方向后，其两侧的平行曲线也就自然地 获得其左右属性。根据边界与轴线的关系，可为各条边界的两侧赋以内侧与外侧 属性。朝向轴线的一侧取为内侧，背向轴线的一侧取为外侧。当轴线的弯衄空间 不能容许缓冲区边界通过时，产生边界的自相交问题，形成若干个自相交多边形， 自相交多边形分为岛屿多边形与重叠区多边形两种类型( 如图1 5 所示) 。当轴 线方向为顺时针方向时，对于左边界，岛屿多边形呈逆时针方向，重叠多边形呈 顺时针方向；对于右边界，岛屿多边形呈顺时针方向，重叠区多边形呈逆时针方 向。岛屿多边形是缓冲区边界的有效组成部分，而重叠多边形不是缓冲区边界的 有效组成部分，不参于缓冲区有效边界的最终重构。 图1 - 5 线的缓冲区边界自相交多边形 由缓冲区多边形边界自相交所产生的自相交多边形的个数是难以确定的，同 时会随着缓冲半径的不同而发生变化。对于产生的这些自相交多边形，凸角圆弧 算法仅给出了通过封闭多边形的顶点点序方向( 顺时针或逆时针) 判断其为岛屿 多边形还是重叠多边形的识别方法，但未给出这些自相交多边形的生成方法，也 没有提供特定的数据结构来很好地组织和管理缓冲区结果多边形。 6 中南大学硕士学位论文 第一章绪论 1 2 3 叠加分析基本算法 叠加分析是地理信息系统最常用的提取空间隐含信息的手段之一。地理信息 系统的叠加分析是将同一地区、同比例尺的两组或更多的专题图层进行叠加， 建立具有多重地理属性的空间分布区域，进行叠加产生一个新的数据层的操作， 其结果综合了原来两层或多层地图要素所具有的属性，从而满足用户需求和协同 决策的一种方法。它不同于通常所说的视觉信息复合，这主要是因为叠加分析的 结果不仅产生视觉效果，更主要的是形成新的目标，对空问数据的区域进行了重 新划分，属性数据中包含了参加叠加的多种数据项。根据不同的数据模型可将空 间叠加分为栅格叠加和矢量叠加两种。栅格叠加比较容易实现，但精度往往不能 满足用户的要求：而矢量叠加与其相反，它能达到很高的精度，但是需要处理大 量的矢量空间数据。由于空间数据量较大，常规的算法难以满足用户对时间的要 求，必须进行特殊的处理。因此，如何快速高效地完成叠加运算是g i s 空间分析 中的关键技术之一。 从图形学的角度，多边形与多边形( 或线) 韵叠加算法的核心是多边形对多 边形( 或线) 的裁剪。在图形系统中，二维裁剪是最为基础和常用的操作之一。 其典型的应用是在图形的消隐等各种三维图形的处理以及各种排料算法的求交 操作之中。对裁剪算法的研究主要集中在裁剪直线和裁剪多边形两方面。多边形 裁剪与线剪裁相比具有更高的使用率，因此它是目前裁剪研究的主要课题。多边 形裁剪用于裁剪掉被裁剪多边形( 又称为实体多边形) 位于窗口( 又称为裁剪多 边形) 之外的部分。多边形愈复杂，其裁剪算法就愈难以实现。现有的解决方案 或者局限于某一类多边形，或者结构复杂且时间消耗大。对于特殊情况已有几种 有效的算法，如s u t h e r l a n d - h o d g e m a n 、粱b a r s k y 、f o l e y 、m a i u o t 、a n d e r e e v 等 算法要求裁剪多边形是矩形。而在实际应用中，只有对于一般多边形的裁剪才有 普遍意义，且更实用。m o n t a n i 和r e 、r e p p a p o r t 以及s e e h r e s t 和g r e e n g b e r g 等人曾 提出过对于一般多边形的裁剪算法，以及近年来出现的一些改进算法 2 6 - 3 6 1 ，其 中有些算法允许多边形具有孔洞。在这类算法中最具有代表性有w e i l e r 算法口7 l 和近年出现的v a t t i 算法 3 8 1 及g r e i n e r - h o r m a n n 算法p 9 】，它们可以在合理的时问内 处理一般的情况。其中，w e i l e r 算法使用的是树形数据结构，适用于任意多边形 的裁剪，但计算量大，内存开销大，影响计算机的工作效率：而v a t t i 算法和 g r e i n e r - h o r m a n n 算法使用的是双线性链表数据结构，所以后两者在复杂性及运 行速度方面均优于前者。 s u t h c r l a n d - h o d g e m a n 算法和w e i l e r 算法是叠加分析中两类典型方法，以下分 别介绍它们实现多边形叠加的基本思想。 7 中南大学硕七学位论文第一章绪论 l 、s u t h e r l a n d h o d g e m a n 算法 s u t h e r l a n d h o d g e m a n 多边形裁剪算法采用分割处理的策略，将多边形关于矩 形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪，所以该算法也称为逐 边裁剪算法。多边形关于窗口四边的裁剪是相继进行的，不妨假定裁剪顺序为左 边、上边、右边和下边，那么原多边形关于窗口左边的裁剪结果多边形可作为关 于上边裁剪的输入多边形，关于上边的裁剪结果多边形可作为关于右边裁剪的输 入多边形，依次类推，裁剪过程是一个流水线过程。图1 6 ( a ) 所示，待裁剪多边 形为v o v ，v 2 u ，经窗1 2 1 左边裁剪后，结果多边形v o v 1 v 2 v 3 。v 4 ，见图- 6 ( b ) 。该 多边形又作为关于窗口上边裁剪的输入多边形，裁剪结果为v o ”v 1 ”v 2 “u ”v ”k “， 见图1 - 6 ( c ) 。再分别经窗e l 右边和下边裁剪后得到最终结果为v 0 4 、4 k 4 ，见图 1 - 6 ( e ) 。 。 。4 岱了；国； 图1 - 6s u t h e r l a n d - h o d g e m a n 算法裁剪原理 假设待裁剪多边形为v 0v l k ，窗口各边所在的直线将二维空间划分成两 个半空间，记裁剪窗口区域所在的一侧为内侧空间，另外一侧为外侧空间。在多 边形关于窗口各边的裁剪过程中，从v n v o ，v 0v l 直到v n 。v n ，检查多边形的每边 与窗口所形成的半空间的关系，输出0 、1 或2 个顶点到结果多边形顶点表中，图 1 - 7 显示了多边形的各边与半空间的所有四种关系。 s p ( a ) s ( c ) p s 图1 7 多边形各边与半空间的四种美系 假设当前处理的多边形的边为s p ，顶点s 在上一轮中已经处理。图l 一7 ( a ) 中， s p 完全落在裁剪边的内侧，将点p 输出到结果多边形顶点表中；图l 7 ( b ) 中，p 点 在外侧不可见，而交点h 应输出；图1 - 7 ( c ) 中，s p 完全在外侧，没有输出；图1 7 ( d ) 中，交点h 和p 点，都是结果多边形的顶点，按顺序先输出h 再输出p 。由以上分 8 中南大学硕士学位论文第一章绪论 析得知，裁剪结果多边形的顶点由两部分构成，一部分是落在裁剪边内侧的原多 边形顶点；另一部分是多边形的边与裁剪边的交点。只要将这两部分顶点按一定 的顺序连结起来就得到了裁剪结果多边形。 图1 4 凹多边形的裁剪 凸多边形可以用该方法获得正确的裁剪结果，但是对凹多边形的裁剪( 图 4 8 ) 则显示出一条多余的线段。因为只有一个输出顶点表，所以表中最后一个 顶点，总是连着第一个顶点，在许多应用中，如实区域扫描转换中，这些退化边 界的存在无关紧要。然而在另一些应用中，如在某些消除隐藏面算法中，则需事 先消去这些退化边界，这无疑增加了算法的复杂性。为了裁剪凹多边形，一种方 法是将凹多边形分割成两个或更多个凸多边形，然后分别处理各个凸多边形。另 一种方法是修改s u t h e r l a n d - h o d g e m a n 算法，沿着任何一个裁剪窗口边界检查顶点 表，正确地连接顶点对。 2 、w e i l e r - a t h e r t o n 算法 在w e i l e r - a t h e r t o n 算法中，裁剪窗口和被裁剪多边形可以是凸的、凹的或者 是带有内环的任意多边形。裁剪窗口和被裁剪多边形处于完全对等的地位，称被 裁剪多边形为主多边形。记为a ，称裁剪窗口为裁剪多边形，记为b ，如图1 9 所 示，a 、b 分别用实线和虚线表示。约定多边形外部边界的顶点逆时针排列，内 环的顶点顺时针排列。因此，多边形区域始终位于有向边的左侧。多边形a 和b 的边界将整个二维平面划分成a n b ，a b ，b a ，a u b 四个区域。 图1 - 9 多边形的裁剪 内裁剪的结果( 即两多边形的叠加) 为a n b 。裁剪结果区域的边界由a 的 9 中南大学硕十学位论文 第一章绪论 部分边界和b 的部分边界两部分组成，并且在交点处边界发生交替，即由a 边界 转至b 的边界，或由b 的边界转至a 的边界。由于多边形构成一个封闭的区域，所 以，如果主多边形和裁剪多边形有交点，则交点必成对出现。这些交点分为两类， 类称为入点，主多边形边界由此交点进入裁剪多边形区域内；另一类称为出点， 主多边形边界由此交点离开裁剪多边形区域。 w e i l e r - a t h e r t o n 算法的具体实现步骤如下： s t e p l 建立主多边形和裁剪多边形的顶点表； s t e p 2 求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形 的顶点表中，在两多边形顶点表中的相同交点间建立双向指针； s t e p 3 将裁剪多边形对主多边形进行裁剪操作。对没有被跟踪过的所有交 点，执行以下步骤： ( 1 ) 建立空的裁剪结果多边形的顶点表： ( 2 ) 选取任意一个没有被跟踪过的交点作为起点，将其输出到结果多边形 顶点表中； ( 3 ) 如果该交点为入点，跟踪主多边形边界( 顶点表) ，否则跟踪裁剪多 边形边界( 顶点表) ； ( 4 ) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表 中，直到遇到新的交点； ( 5 ) 将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针 改变跟踪方向； ( 6 ) 重复( 4 ) 和( 5 ) ，直至回到起点。 1 3 论文组织结构 本论文主要涉及的内容是地理信息系统空间分析中缓冲区分析和叠加分析 两类主要分析方法的研究。论文共分六章，结构如下： 第一章为绪论，提出本文的研究内容、重要意义和研究现状，并阐述空间 分析的关键技术及叠加分析和缓冲区分析现有核心算法。 第二章首先简述空间分析的数据特征、表示方法、研究内容及学科基础， 然后进一步介绍空间分析模型、缓冲区分析和叠加分析的相关理论。 l o 中南大学硕士学位论文 第一章绪论 第三章介绍缓冲区分析的基本概念和性质，在角平分线算法和凸角圆弧算 法基础上，本章提出一种新的缓冲区半径旋转生成算法。并详细给出点、线和 面各种目标的缓冲区生成的具体方法及步骤。另外，对缓冲区生成过程中出现 的特殊情况进行处理，并应用递归方法管理和存储缓冲区边界的自相交多边形， 形成了一套完整的缓冲区生成算法。 第四章首先介绍叠加分析的基本概念及定义，然后在叠加分析w e i l e r 算法 和g r e i n e r - h o r m a n n 算法基础上，本章提出一种既适用于简单多边形叠加，也 适用于复杂多边形叠加的改进算法，简化了多边形叠加的流程。改进算法在占 用存储空间、计算量和运行速度方面都具有优越性。 。第五章概述功能实现的方法，以v c n e t 作为软件开发环境，采用基于 0 0 4 0 的o r a c l e 9 is p a t i a l 空间数据访问方法，实现空间分析中叠加分析和缓冲 区分析两种重要功能。 第六章也是全文的最后一章，对全文所开展的工作进行总结，并指出进一 步的研究工作。 中南大学硕士学位论文第二章空间分析 第二章空间分析 空间分析是基于地理对象的位置和形态特征的空间数据分析技术，其目的 是提取和传输空间信息，这是地理信息系统区别于一般信息系统的主要功能特 征，利用空间分析方法不但可以查询数据库系统中的各种信息，而且可以通过 这些信息去揭示事物间更深刻的内在规律和特征。空间分析是g i s 的核心功能 之一，g i s 的成功应用依赖于空间分析方法和功能的有效应用。 2 1 空间分析基础 地理信息系统能够飞速发展和广泛应用，主要原因就是其具有管理空间数 据，并利用空间数据进行空间分析，为各行业服务的能力。 2 1 。1 空间数据的特征 空间数据是指以地球表面空间位置为参照的自然、社会和人文经济景观数 据，可以是图形、图像、文字、表格和数字等。它是g i s 所表达的现实世界经 过模型抽象后的内容，一般通过扫描仪、键盘、磁带机或其它通讯系统输入g i s 。 在g i s 中，空间数据主要包括以下内容： l 、空间实体的位置 在某一个已知坐标系中的几何坐标，标识了地理现象在自然界或某个地图 区域的空间位置，如经纬度、平面直角坐标和极坐标等。 对空间实体的位置进行描述，必须对其进行抽象表示。一般来说，在二维 分析空问，根据分析问题的尺度，我们把自然界中的物体抽象为点、线和面三 种，在三维分析空间，则区分为点、线、面和体四种。 2 、空间实体之间的关系 实体之间的关系通常包括： ( 1 ) 度量关系，如两个实体之间距离的远近； ( 2 ) 延伸关系或方位关系，定义了两个实体之间的方位； ( 3 ) 拓扑关系，定义了两个实体之间的关联、邻接和包含关系。 1 2 中南大学硕士学位论文 第二章空间分析 3 、空间实体的非几何属性 一般简称属性，是指与地理实体相关联的地理变量或地理意义。属性分为 定性和定量两种，定性数据包括名称、类型、特性等，如地貌类型、土地利用 类型、行政区划等，定量数据包括数量、级别等，如土地面积、道路长度、人 口数量、高程等；非几何属性一般是经过抽象和概括，通过分类、量算和统计 得到。地理信息系统中的分析和检索大部分都是通过对属性的操作运算实现的， 因此，属性数据的分类系统、量算指标及准确性对系统功能的实现有较大的影 响。 4 、空间实体的时间特征 空间实体的时间特征是指空问实体或现象随时问的变化。空间实体的位置 数据和属性数据相对于时间来说，常常呈相互独立的变化，即在不同的时间， 空间位置不变，但是属性特征可能已经发生变化，或者相反。 对空间数据的分析经常要面临空间数据的误差、数据集成、数据的详尽程 度以及合适的空间分析方法等问题。数据的误差会在定位和属性数据的测量中 产生，并在各种操作和分析过程中传递。同时，操作和分析过程本身也会产生 一定的误差。数据集成过程中不同类型数据可能不兼容也是空间数据的特征之 一。这种不兼容可能由使用不同的空间参考系、不同时段的数据层，不同的数 据综合程度以及位置误差等引起。最后，由于对象和事件在空间分布上的非独 立性，但是常规统计分析中样本独立是最基本的假设前提之一，因此空间数据 不适于常规的统计分析。这一问题本质上是由地理现象的空间依赖与空间异质 性决定的。 2 1 2 空间数据的表示 空间数据的表示，就是指将以图形模拟的空间物体表示成计算机能够接受 的数字形式。计算机对上述空间数据内容的描述，主要的差别体现在对空间数 据位置及其关系的表达，对非几何属性的记录，一般都用关系表的形式或指针 来完成。 计算机描述空间实体( 位置及关系) 有显式描述和隐式描述两种形式。显 式表示，就是把表示的空间栅格化，通过给定栅格中一系列像元的编码、颜色、 数值或符号来表示。隐式表示是用一些坐标点或定义了起点和终点的线及某种 连接关系的矢量来描述。显式描述和隐式描述，从数据结构角度，一般称为栅 格数据结构和矢量数据结构。 中南大学硕士学位论文第二章空间分析 栅格数据结构是最简单和最直观的空间数据结构，又称为网格结构或像元 结构，是指将地球表面划分为大小均匀且紧密相邻的网格阵列，每个网格作为 一个像元或像素，有行列号定义，并包含一个代码，表示该像素的属性值，或 仅仅包含指向其属性记录的指针。因此，栅格结构是以规则的阵列来表示空间 地物或现象分布的数据组织，栅格中的每个数据表示地物或现象的非几何属性 特征。 图2 1 点、线和面数据及其栅格表示 如图2 1 ，在栅格结构中，点用一个栅格单元来表示；线则用沿线走向的一 组相邻栅格单元表示；面或区域用记有区域属性的相邻栅格单元的集合来表示。 矢量数据结构，是另一种常见的图形数据结构，它是通过记录坐标的方法 尽可能精确地表示点、线和面等地理实体，坐标空间为连续的，可以允许任意 位置、长度及面积的精确定义。 在矢量数据结构中，每个点用一个x ，y 坐标来记录，线用一组有序的x ， y 坐标来记录，面用一组线段( 所有线段可构成一个封闭的区域) 的x ，y 坐 标来记录。在面的表示中，多边形的第一个坐标和最后一个坐标总是相同的， 在g i s 软件中，一般是通过拓扑检查来实现的。 2 i 3 空间分析的内容 g i s 提供一系列的空间分析工具，用户通过已有的数据模型，经过一系列 的操作序列，求得一个新的模型，这个新模型可展现出数据内部或数据之间新 的或未曾明确的关系，从而回答用户的问题。 空问分析从数据模型可划分为拓扑分析、属性分析和拓扑与属性的联合分 析。拓扑分析包括空间图形数据的拓扑运算，即旋转变换、比例尺变换、二维 及三维显示、几何元素计算等；属性分析包括数据检索、逻辑与数学运算、重 分类，统计分析等；拓扑与属性的联合分析包括与拓扑相关的数据检索、叠加 1 4 中南大学硕士学位论文第二章空间分析 分析、区域分析、邻域分析、网络分析、形状探测、瘦化处理、空间内插等。 空间分析的基本步骤包括建立分析的目的和标准、准备空间操作的数据、 进行空间分析操作，准备表格分析的数据、进行表格分析、结果的评价和解释、 改进分析结果、产生最终的结果和表格报告。 为了达到空间分析的目的，必须在现有的全部要素基础地理数据和按专业 系统分类的数据的基础上提炼用于实现空间分析的专题图，并在基础数据结构 的基础上进一步拓展部分专门存放用于空间分析数据的数据库。然后，再配合 相应的空问分析模块，最终达到分析的目的。其技术流程如图2 2 所示 2 1 4 空间分析的学科基础 图2 - 2 空间分析技术流程图 6 0 年代地理学计量革命中的有些模型初步考虑了空间信息的关联性问题， 成为当今空间数据分析模型的萌芽。也是6 0 年代，法国m a t h e r o n 在前入的基 础上，总结提出了地统计学，或称g r i 百n g 方法，i 内容为用随机函数评价和估计 自然现象的技术，随后- j o u m e l 针对矿物储量推算，将此技术在理论上和实践中 椎向成熟。同时，统计学家也对空问数据统计产生了兴趣，在方法完备性方面 有诸多贡献。地理学、经济学、区域科学、地球物理、大气和水文等专门学科 为空闯信息分析模型的建立提供知识和机理。 2 2 空间分析模型及相关软件 空间模型是指根据空间信息建立的模型或具有空间分布意义的模型。空间 模型具有相当广阔的和交叉性质的研究领域。从不同的角度考察空闯模型，将 获得不同的分类。 2 2 1 空间分析模型理论 空间分析功能的实现分为4 个层次： 中南大学硕士学位论文第二章空间分析 1 、认知，对空间数据进行有效获取和科学的组织描述，利用空间数据来再 现事物本身，例如由管线的平面图绘制纵或横剖面图； 2 、解释，理解并解释空问数据的背景过程，认识事件的本质规律，例如住 房价格中的地理邻居效应； 3 、预报，了解和掌握事件发生的规律后，运用预测模型对未来的状况做出 合理推测，例如预测传染病的爆发； 4 、宏观决策和调控，根据空间分析结果做出合理决策，调控地理空间上发 生的事件，如合理分配资源等。 可见，随着空间分析技术应用的深度和广度的不断拓展，g i s 也将由一般的 空间事务处理向分析型的空间决策支持方向迈进。现有g i s 的空间分析仍旧停留 在应用层次