（地图学与地理信息系统专业论文）缓冲区生成与多边形叠加算法研究.pdf

摘要 本文针对当前缓冲区分析的研究现状，在地理信息系统、计璧蓠藿嚣鏊； 羹霾霞浅篓霾冀霾羹雾装戮鐾墓；冀鲤鋈冀攀澎巢邕簧萎墓霁霆囊簿冀冀望薹菘 羹露些霭速囊雾羹替羹二 蓄璧篓鸶雾翼蓁藤秦毹辫；露鞋鲤嚣蚕蒋塑瓤薹薹辇篓殛鬻翼囊亘雾簧匦 举壁塞謇蕈器；嚣耄蠢鋈鬟茎雾；蓁鋈羹雾堑霸耨唾萄雾誊醚轿雾篓冀雾；薹嘉塞 霞鋈冀耋蔷矍豳雾施簧霭震鏖羲型：纂皲冀纂霎薹葫装，修订版一匕京：高等教 育出版社，2 0 0 l ，1 6 5 1 7 1 【3 】m f g 0 0 d c h i l d ( 2 0 0 1 ) g e o 酣i ci n f 0 】啦a t i 0 i ls y s t 锄i i la g d i e ，e d i t e n c y c l o p c d i a o f g l0 b a lc 1 1 锄g e n 州y 破：魄f o r du n i v 粥时p 瑚s 【3 5 4 】 【4 】吴信才地理信息系统原理与方法【m 】北京：电子工业出版社，2 0 0 2 ，1 6 0 1 6 7 【5 】q i i iy a n ，j i - x i 觚压强g h l t 啊t d ea p p l i c a t i o no fr s 锄dg i st oa 鲥c t l l t l 鹏l a n du s e p l 砌1 i n g 【j 】g 一s p a t i a li n f o n n a t i 衄s c i c c ，2 0 0 2 ，5 ( 2 ) ：51 5 5 【6 】cl a 咄m p u t 妇gw a t 盯i i li t sp l a ：ap e f s l c c t i v e g i si l lh y d r o l o g y 蜘dw a 衙 m 锄ag 啪e n t 【j 】h y d m l o 舀lp r o o 豁s 鹤，1 9 9 8 ，1 2 ( 6 ) ，8 2 3 8 3 4 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 壁浆粒妻徭石月名 学位论文使用授权说明 日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理 敝作者c ：随南乞聊磊占月 河海大学硕士学位论文 第一章绪论 地理信息系统( g i s ) 与计算机辅助绘图系统的主要区别是g i s 提供了对原始 空闻数据实施转换以豳答特定查询的能力，两这些变换麓力中最核心的部分就是 对空间数据的剥用和分析，即空间分柝能力。空闻分橱源予6 0 年代地理和区域 科学的计量革命，在开始阶段，主要是应用定量( 主要是统计) 分析手段用于分 析点、线、面的空间分布模式。后来更多的是强调地理空间本身的特征、空间决 策过程和复杂空间系统的时空演化过程分析。实际上自有地图以来，人们就始终 在自觉或不自觉的进行着各种类型的空间分析。如在地图上量测地理要素之间的 距离、方位、面积，乃至利用地图进行战术研究和战略决策等，都是入们利用地 图进行空间分析的实例，丽后者实质上已属较高层次上的空间分析。 地理信息系统集成了多学科的最新技术，如关系数据库管理、离效图形算 法、插值、区划和网络分析，为空间分析提供了强大的工具，使得过去复杂困难 的高级空间分析任务变得简单易行。空间分析是对分析空间数据有关技术的统 称。根据作用的数据性质不同，可以分为：基于空间图形数据的分析运算； 基于非空闻属性的数据运算；空闻与非空间数据的联合运算。空闻分析赖以进 行酶基础是地理空闻数据库，其运用的手段包括各种几何的逻辑运算、数理统计 分析，代数运算等数学手段，最终的虽的是解决人们所涉及到地理空闻的实际闯 题，提取和传输地理空间信息，特别是隐含信息，以辅助决策。 目前的地理信息系统软件如国外商用的觚g i s 、m a p i n f 0 ，国内的 s 删a p 、m a p g i s 以及开源的g i 稻s 、q g i s 等都具有比较好的空间分析功能。 空问分析也早已成为地理信息系统的核心功能之一，它特有的对地理信息( 特别 是隐含信息) 的提取、表现和传输功能，是地理信息系统区别予一般信息系统的 主要特征功能，体现了g l s 的本质。 1 1 研究背景及意义 缓冲区分柝与多边形叠加是毯s 中基本的空间分析功能之一，蔼蜃者更是 众多空间分析算法的基础。它们在很多行业有着广泛的应用，水剩学科也不例外， 河海大学硕士攀位论文 例如利用缓冲区分析可以来进行洪水淹没的计算，在计算雨量站权重的泰森多边 形中需要瘸到多边形叠加分析等等。因此，这两种算法在数字流域系统中就显褥 异常重鼹。虽然当前地理信息系统主流软件平台( 如a r c g i s 、m 印i n 硒等) 中 这两个功能的算法均毙较成熟，但其体的算法都没有公开。嗣内井豹些文献也 有相关论述【1 毛1 m 1 4 2 2 - 矧，但它们并不全面，实际过程中会遇到很多异常情形，而 且菜些方西( 如不对称缓冲送边雾鳇生藏) 也不适合我靛数字流域系统的需求。 关于多边形叠加算法，微软的相关函数库( 如m f c ) 提供了交、并、补函数 i 赡寝鐾成员丞数 ，但这壁函数只适羽予整型变量，对予数字漉域系统串 要求的浮点型变量并不适用，而且它们未能公开多边形类( c r 鲈类) 的顶点数 据成员，无法获得裁剪运算螽豹多边形。此外，冒际上一些g l s 的开源栽码霹 ( 如g d a 【c i g r 、g e o s ) 也提供了这两种功能，但是它们所基于的数据结构岛 我娟数字流域系统的数据结擒商很大差异，魏票使蹋歼嚣库，就需要将地理数据 进行来回的转换，这极大的浪费了计算机的资源，使得计算机大部分的运行时间 都花费在数据的转换主，这也违背了算法设计戆初褒。 ， 因此，很有必要对缓冲区生成与多边形叠加的算法进行深入的研究，以适 合我缃的数字流域系统，这也是本文 舞究的主要悫容。 i l 。2 研究内容 本文的研究内容分为缓冲区生成与多边形叠加算法两部分。前者主要是在 凸角圆弧法的基础上，利用矢量方法，探讨缓冲区边界生成时产生的失真现象、 不对称缓冲区的生成、自相交多边形以及轴线自相交的处理等；后者主要是研究 新的多边形裁剪算法一面向对象的通用多边形裁剪算法，并针对特殊多边形鹩 裁剪提出一些解决方法。 1 。3 缓冲区分析 空间缓冲区分析( s p 删a lb u 妇瞬a n a l y s i s ) 是地理信息系统中基本的空问分析 功麓之一艇。它是根据研究鏊标起点、线、面实荐，在其周围建立一定距离麴繁 状区，用以识别这些目标实体对邻近对象的辐射范围或影响度，以便为某项分析 或决策提供莜据湖。它在现实孛霄着缀广泛鳇应用： 2 河海大学硕士学挝论文 一) 在城市规划中的应用： 政府拟对道路进行改造，在工程实施之前需要对道路改造过程中涉及到的 商铺、屠民楼等建筑物进行统计，此时可以利用缓冲区分析来确定需要拆迂的范 围及对象【4 j 。 ( 二) 在生态环境保护中的应焉： 针对目前我国水土流失面广量大，水资源短缺、水污染严重的实际情况， 在汪、河( 沟) 、湖、库周边地区，可以应矮缓冲区分桥的方法，结合必要的王程 措施，对进一步加快水土流失防治进程，涵养水源，降低农业生产中农药、化肥 等面源污染对承体的污染，保护生态环境其有十分重要的意义【5 瑚。 ( 三) 在商业方面的应用： 商韭选垃中，根据人翻麓密度、交通便利情况来决定超市的位置。在商业 评价中，根据门店的地理位置及规模，确定该店的辐射范围。与最优路径结合可 以选定最佳的配送方案噬。 3 1 缓冲区生成算法的研究现状 缓冲区根据研究目标的不同，可以分为：点缓冲区、线缓冲区、面缓冲区。 点缓冲区，是以目标点为圆心，半径为缓冲距的圆周所包围的区域；线缓冲区， 是以目标线为中心线，向双侧或单侧平移一定距离的条状区域；面缓冲区，是以 翻标面的边界线为中心线，向外或向内扩展定距离所形成的多边形区域【协】。 缓冲区的生成方法主要有栅格和矢量鼯种。 ( 1 ) 栅格方法 栅格方法是将露标对象( 点、线、面) 转换为栅格模式，借助缓冲区半径 计算像元加粗次数，对其进行加粗，然后进行边缘提取，最后得到缓冲区【l l 】。栅 格方法的算法原理比较简单，且容易实现( 如图l 。1 所示) 。 3 河海大学硕士学位论文 穆) 矢量方法 l 点目标缓冲区 圈1 1 栅格方法 点鬻标缓冲区是以爨标点为隳心，以特定魏缓泞送距离为半径的麴。在这 里，我们可以采用圆弧弥合法，将圆心角等分，用等长的弦来代替圆弧，即用 今正多边形来无限逼近测髑l 潮，如避嘻。2 所示。 参= 毡l ，孬0 一 ) 其中粕，嫡为点篷标对象的坐标，p f x ，磅涛缓冲区逑赛上各弥合点上的坐标利 用公式1 - 1 计算) ，d 为缓冲区半径，n 为等分数。等分数越大，等分的圆心角越 小，步长越夺，精度越离；等分数越小，等分酶匾心角越大，步长越大，精度越 低。 n=4n=6n=s 爱 。2 誉精步长的鼗弧豫裔 i i 线目标缓冲区 线缓挣嚣的建立是以线获蠢标为参考轴线，离开轴线向薄麴或荤侧沿法线 方向平移一定距离，并在线端点处以光滑曲线( 如半圆弧) 连接，所得到的点组 成的封闭区域即为线状嚣标鹣缓冲区f 臻。线缓冲区生成熬方法主要有分段叠瓣 4 、夕、稚， 蕊|推丝栉 厂义厂心 0 ，n o s 搴 d d + + n i l = x y ，p、陟、 河海大学硕士学位论文 法e 、焦平分线法【l l 】、凸角圆弧法等。本文采用凸角圆弧法来生成线缓冲区。 分段叠加法 分段叠加法将轴线分解为若干条简单的线段，然后分别对其生成局部缓冲 区( 线段两端分别用圆弧弥合) ，最后将这些局部缓冲区进行叠加得到结果缓冲 区( 如图1 3 所示) 。 豳 3 分段叠加法 角分线法 角分线法是在轴线首尾点处，作轴线的垂线并按缓冲区半径r 截池左右多 边形的起止点，在轴线的其他转折点上，用与该线关联的前后两邻边距轴线的距 离为r 的两平行线的交点来生成缓冲区对应顶点( 如图1 4 所示) 。 豳1 4 角分线法 凸角圆弧法 凸角圆弧法的原理和角分线法有些相似，均属于双线法，但凸角圆弧法首 先要判断轴线各结点的凹凸性，然后在凸的地方用圆弧弥合，而凹的地方用平行 线交点代替( 如鹰 5 所示) 。 5 河海大学硕士学位论文 虽然凸角圆弧法具有很多优点，但其缺点也很突出，主要是缓冲区边界随 着缓冲距的增大将会迅速远离轴线，这就会出现尖角和凹陷等失真现象( 如图 1 7 所示) 以及自相交多边形问题，这些均是不合理的，必须进行修正，因此这 将是本文的研究内容之一。 ，一 s b i 图1 7 缓冲区边界尖角、凹陷现象 当前国内外此方面的文献较多的描述凸角圆弧法的基本思想【l 卜1 7 1 ，较少对 其产生的失真现象的处理进行论述【1 2 】；大部分文献针对的是建立双侧对称的缓 冲区【1 1 1 3 1 ，而很少阐述单侧或左右不对称的缓冲斟1 舯。龚洁晖等人曾归纳了一些 失真现象并提出了不同的修正方法1 1 2 1 ，但这些并不全面，实际过程中，出现更 多的失真处，有些方法也不完全正确。本文将对这些方面进行详细的叙述。 1 3 3 缓冲区问题的研究方法 利用凸角圆弧法生成缓冲区的边界时，轴线的转角处容易产生尖角、凹陷 等失真现象。缓冲距越小，失真现象越轻微；缓冲距越大，失真现象越明显，如 图1 8 所示。 7 河海大学硕士学位论文 p h ：、。 l _ l ， 圈1 。8 缓；聋区边界失翼 本文将用几何的方法，归纳缓冲区边界生成中失真现象产生的条件，在不 同的条件下缓冲区边界将会产生不同的失真现象( 尖角或凹陷) 。在前人1 1 2 】的基 础上将缓冲区边界的失真现象分为三类：凸凹凸、凸凹凹、凹凹凸( 分别为前一 结点、当前结点与后一结点的翻凸性) 。然后根据缓冲边界上的点与特点弥合弧 段的位置关系( 点在弧段左侧或右侧) 来判断边界是否失真，并提出相应的解决 方案，用相应两个弥合弧段或弥合弧段与缓冲乎行线的交点来代替失真点，并去 除多余的弧段，总共可分为三大类3 6 种情形。 1 4 多边形叠加 空间叠加分析( s p a t i a lo v 刚a y 馘a l y s i s ) 是指在统一空间参照系统条件下，每 次将同一地区两个地理对象的图层进行叠加，以产生空间区域的多重属性特征， 或建立地理对象之间的空间对应关系【2 】。叠加分析是g i s 用户常用的捷取数据的 手段之一。该方法源子传统的透明材料叠加，即将来自于不同数据源的图纸绘予 透明纸上，在透贺桌上将图纸叠放在一起，然嚣焉笔勾蘧磁感兴趣的部分( 郎提 取感兴趣的数据) 。地图的叠加，按直观概念就是将两幅或多幅地图重叠在一起， 产生新数据层和新数据层上的属性【4 l 。 叠加分析也可以分为栅格与矢量两种，在栅格系统中，层间叠加是通过像 元之间的各种运算来实现，而矢量方法则是通过几何运算来求得叠加结果【4 】。多 边形与多边形之间的叠加是g i s 叠加分析中最常用的一种，它叠加的结果是在 新的叠加图上，产生许多新的多边彤， x 河海大学硕士学位论文 点列表，均位于裁剪面的可见一侧。此算法可以在任何凸多边形窗口内对任何凸 或凹的、平面的或非平垂的多边形进行裁剪。窗口各边以什么顺序裁剪多边形无 关紧要2 糊1 。 裁剪窗口 边形 - - 裁剪底边及裁剪 翡绩莱多边髟 一- _ 。 剪左边 剪顶边 图缄抛 图 ，l o 逐次多边形裁舅 ( 2 ) l i a n g b a r s k y 算法 l i 勰g - b a 戚( y 多边形裁剪算法是基于其线段裁剪概念。该算法假定区域和 多边形共面，裁剪区域或窗口的每条边将平面划分为两个半平面。包含裁剪窗 髓的半平面稼为酉见或内半平面，另一个称为不可见或终半平面。窗目的四条边 将平面划分为九个区域，如图1 1 1 所示。每一个都位于一定数目的半平面的可 见侧，但只有裁剪窗口位于所有四条边的内侧。它通过判断交点的进出性以及将 折点输出到多边形( 如图1 1 2 所示) ，而得到结果多边形【2 2 雄辩。 l o 如图1 1 3 所示 籼 图1 1 3 w 娃静眦瞰o n 算法 1 。4 。2 多边形叠加润题的提出 。二笺一 么不能娃理凹多边形( 如删赫擘畦竺：二矗：；蕃多新的多边形羲剪技 点不易判断( 如黜舢鳓算法) 邈辱券粉川” 1 2 河海大学硕士学位论文 1 5 论文组织 论文共分五章，依次为： 第一章为绪论，介绍了本文的研究背景、研究内容、研究方法、国内外研 究现状以及论文的组织结构。 第二章介绍了在缓冲区生成算法与多边形裁剪算法中需要用到的相关图形 学算法。 第三章介绍了缓冲区生成算法中的凸角圆弧法，在它的基础上，归纳了缓 冲区边界生成时产生的失真现象及其条件，并提出其相应的解决方案。 第圈章提出了瑟向对象豹逶用多边形裁剪算法，概括了该算法中的一些特 殊情况，特别是对重合边的情形进行了重点的讨论，并提出了新的解决方法。 第五掌秀对本文磺究工律的总练秘对避一步工箨的展塑。 1 4 河海大学颁士学位论文 第二章图形学算法基础 2 1 点与直线段的位置 假设平嚣内有a ( 瓢，y ) ，b ( x b 站两点，现考虑另一点c ( x 白y 。) 相对于直 线段a b 的位置，即其是在直线段左侧，右侧还是直线段上。矢量的叉积面盈 只含z 分量，z 分量的符号反映了该位置( 如图2 。1 所示) ，叉积公式如2 - l 。 c a b $ a c 图2 1 点与直线的位置 厶c 絮么艿彳c ：而一颤) 率虼一儿) 一一毛) 掌欺一致) 2 - 1 ) b 按照右手法则可知： f a c o嘴位子线段a b 左侧 c 进行比较。若f x ，交点数不变。 步骤四：判新交点总数为奇数或楚偶数，如果为奇数，则代表点p 在多 边形内部；如果为偶数，则点p 在多边形外部。 2 4 两直线段的交点 设两直线段l ；与k ，l ；的两个端点为p ，( x ，y ，) 、p ：( x ：，妫，l 2 的两个端点 为p 3 ( x 。，y 。) 、n ( x 。，y 。) 。根据直线的两点公式( 式2 5 ) ： y y i x 一而 - - _ _ - _ _ _ _ k = _ _ _ _ - _ _ _ _ 照一魏而一五 ( 2 5 ) 兰二垫：苎二兰 y i y 3x 4 一黾 。 可得两直线方程( 式2 - 6 ) ： ：嚣曷其中长三：二装篡裟c 2 每， ( 1 ) 当a l 现= r a 2 转l 时，两条直线段平行或重合。 河海大学硕士学位论文 条线段朗进行跨立试验n 砖，霹以利用2 。1 中的算法，即通过两个矢量的叉积来判 断线段的两端点是否在另一条线段的异侧。如图2 。11 所示，这两条线段可以通 过快速排斥试验，即矩形包豳盒相交，但两线段本身并不相交，因为线段并没有 跨立对方。需要注意的是，实际情况中应该选择至少有一个端点位于对方的矩形 包围盒内的线段来进行判断，即判断k 的端点c 、d 是否跨立l 。，而不是判断l 。 的两点a 、b 是否跨立k 。如果此试验成功，则线段相交，反之则线段不相交( 如 图2 。 1 所示) 。 a 2 6 本章小结 豳2 1 1 跨立试验 针对本文研究的两个重点内容( 缓冲区生成、多边形叠加) ，论述了它们涉 及到的图形学算法，并在经典的计算机图形学算法的基础之上做了一些改进，提 出了一些特定的解决方案。主要有以下凡点： ( 董) 在点与直线位置的经典算法基础上提出判断点与弧段的位置的方法。 2 ) 叙述了点与多边形位置的算法，并总结了其特殊情况的处理，并详细叙 述了其实现的详细步骤。 ( 3 ) 概述了直线求交的算法，并根据本文研究的内容重新设定了重合线段求 交的交点计数。 ( 4 ) 简述了对两多边形求交葬法的优纯方法。 河海大学硕士学位论文 第三章缓冲区生成算法及其失真现象校正 3 1 缓冲区的基本概念 空闻缓冲区分析( s p 撕a l 撕翁融鑫毂a l y s i s ) 是地理信息系统中基本的空间操 作功能之一，它是根据研究目标的点、线、面实体，在其周围建立一定距离的带 状区，用以识别这些目标实体对邻近对象的辐射范围或影响度，以便为某项分析 或决策提供依据。从数学的角度看，缓冲区分析的基本思想是给定一个空间对象 或集合，确定它们的邻域，邻域的大小由邻域半径r 决定。因此对象o i 的缓冲 区定义为： 马= 扛：d ( 五璐) 震 ( 1 ) 即对象o i 的半径为r 的缓冲区为距o i 的距离d 小予r 的全部点的集合。 d 一般是最小欧氏距离，僵也可以是其他定义的距离冽。对于对象集合 d = q ：江l ，2 ，辫； ( 3 1 2 ) 其半径为r 的缓冲区是各令对象缓冲区的并，即： 君= u 置 ( 3 1 3 ) f = l 点对象、线对象、面对象及对象集合的缓冲区如图3 1 所示。 o q圆 一 圈3 1 点、线、多边形的缓冲区 河海大学硕士学位论文 图3 3 自相交多边形 自相交多边形分为两种：岛屿多边形和重叠多边形。岛屿多边形是缓冲区边界的 有效组成部分；重叠多边形不是缓冲区边界的有效组成，不参与缓冲区边界的最 终重构。岛屿多边形与重叠多边形的自动判别方法为：首先定义轴线坐标点序为 其方向，然后从轴线首点到末点生成右侧缓冲区边界，再从末点到首点生成左侧 缓冲区边界，这样可以根据点序的方向来判别自相交多边形的类型。顺时针方向 的为岛屿多边形，需要保留；逆时针方向的为重叠多边形，将其剔除，最终形成 缓冲区轮廓( 如图3 4 所示) 。可以采用递归法自相交问题n 引。图3 ：4 剔除自相交多边形后的缓冲区边界( 2 ) 失真问题 利用凸角圆弧法生成的缓冲区边界，轴线转角尖锐的转折点的平行线交点 随缓冲距的增大将会迅速远离轴线，这就会出现尖角和凹陷的失真现象，后面将 对其进行详细的讨论。 ( 3 ) 不对称缓冲区 在实际应用中，经常需要建立不对称缓冲区，如环境评价中，河流左右岸 的影响度不一样；城市规划中，对道路两侧拆迁的范围不同等。当建立左右缓冲 距不相等的缓冲区( 不对称缓冲区) 时，轴线两端以内的中间结点处缓冲区边界 河海大学硕士学位论文 因此，p 点为失真点。 豳3 7 中，0 线豳3 8 缓；孛区边券 3 3 1 缓冲区边界生成时的失真现象产生条件 虽然利用凸角圆弧法生成线目标缓冲区容易产生失真现象，但并不是在轴 线的每个结点附近都发生失真。失真现象总是发生在当前点处为凹角( 两侧端点 除外) 的这一侧，在凸角处则不会失真，而在凹角处发生失真也是有条件的，如 图3 9 所示，i 葫为线目标对象即中心线，、蚓分别为线段而、历的长度， 聪为么d 与的夹角，d 为缓冲区半径即缓冲距，缓冲区边界产生失真现象的 条件如式3 - 5 所示。 o o fo 矗 删 心“脚 l 蠢勉 陷 图3 9 失真现象产生的条件 不产生失真现象 产生凹陷 ( 3 5 ) 产生尖角 其中删= m ；n ( t a n 詈，i ，2 l 锄詈) ，= m a x ( 毒劬詈，蚀詈) 显然，缓冲区边界上的这些失真现象是不合理的，必须对其进行修正，也 就是用真实边界上的点来替代失真点，这就是失真现象修正。 河海大学硕士学位论文 3 3 2 修正前的准备及相关定义 节点：构成轴线线坐标序列中的各个坐标点。 中心线左( 右) 侧：中心线前进方向上的左( 右) 侧即为其左( 右) 侧， 在几何上判断点在线段的左( 右) 可以利用矢量叉积来计算。 结点元素：趣角圆弧法在中心线上节点凹侧的地方用平行线的交点来代 替，凸侧用圆弧来模拟，所以中心线上每个节点( 包括两端点) 都对应一个点集 ( 凹侧点集只包含一个点，凸侧点集可以包含多个点) ，这些点集就称之为中心 线上节点所对应的结点元素。在本文中，( i 一2 ) 、( i 1 ) 、( i ) 、( i + 1 ) 、( i + 2 ) 代表 中心线上相邻节点所对应的结点元素，其中( i ) 为当前节点对应的结点元素， ( i 1 ) 、( 冲1 ) 分另| j 为当前节点前一个和后个节点所对应的结点元素，( i 一2 ) 是 ( i 1 ) 的前一拿结点元素，( i + 2 ) 为( i + 1 ) 的詹一个结点元素。 点l 、2 、3 、4 、5 表示缓冲区边界上的点，点2 力( i 1 ) 的最后一个点， 点3 为( i ) 的点( 因为只针对凹处校正，所以( i ) 中始终只有一个点) ，点4 为( i + 1 ) 的第一个点。龚洁晖等人的校正方法认为点1 是( i 一2 ) 的最后一个点，点5 为( i + 2 ) 的第一个点n ，但这种简单的判断方法在某些情况下同样会产生失真，所以本人 认为点l 和5 的选取应该视中心线上对应节点处该侧的凹凸性而定。如果i l 节 点该侧为凸角的话，取点薹为卜l 所对应的点集中的第一个点，若为凹焦，点熏 为i 一羔点前一个节点所对应的点集中的最后一个点。如果i + l 节点为凸焦的话， 取点5 为“l 所对应的点集中的第一个点，若为凹角，点5 为卜l 点前一个节点 所对应的点集中的第一个点。 n a 9 1 表示点2 的凹凸性，n a 9 1 = l 代表点2 左侧凹右侧凸，n a g l _ - l 代表 点2 左侧凸右侧凹；同理f l a 9 2 表示点4 的凹凸性，k e y 表示点3 的凹凸性。 k 。为点2 相对于( i + 1 ) 的位置关系，k l _ l 表示点2 在( i + 1 ) 的左侧，k 。= o 表示点2 在( i + 1 ) 的右侧；磁为点4 x 河海大学硕士学位论文 线两端处计为凸角，所以可_ 以将畸变校正的条件分力以下三类： 中心线上当前节点处该侧为凹角，前一节点与后一节点处该侧均为凸角。 帮( i 一至) 是圆弧弥合点集，i 是平行线的交点，( i + 1 ) 为嚣弧弥合点集。此类情况酶 判断条件、校正方法、修正前以及修正后示意图如表3 1 所示。 表3 1 第一类情况 判瞬条徉 修趸蘸示意鬻求交线段修萎藉煮痔其示意匿 2 p 5 k i = l 1 却 ( i - l ，3 4 )1 u 7 k 2 = o k 3 3 4 f l 鸭l = - 1k l = o ，夼 ( 2 3 ，件1 )n k e y = - lk 2 = l 1 5 戮蠢醇= | 毒 5 2 l 5 k i = l 1 划 ( i - l ，i + 1 ) x 2 = l l 。 4 f i 鹕l 一- l 1 、2 x 掣一一l f 卜、 、3 弦3 ， 1 ) h 5 f l a 9 2 m l 屏， p 4 1 2 ： f 堍l * 一l 影 “5 l p k e y 一1 3 k 3 4 ，i i ) 一 s f l 啦一l 3 l 河海大学硕士学位论文 f l 醒l * l 1v 5 无 l ，2 ，3 ，4 ，5 k 掣。l ( 无失赛) f l a 9 2 。l 3 k l o 1 谁， l ， + 1 ) “、 k 2mo卜 p j 3 ( 2 3 ，i + 1 ) - 、。 秘a g l = l 1 、 ，5 卜5 k c y = l k l 。l 一o 琴l 磷= l 4 k l = o 一一籼 r 54 p l 、s4 _ 1 ) n x 2 一l ， l 7 p ! f l 铭l = i t 厂 ，一s k c y * l 3 z ( 3 4 i - 1 ) ： f 1 8 9 2 = l t 式 t 叫 2 3 鞫昭lml ，八5 无 l ，2 ，3 ，4 ，5 k 掣m l 无失囊) f l a 酩= l 5 i s 擎 f i 鸱l = l | | l ，l + 1 ) l i 畸= l 1 u f l a 9 2 = l 河海大学硕士学位论文 5 、 k 2 一o l 鼍2 ( 4 5 ，i - 1 ) 冬 l _ p f 匆 ( 3 4 ，i - 1 ) ， k 2 一l l 7 l 、 f l 鳎l = l p x 彰= l f l a 9 2 一一l 5 k 2 = o ，制 ( 4 s ，i 1 ) l l 心p 5 4 4 ，i - 1 ) k o = l l 叫奎 l 、 p l p f l a g l = l k 帮= 一l ； l ，2 ，3 ，4 ，5 k 2 一ol ， 无 无失粪) 5 叶 4 冬s ( 3 4 i - 1 )l 琢略l = l l 刊 ? 一p k c y = l k 2 一l f l 啦= l 河海大学硕士学位论文 3 k 2 = o 。代 ( 2 3 ，4 5 ) 。八2 l j 4 饼5 p 中心线上当前节点处该侧为凹角，前一节点处该侧为凹角，后一节点处 该侧为凸角。即( i 一1 ) 是平行线的交点，i 是平行线的交点，( i + 1 ) 为圆弧弥合点集。 此类情况的判断条件、校正方法、修正前以及修正后示意图如表3 3 所示。 表3 3 第三类情况 判断条件修正前示意图求交线段惨正后点序及其示意图 3 八 s 广。 k l = l5 邗4( 1 2 ，砷 ， 、 p f l a g l = - l 撕t z k t 猡= 一l 秘啦= 一l 2 l ( 2 3 ，i + 1 )k l = o 5 刊 厂鼍 k 1 。j k 1 = 1 j i ， ( 2 3 ，汁1 ) f l 鸭l = - l0 补5 卜5 4 k 留= l f l a 9 2 = l 务5 1 2 ，转l 。a 5 x l = 臻 河海犬学硕士学位论文 2 2 2 k l l 弋 裙3 ， + l 、3 卜 ，墨泠5 k 帮* * l 毒 f l a 9 2 一l 35 k lm 0无 l ，2 ，3 ，4 ，5 | ( 无失嶷) 2 | t l l ，2 ，3 ，4 ，5 k l l 2 0 5 无 ( 无失真) x 帮一l f l 磷；一l 差 3 l ? 襄l 8 掰5 1 2 i + l 芗 妒。5 4 z 重 k l * l 5 枇 1 2 l f 厂鼍 s 秘鑫客l 。l x 彰* l f l 硪= l 熏 ( 2 是i + 1 ) k l 一蛰 5 翔4 y 1 2 5 八l 。s 一p 河海大学硕士学位论文 ：i i ， 2 少1 2 ( 2 3 ，件1 ) t a ， k i = l 。爿。个s f l a g lml 4 k e y 一1 ? 小s 稀a 9 2 * l k l = o 4 岭 ( 1 2 ，i + 1 ) ? 一s 3 4 生成线目标缓冲区的主要步骤 前面论述了穗角圆弧法的基本思想以及失真现象修正，下面将用具体的例 予来具体阐述该算法的主要步骤。 步骤一：利用凸角圆弧法对线目标对象生成初始缓冲区边界，即在凸侧使 用圆弧弥合，凹侧用平行线的交点代替。为清晰起见，以右侧缓冲区为例，如图 3 1 0 所示，莉为线目标对象( 轴线) ，d 为缓冲区( 右) 半径，耳孑荔i 覆 即为初始缓冲区边界。 稠3 。 o 线謦标缓冲区透界 ( 1 ) 判断线目标对象( 轴线) 转折点的凹凸性 根据轴线当前结点处前后两个矢量的叉积来判断该点处的凹凸性，如图 3 7 河海大学硕士学位论文 如果轴线该结点当前侧( 如右侧) 为凹角，用前嚣两邻边平行线的交点生 成对应点，如图3 。1 3 所示。 步骤二：对上一步所产生的初始缓冲区边界进行失真现象校正。图3 1o 所 示的轴线面亨面上的节点c 所对应的缓冲区边界上c ，点，c 。点为丽、历的平 行线l ；、l ：的延长线上的交点，该点明显偏离了理想中的缓冲区边界，产生了尖 角，该尖角并不是我们所需要的缓冲区，所以必须对其进行校正。 ( 1 ) 因为生成缓冲区时只会在轴线上的凹侧产生失真现象，所以先判断轴 线上当前节点处的凹凸性( 两端端点除外) ，如图3 0 中的点c ，该处右侧角( 沿 轴线前进方向) 为凹毙，并产生了失真现象。 ( 2 ) 如果轴线上当前节点处该侧的焦为凹角，计算其夹焦程的大小，设该 节点相邻薅条边为l ；、l 。，其距离分别与夹角的一半的正切值的乘积为矧宰溉罢、 弛| 搴詈，比较缓冲区半径d 与矧橐锄詈、k | 毒纨詈的大小，假设矧毒纨詈小 于幸镪n 要，设可分为以下三类： 二 i ：o d 阶t a i l 要 当缓冲距d 小于两者中最小值时，轴线上当前节点对应的缓冲区边界上的 点3 是五、易分别对应的平行线段、如在线段内的交点。缓冲区边界上并没有 产生失真现象，所以并不需要校正( 如图3 1 4 所示) 。 图3 4 第i 类图3 5 第籍粪 池盼纽詈 阶钮詈 当缓冲距d 大于两者中最大值时，点3 为的延长线与乏延长线的交点， 点3 偏离了理想的缓冲区边界，产生了失真现象( 尖角) ，所以需要对萁进行修 正( 如图3 6 所示) 。转到( 3 ) 。 o 图3 1 6 第i i i 类 ( 3 ) 设i 为轴线上当前节点，i l 、i + 1 分别为当前节点的前个节点和后一 个节点。取i 点对应的初始缓冲区边界上的点( 因为当前节点处为凹侧，所以只 有一个点) ，将其编号为3 ；取点2 为i 一1 所对应的点集( 如图3 1 6 的弧段1 2 ) 中最后一个点：点4 为i + l 对威的点集( 如图3 1 6 的弧段4 亏) 中第一个点；如 果i l 节点该侧为凸角的话，取点l 为i 一1 所对应的点集中的第一个点，若为凹 角，点l 为i l 点前个节点所对应的点集中的最后一个点。如果i + l 节点为凸 角的话，取点5 为i + l 所对应的点集中的第一个点，若为凹角，点5 为i l 点前 一个节点所对疲的点集中的第一个点。此过程中轴线备节点所对应的点集为该点 所对应的缓冲区边界上的点集。 ( 4 ) 判断点2 、点4 分别位于i + 薹、卜薹节点对应弧段( 圈3 6 中4 5 、i 主) 的哪一侧，可知点2 位于孤段4 5 酶左侧，点也位于弧段i 2 的左侧。 ( 5 ) 对线段求交，删去初始缓冲区边界上的失真点i 调整局部缓冲区边界 p l 河海大学硕士学位论文 c a 坩a y 咀i n e n u m b e r ：存放边的数组 c g e o p o i n t s e t 赶r a y 氇_ p o i n t s e t 矗r r a y ：存放数据纛集戆数维 c g e 乩i n e p o i n t d a t 越r r a ym _ l p d a t a 舡r a y ：存放中心线上各个线段起点翔终点分别( 与中心线 垂直方向) 平移缓冲区半径的点 p u b l i c ： c g e o f e r 缱酬b l ed 鞠i s 专醵e e ，d 醐b l ed 鞠i s t 飘e e ，s 魏钟tn 静辫，i 狂tn s 酌躐舞) ： v i r t u a l v c g e o b u f f e r ( ) ： p u b l 主e ： b 0 0 lc r e a t e ( c p o i n t x 姆p p o i n t ，c r g n d a t a 却b u f f e r r g n ) ：创建点的缓冲区 b 0 0 lc r e a t e ( c l i n e d a t 8 却l i n e ，c r g n d a t a 却b u f f e r r g n ) ；剞热线的缓冲区 b 0 0 lc r e a t e ( c r g n d a t a 串p r g n ，c r g 曲a t a 姆b u f f e r 题n ) ：创建聪的缓冲区 b 0 0 lc o n v e r t p o i n t ( c p o i n t ) ( 1 f 母p p o i n t x y c d o u b l e p o i n t 牛p d d u p o i n t ) ：将p p o i n t ) ( 1 f 转换为 两。驻孙i 舞t b 0 0 lc o n v e r t p o i n t ( c d o u b le p o i n t 却d o u p o i n t ，c p o i n t x y 却p o i n t x y ) ；将p d o u p o i n t 转换为 妒o i n t ) ( j f b 0 0 lc a l c r o s s p r o d u c ti o n ( c p o i n t x y 印p o i n t ) ( 1 a ，c p o i n t ) ( 1 f 聿p p o i n t x y b ，c p o i n t x y 术p p o i n t ) 【y c ， d o u b l e 盎d c r o s s ) ：求得两条线盼叉袄，第一条线是a b ，第二条线是b c ，整个线豹方向势a b c b o o lc a l c r o s s p r o d u c ti o n ( c p o 主n t x y 堆p p o i n t x y a ，钟o i n t x y 奉p p o i n t x y 甄c p o i n t x y 宰p p o i n t x y c ， c p o i n t 】( 1 掌p p o i n t x y n ，d 删b l e 矗d c r o s s ) ：求褥两条线的叉积，第一条线是a b ，第二条线怒c d b le a 王e o n v e x o r e c 8 v e ：计舞 嚣点间鲍髭裹 b 0 0 lc a l f 0 0 t p o i n t ( c p o i n t ) ( 1 p p o i n t x 豫，c p o i n t ) 【1 f 却p o i n t x l b ，c p o i n t ) ( 1 p p o i n t ) 【1 g 渤i 斌) 【j f 轰勤髓弦i 魏专) ：求点e 巍直线撼鳇菱是 河海大学硕士学位论文 第四章多边形叠加及其特殊情况处理 4 1 多边形叠加概念 空间叠加分析( s p a t i a lo v c r l a ya n a l y s i s ) 是指在统一空间参照系统条件下，每 次将同一地区两个地理对象豹图层进行叠加，以产生空间区域的多重属性特征， 或建立地理对象之间的空间对应关系n 3 。 叠加分析也可以分为搬格与矢量嚣种，本文讨论矢量的叠加。叠加分析包 括点与多边形的叠加、线与多边形叠加以及多边形与多边形叠加。多边形之间的 叠加可以有合并、相交、相减、判别等方式。多边形之间的叠加分柝在计算视图 形上来说其实是多边形的裁剪，本文将只对其图形算法方面进行研究。 在计算机图形学中，有缀多经典的多边形裁剪算法如s 碰l 棚棚h 甜g 掇褫、 l i 觚g - b 删嫩”w d l * a t h 叭o n 等。但它们中间要么不能处理凹多边形，要么出 入点不易判断。近年来，虽然涌现了许多新的多边形裁剪技术，对以往经典算法 做了有益的改进，但是大多是以出、入点为裁剪依据，而这样的设计方式，会造 成：一是在生成结果多边形的过程中，会花费不必要的开销判断每个顶点的出、 入属性上m 1 ；二是对于提取最直接的结果多边形信息( 线信息而非点信息) 带来 一定的困难。因此如何设计一个可以避免上述阂题发生的算法就舜常重要，因此， 本文提出了面向对象的通用多边形裁剪算法。 4 2 面向对象的通用多边形裁剪 4 2 1 基本思想 面向对象的通用多边形裁剪算法的基本思想是对主多边形与裁剪多边形求 交点并记录( 主多边形为被裁剪的多边形，裁剪多边形为裁剪区域) ，判断这些 交点的有效性，然后根据交点和顶点集组成扩展边，最后通过交点的相交线段的 索引来联立结果多边形。算法基本思想来源于这样一个事实：多边形的唯一性取 决于两个基本条件，即顶点坐标的唯一性与顶点顺序排列的唯一性。 河海大学硕士学位论文 b l ( 助 一 玛b ：i 图4 1 多边形裁剪 以图4 。| l 所示的两个多边形为例。实线代表多边形a ( 顶点为氩， i _ 1 ，2 ，1 2 ) ，虚线代表多边形b ( 顶点为b ；，i = 1 ，2 ，7 ) ，多边形a 中有一 个洞( a 旗a ，a ；，a ，0 。对多边形a 和b 进行裁剪。把每个多边形看成是由一组闭 合线组成的，并对每条闭合线作如下规定，非洞闭合线称之为父线，其项点按逆 时针排列；洞闭合线称为子线，顶点按顺时针排列。两个多边形在相互叠置后， 各被切分为若干个边段，称之为扩展边。如多边形a 就被分为c 。眦吣c 2 ，c 。g ， c a a ，c 4 a 。a 成c l ，c “嵫。c 6 ，雠，g 六个扩展边，多边形b 被分为 c 。b 函。b s c 。、c 。8 。、c 3 b ，e 。、c 。c ；、c 5 b 舷、c 粑；六个扩展边。两对于a 的每 扩展边，都可以在b 中找到首点与该扩展边末点重合的唯一扩展边，称之为a 扩展边在b 中的相接扩展边，同样，对于b 的每一条扩展边，都可以在a 中找 到首点与该扩展边末点重合的唯一扩展边，称之为b 扩展边在a 中的相接扩展 边。 多边形运算主要有多边形相交、合并以及补等运算方式。 ( 1 ) 两个多边形的相交运算： 在多边形a 的扩展边组中任选位子多边形b 内的一条扩展边，然后从该扩 展边出发，寻找其在b 中的相接扩展边，再选取在a 中的相接扩展边，以此类 推，不断寻找在对方多边形中的相接扩展边，当回到起始扩展边时，便得到了结 果多边形的一条父线。 ( 2 ) 两个多边形的合并运算： 在多边形a 的扩展边组中任选位于多边形b 外的一条扩展边，然后扶该扩 展边出发，寻找其在b 中的相接扩展边，再选取在a 中的相接扩展边，以此类 河海丈学硕士学位论文 推，不断寻找在对方多边形中的相接扩展边，豢回到起始扩晨边时，便褥到了结 果多边形的子线或父线。它的运算方式几乎与相交运算雷同。不同之处仅在于， 驮a 选择的超始扩展边在多边形b 外。 ( 3 ) 单个多边形的补运算： 若是以一预知全集求多边形的补，则只需先将该全集范围的边界线俸为父 线加入到一个存放结果的新空多边形中，再“翻转”组成原多边形的线，即原多 边形的父线变为予线，子线变为父线，翔入到耨多边形中。 算法得以实现的本质在于充分利用了多边形中洞与非洞闭合线的方向性， 如图4 。i l 所示，几乎是完全顺着线的方南走，就完成了多边形的裁剪。 4 2 2 算法实现 以图4 。1 所示的两个多边形为例，对其进行裁剪，主要分为以下几步： 步骤一：对多边形顶点进行重新排序。父线的顶点按逆时针进行排序，子 线的顶点按顺时针进行排序。多边形顶点数据酋尾重合即闭合。多边形a 的顶 点为a 。、a 。a 。，多边形l i i 的顶点为b 。、b b ，。 步骤= ：对单个多边形求补运算。如果做其他运算，则跳过此步，执行步 骤三。若求多边形的补集则只需先将该全集范围的边界线作为父线加入到个存 放结果的新空多边形中，再“翻转”组成原多边形的线，即原多边形的父线变为 予线，子线