（精密仪器及机械专业论文）矢量图形裁剪算法在土地调查信息处理中的应用(精密仪器及机械专业优秀论文).pdf

东南大学硕上论文 摘要 通过对地理信息系统( g i s ) 和目前实际土地变更调查方法的研究，构建以矢量图形 及图形裁剪技术为核心的土地变更调查数据更新系统；提出了土地变更调查数据更新中 的几个关键问题的解决方案，实现了土地变更调查外业采集的g p s 高精度数据与各种原 始底图数据在内业g i s 平台上的大批量、自动化变更，从而实现土地变更调查数据更新 方法的变革。 本文研究主要内容集中在以下几方面： 1 、针对w e i l e r - a t h e r t o n 算法在特殊情况下失效问题，提出了广义出、入点概念和 改进算法的解决方案。 2 、采用外接矩形过滤技术、双缓冲技术和道格拉斯普克( d o u g l a sp e u c k e r ) 压缩 算法，实现了海量地图数据的快速显示。 3 、在矢量图形裁剪算法基础上设计了自动更新方法，不仅能正确计算、输出几何实 体数据，而且还可以对属性信息做相应的更新，保证了数据的正确性和现势性，避免了 手工添加、更改属性信息带来的错误。 4 、基于0 g cs i m p l ef e a t u r es p e c i f i c a t i o n ( 简单特征规范) 空间数掘模型的土地 调查数据更新软件的设计与实现。 关键字：土地变更调查、g i s 、计算几何、矢量图形裁剪、w e i l e r a t h e r t o n 算法。 东南人学硕上论文 a b s t r a c t i nt h ep r o c e s so f t h er e s e a r c ho f t h eg i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) a n dt h ec u r r e n t m e t h o do fl a n ds u r v e yi np r a c t i c e ，w ee s t a b l i s h e dl a n ds u r v e yu p d a t i n gs y s t e mb a s e do n v e c t o rg r a p h i c sa n dg r a p h i cc l i p p i n gt e c h n o l o g ya n dc o m eu p 、而t l lt h es o l u t i o no fs e v e r a lk e y p r o b l e m si nl a n ds u r v e yu p d a t i n gp r o c e s st or e a l i z ea u t o m a t i cu p d a t i n gl a r g eq u a n t r i e so fg p s h i 吐p r e c i s i o nd a t aa n do r i g i l l a lm a pd a t ao ng i sp l a t f o r m 1 1 l er e s e a r c hc o n t e n t sa r es u m m a r i z e d 嬲f o l l o w s ： 1 b e c a u s co fw e i l e r - a t h e r t o o na r i t h m e t i ci n v a l i d a t i o ni ns p e c i a li n s t a n c e t h ec o n c e p to f g e n e r a li n o u tp o i n ta n d a d v a n c e da r i t h m e e t i ca r ci n t r o d u c e d 2 a d o p tt e c h n o l o g yo fo u t s i d er e c t a n g l e ，d o u b l eb u f f e ra n dd o u g l a sp e u e k e r t od i s p l a y g r e a td e a lo f m a p d a t ar a p i d l y 3 d e s i g na u t ou p d a t i n gm e t h o db a s e do ng r a p h i cc 1 i p p i n ga r i t h m e t i c i tc a nc o m p u t e c o r r e c tg e o m e t r yd a t aa n du p d a t ec o r r e s p o n d i l l ga t t r i b u t ei n f o r m a t i o nt og u a r a n t e ec o r r e c t n e s s a n ds y n c h r o n i z a t i o nw h i c ha v o i de r r o rf r o mm a n u a le d i ta t t r i b u t ei n f o r m a t i o n 4 d e s i g na n dr e a l i z et h el a n ds u r v e yd a t au p d a t i n gs o f t w a r eb a s e do no g cs i m p l e f e a t u r es p e c i f i c a i o ns p a t i a ld a t am o d e l k e yw o r d s ：l a n ds u r v e y , g i s ，c o m p u t a t i o n a lg e o m e t y , v e t c o rg r a p h i c sc l i p p i n g ，w e i l e r - a t h e r t o nc l i p p i n ga r i t h m e t i c i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 研究生签名： 盈遵日期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办 理。 研究生签名：盈：匙导师签名： 聃螳。 东南大学硕士论文 第一章绪论 1 1 土地调查 1 1 1 背景2 1 土地是人类生存、发展的基础，也是立国安邦的基本要素。查清土地资源状况，并作出 科学评价，对加强国土资源规划、管理，保护与合理利用，保障整个国民经济持续，快速、 健康发展，具有十分重要的意义。1 9 8 4 年，国务院部署在全国全面展开土地资源调查工作， 以县为单位统一组织力量，严格按照全国统一的技术规程和土地分类标准，进行外业调查和 内业工作。在分批开展和完成全国各县调查任务的基础上，1 9 9 6 年又完成了一次统一时点 的变更调查。全国土地资源调查是一项具有重要意义的国情、国力调查，是一项复杂、浩大 的系统工程。查清了我国农村土地的权属界线、各个地块的面积和用途；各个乡( 镇) 、县、 地( 市) 、省和全国土地的类型、数晕、分布、利刚雨i 权属状况。 目前，土地调查的成果已在政府和部门规划、计划，土地管理，农业普查、行政勘界、 工程建设等方面得到广泛应用，为编制国民经济和社会发展计划、制定有关政策、科学决策 等提供了重要依据。 1 1 2 土地调查的内容嘲 土地管理法实施条例第十四条规定，土地调查包括土地权属调查( 地籍调查) 、土 地利用现状调查、土地条件调查和土地利_ h j 动态监查。土地调查正是针对土地的自然属性( 面 积、位置、形状、适应性条件等) 和社会属性( 权属、价格、等级、其它经济关系和法律关 系等) ，及其变化情况和趋势的调查，并将其合理组织和表达，为土地管理和资源配置服务 的一种活动。实质上，调查与土地有关的任何性质的活动，都可以纳入土地调查的范畴中。 本文研究的主要是土地利用现状调查，它包括以下内容： 1 ) 地类的变化。地类的调查统计是土地利h j 现状调查的基本内容之一。地类的变化是 指土地的用途或利用方式发生了变化。 2 ) 图斑的变化。图斑的变化是土地利用变化中十分普遍的现象。行政境界和权属范围 的变动、地类的变化等，通常是以十地界线的推移来实现。图斑的变化存在着一个i 到斑的规 模大小范围的变化，也存在着某图斑消失或者增添一些新图斑的现象，即出现图斑间的合并、 分割、增加、消失以及其他方式的变化。 3 ) 权属的变迁。土地权属是土地所有或使用的法律权力标志。土地权属的变化常常都 伴有土地用途( 即地类) 的变化和地类i 劐斑的变动。 4 ) 行政境界调整。行政境界有时从发展区域经济和管理工作的需要出发，会作适当调 整。行政范嗣的分割和合并，也包含着土地利用其他方面( 如地类、图斑等) 的变化。 5 ) 飞地、争议地的变化。 6 ) 单位更名的变化。 1 2 国内外研究现状 1 2 1 国外土地调查的现状乜羽 土地是人类赖以生存和发展的不可再生的资源，土地资源是国土资源重要的组成部分。 先进发达国家和有关国际组织十分重视土地资源和土地利_ e l j 的动态监测。 英国土地利用调查与制图工作开展最早，于1 9 3 0 年成立土地利用调查所。1 9 3 1 年开始 东南大学硕士论文 第一次土地调查，历时十多年。对全国土地利用情况和沿革变化情况进行摸底清查，把全国 土地划分为六类，主要是农业用地并绘制1 ：1 0 万的地图。1 9 6 0 年又开展第二次土地调查， 土地利用划分1 2 个类型。6 0 年代后期。当时的土地管理局绘制l ：6 5 0 0 0 英格兰和威尔士 土地分类图，并对土地资源进行了综合评价。英国进行的土地调查和土地分类评价工作，为 合理利用土地起到了十分积极的作用。 澳大利亚全国性的土地调查研究始于1 9 4 6 年，成立全国土地调查小组，对全国土地资 源进行详细勘查，划分并制定了土地利用分类图。近年来土地利用调查主要是在澳大利亚南 部进行环境调查。特点是强调土地生态问题。更广泛的为土地利用规划服务。 美国土地利用调查工作开展比较早，在1 9 3 4 年进行了以土壤侵蚀度为中心内容的土地 利用调查。1 9 3 7 年又开展了土地调查，制定了土地保护计划方案，把土地按适宜性分为8 级。7 0 年代以来，美国国内土地调查计划在遥感技术的推动f 蓬勃展开，1 9 7 2 年在遥感技 术支持下形成的地质测量局土地利用、土地覆盖分类方案，结束了美国土地利用调查长期以 来没有统一分类系统的局面。此后，美国大量利用信息技术和自动化技术编制1 ：1 0 万和l ： 2 5 万的土地利用例和土地覆盖图。 1 2 2 国内土地调查的现状“” 我国的土地利用现状调查包括：一次详查、变更调查、更新调查。一次详查是指上个世 纪8 0 年代在全国范围开展的土地资源调查。变更调查是在已有调查成果的基础上，对利用 状况发生变化部分的土地进行信息更新。更新调查抛开已有调查的成果，重新开展的土地资 源调查。其中，变更调查最为频繁，因为一个地块的用途、形状随时都可能发生变化，为了 掌握每个地块的利用现状，需要经常地进行变更调查。 在我国，土地利用现状变更调查采用的方法大致分为两步：外业调查、内业转绘。 外业调绘是在多种图件资料上进行的，如晒印航片、放大航片、彩红外片、相片平面图、 影像平面图，卫星像片、线划地形图等。地类调绘的过稃实际分成两个阶段，第一阶段确定 所摄物体的内容，为此细致地研究航空像片；第二阶段着墨整饰，即对每一个地物选择相应 的图式符号( 相麻的地类代号) ，并按相应的细则和编辑指示书的规定，绘地物于航片的影 像上。这就要求工作人员持像片赴实地进行野外核对调查，识别像片上各种影像所反映的地 物内容，根据用途要求进行适当的综合取舍，并调注和虽测有关地理名称及必要的数据，然 后按规定的图式符号以不同的颜色在室内进行着墨和整饰。 土地变更的转绘一般都在复制的土地利用现状图上进行修测，而后用红色蒙绘剑新的土 地利用现状图上的。在用航片进行外业调绘的情况下，需要通过转绘工作来修正图件。转绘 方法较多，可以分成两大类：一是纠正转绘，使用的技术方法有：图解法、仪器法、航片数 字化转绘( 计算机) 、卫片图像计算机处理等；二是转描( 蒙绘) 。 综观传统的土地变更调查方法：使j j 平板仪、皮尺等测定变更数据，不仅需要投入大量 的人力物力，技术手段落后，而且调有数据的精度不能保证；变更数据的精度很大稃度上依 赖于调查底图，并且在转绘或蒙绘过程中又一次降低调商数据的精度；土地变更调杏的具体 步骤繁多，使得调查周期很长。总而言之，在科技日新月异的今天，仍采用传统的土地变更 外业调查方法时效太慢，已不能满足现代土地变更调查的需要。 近年，多种调查方式和技术在土地调查中得到应用。各国普遍把全面土地调查方式和非 全面土地调查方式结合起来使用。科学技术的进步，使新技术在土地调查中逐步得到应用， 航空遥感、卫旱遥感特别是二十世纪末新兴起来的地理信息系统( g i s ) 技术使土地调查越 来越便利，数据越来越精确。 2 东南大学硕士论文 1 3 本论文的研究内容和组织结构 根据土地调查的实际情况，本文重点将讨论土地调查数据更新系统的原理、构架、设计 和实现。该系统是一个矢量图形系统，其研究内容包括：空间地理信息数据库、矢量图形系 统设计、矢量图形变更技术、图形快速显示技术、自动更新技术等。其中关键技术是矢量图 形裁剪算法和土地调杏数据更新软件( 该软件是一矢量图形系统) 的设计与实现。本文讨论 了针对矢量图形裁剪的改进算法，并采用改进算法在现有底图的基础上对外业g p s 采集的 数据进行分割、更新和输出等操作。为了快速显示海量地图数据，本文讨论了外接矩形过滤 技术、双缓冲技术和道格拉斯普克( d o u g l a sp e u c k c r ) 压缩算法在图形显示中的应用和实现 方案。为了减轻内业土地调查更新工作的负担、提高工作效率、实现全自动化更新，在矢量 图形变更技术的基础上设计并实现了自动更新技术；自动更新技术不仅能正确计算、输出了 几何实体数据，而且还可以对属性信息做相应的更新，从而保证了数据的正确性和现势性， 避免了手工添加、更改属性信息带来的错误。在软件设计和实现过程中，完全根据软件工程 理论和面向对象设计思想进行开发，并且根据o g cs i m p l ef e a t u r es p e c i f i c a t i o n ( 简单特征 规范) 设计了空间数据模型。 本文的框架：首先介绍土地调查，包括第一章。第二章介绍矢量图形计算几何理论，包 括：矢量的概念、算法，线段求交，多边形求交和一些著名算法。第三章研究了矢量图形裁 剪算法，对w e i l e r - a t h e r t o n 裁剪算法做了介绍并且分析了该算法失效的问题，在此基础上提 出了改进算法；同时分析了改进算法在特殊情况下的处理、实现、对岛状图形的处理以及线 段与多边形裁剪算法。第四章讨论了土地调查数据更新软件的设计与实现，分为：1 ) 土地 调查数据更新软件设计与开发；2 ) 土地调查数据更新软件中的关键技术。最后，介绍了该 软件在北京大兴区土地变更调查中的应用和成果，并做了展望。 3 东南大学硕士论文 第二章矢量图形计算几何理论 2 i 引言n 儿幻 1 9 7 5 年s h a m o s ( 沙莫斯) 和h o e y ( 霍伊) 利用计算机有效的计算平面点集的v o r o n o i 图， 并发表了一篇著名的论文，这标志着计算几何的诞生。作为计算机科学的一个分支，计算几 何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、地理信息系 统、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分广泛的应用。 本章将简单介绍与矢量图形相关的计算几何理论与方法，包括：1 ) 基本定义；2 ) 矢量 概念及运算；3 ) 线段与线段求交；4 ) 判断点是否在多边形中；5 ) 线段集求交算法；6 ) 多 边形求交算法。 2 2 基本定义 本章研究的对象是欧几里得空间的点集，包括点、直线、线段以及由有序点确定的多边 形。 用e d 表示d 维欧几里得空间，即实数x 0 = 1 ，2 ，3 d ) 的d 元组( ) ( 1 ，x 2 ，x 3 x d ) 的空间。 本章中讨论的几何实体都是在二维空间下的，下面给出基本几何实体的定义。 1 ) 点。用p 表示一个点，在e d ( d 维欧氏空间) 中点p 定义为一个d 元组( x 1 ，x 2 ，x 3 x d ) 。 点p 也可解释为有d 个分量的向量，此向量为起点为原点，终点为p 的向量。在二维空间中 可以表示为p ( 】( ，y ) 。 2 ) 线、线性簇。在e d 中给定两个不同的点p ，胁；两个点的线性组合： 印1 + ( 1 一印2 ) r ) ( 2 。1 ) 是e d 中一条直线。如果给定e d 中k 个线性独立的点内，见籼o 【d ) ，则线性组合： 盯i p l + 口2 p 2 + + ( 1 一盯l 一一口t 一1 ) p i( 盯，r ) ( 2 2 ) 是e d 中的( k - 1 ) 维的线性簇。 3 ) 线段。在e d 中给定两个不同的点朋，见，若在公式( 3 - 1 ) 中加入限定条件o a 1 ， 则得到p l 和胁凸组合，它描述了连接两点的直线段，记为：p l p 2 。 4 ) 凸集。设d 是e d 中的域，p 1 和见是d 中任意两点，如果线段a p 2 完全包含在d 中，则域d 是凸的。 5 ) 多边形。多边形定义为线段的有限集合，该集合中每条线段的端点恰好为两条边所 共有，而且没有边的子集具有这个性质。线段为多边形的边，其端点是多边形顶点，而且顶 点数和边数相等。 若多边形不相邻边不相交，则称该多边形为简单多边形。简单多边形把平面划分为两 个不相交的区域：内部区域( 有界的) 和外部区域( 无界的) 。一般情况下，多边形理解为 边界和内部区域的并。 2 3 矢量概念及运算 2 3 1 矢量的概念 如果一条线段的端点是有先后次序之分的，我们把这种线段称为有向线段( d i r e c t e d 4 东南大学硕士论文 s e g m e n t ) 。如果将有向线段起点平移至坐标原点，我们就把它称为矢量( v 配。如图2 - 1 ， 有向线段p 忱的起点p l 为坐标原点，则记为矢量见。 2 3 2 矢量运算法则嗍 j p 2 暴 。 p 1 o x 轴 图2 - i 矢量概念 1 、矢鼍加减法 设二维矢量p = ( 1 i y 1 ) 、q = ( x 2 ，y 2 ) ，则矢量加法定义为：p + q = ( x 1 + x 2 ，”+ y 2 ) 同样的，矢量减法定义为：p q = ( x l x 2 ，y l - y 2 ) 。显然有性质p + q = q + p ，p q 2 一( q n 。 2 、矢量义积 设矢鼍p = ( x i 。y 1 ) ，q = ( x 2 ，3 1 2 ) ，则矢量叉积定义为由原点( 0 ，0 ) 、p 、q 和p + q 所 组成的平行四边形的带符号的面积。即：p q = x 1 + y 2 - x 2 * y 1 ，其结果是一个标量。显然有 性质p q = 一( q p ) 和p x ( - q ) = 一( p q ) 。 叉积有一个非常重要性质：通过它的符号判断两矢量相互之间的顺逆时针关系： 若p x q o ，则p 在q 的顺时针方向。 若p x q 0 ，则p 妒l 在p l 点拐向右侧后得到p 胁 若( p 2 - p o ) x ( p l - p o ) = 0 。 同理判断q i q 2 跨立p i p 2 的依据是：( q 1 - p 1 ) ( p 2 - p 1 ) ( p 2 一p 1 ) ( q 2 - p 1 ) = o 。 具体情况如表2 - l 所示： 表2 1 快速排斥试验和跨立试验 通过快速排斥试验未通过快速排斥试验 p 2 潞 通过跨立试验 爷 i 2 雏7 l 0 2 0 1 p 2 p l 、 未通过跨立试验 ，q 2 隈 、 p i q i q 2 、对两线段求交点 设两线段端点分别为a 、b 、c 和d ，记为：l 女和l c d 。通常计算两线段交点的方法是利 用l 和l c d 的斜截式方程联立求解。这里我们利用参数方程替代斜截式方程表示两线段， 这样看起来更加直观。 设a = b a 、c = d c ，则l a b 上任何一个坐标点可以表示为：p ( s ) = a + s a ，这个方程 就被称作线段l 女的参数方程；当s = 0 ，s = l 和s = l 陀时：g o ) = a ，p ( 1 ) = a + a = a + b a = b ，p ( 1 2 ) = ( a + b ) ，2 。在s 0 ，1 时p ( s ) 代表线段l 女上所有点。 同样，线段l c d 的参数方程为：q ( 0 = c + t c ，t 0 ，1 。要求两线段的交点，可以令p ( s ) = q ( t ) ，即：a + s a = c + t c 。我们将s 、t = 0 和1 代入方程经计算可以求得s 和t ： s = a 0 ( d l - c 1 ) + c 0 ( a l d 1 ) + d o ( c 1 一a 1 ) d( 2 - 3 ) t = a 0 ( e l b 1 ) + b o ( a 1 一c 1 ) + c 0 ( b l a 1 ) d( 2 4 ) d = a 0 ( d l - c 1 ) + b 0 ( c l d 1 ) + d o ( b l a 1 ) + c 0 ( a 1 一b 1 )( 2 5 ) 上面三个式子中当d e 0 时( 2 - 3 ) 、( 2 - 4 ) 两式有效，可以计算。当且仅当d = 0 时，两线 段平行。当两线段平行时，线段有可能相交也有可能不相交，必须对这种特殊情况处理。 当两线段平行时，有以下三种情况：两线段不相交，一点相交和部分重合。首先判断两 直线段是否为竖直线，如果为竖直线： 1 ) 若两竖直线横坐标不同，则两竖直线不相交。 7 东南大学硕士论文 2 ) 若两竖直线横坐标相同，第一条直线的起始点和第二条直线结束点相同或者第一条 直线的结束点和第二条直线的起始点相同，则两竖直线交于一点。 3 ) 否则两线段重合。且交点为纵坐标最大的起始点和最小的结束点。 如果两直线段都不是竖直线，首先判断两直线段横坐标是否重叠。如果不重叠则表明两 直线段不相交；如果重叠，求重叠区间中一横坐标f 两直线段的纵坐标，若纵坐标不同，即 两直线段平行；若纵坐标相同，即两直线段重合。当两直线段重合时，计算横坐标撮大的起 始点和晟小的结束点，若起始点和结束点横坐标相同，则交于一点；否则重合在起始点与结 束点之问。 2 5 判断点是否在多边形中1 在矢量图形系统中，经常需要选取多边形，判断多边形空间关系，进行多边形裁剪等操 作，这些操作的基础就是判断点是否在多边形中的算法。这里介绍两种判断点是否在多边形 中的算法：回转数法( w i n d i n gn u m b e o 、射线法( r a yc m s s i n g s ) 。 2 5 1 回转数法( w i n d i n gn u m b e r ) 回转数法是一种很直观的判断点在多边形中的算法。设有：任意多边形p 和点q 。假设 自己站在q 点去观察多边形p 上的每一个顶点。沿着多边形p 顶点序列观察，转动一定的 角度保证自己每次都正对所观察的多边形顶点。逆时针方向转动角度为正，顺时针方向转动 角度为负。当遍历多边形p 所有顶点后，如果转动的角度累加为2a ，说明q 点在多边形内； 若角度累加为0 ，则说明q 点在多边形外。 回转数法需要浮点运算，特别是三角计算，这导致了算法比下节将要介绍的射线法慢得 多。h a i n e s 在1 9 9 4 对这两种算法作过比较，前者比后者慢大约2 0 倍。 2 5 2 射线法( r a yc r o s si n g s ) 设：任意多边形p 和点q 。 射线法的主要思想是：从q 点引一射线r ( 任意方向) ，这里为了方便计算我们取x 轴 正向。计算射线r 与多边形p 的交点个数。交点个数为奇数，则点在多边形内；交点个数 为偶数，则点在多边形外。 如图2 - 3 所示，过点1 ( q 1 ) 引一条x 轴正向的射线，先后与边v 1 7 - v 1 8 ，v 1 6 v 1 7 和v 1 2 - v 1 3 相交，交点个数为3 ( 奇数) 。因此可以判断q l 在多边形p 内。对于点2 ( q 2 ) 穿过边v 2 3 一v 2 4 和v 1 2 - v 1 3 ，交点个数为2 ( 偶数) ，因此可以判断q 2 不在多边形p 内。 8 东南大学硕士论文 o 图2 - 3 射线法( r a yc r o s s i n g s ) 虽然射线法的思想很简单，但是在某些特殊情况下还是必须做一定处理。例如：图2 3 中点3 ( q 3 ) 和点4 ( q 4 ) g t 是属于与多边形顶点相交和与多边形边重合的特殊情况。针对以上特 殊情况，下面对射线法作一定的改进。 在计算交点个数时，与射线r 相交的边必须满足：其中一个顶点严格在射线r 的上方， 另一顶点在射线r 的上方或者下方。只有满足了这一限制条件才累加交点个数。如图2 - 3 中的q 3 ，多边形p 的边v 1 一v 2 、v 2 v 3 不计数，v 6 - v 7 、v 7 v 8 与q 3 引山的射线相交，交点数 累加，v 3 v 4 、v 4 v 5 不计数，v 5 v 6 、v l o v l l 和v l l - v 1 2 计数，总共有5 个交点，因此q 3 在多边形p 中。 在实现该算法过稃中，先对多边形p 作个变换。将q 点移至坐标系原点，这样由q 点 引出的射线就是x 轴。这样我们只要判断多边形p 的每条边是否“跨越”x 轴，如果多边 形的边“跨越”x 轴，则只要计算y = 0 时的坐标值就可以计算出交点。设( k 1 ，y i 1 ) 和随，y 。) 为边e 的两端点，令y = 0 可以由式2 - 6 计算出交点坐标( x , y ) 。 y y 1 = ( x x t - 1 ) ，- y , - 1 ) ( 一一t - 1 ) ( 2 - 6 ) 对于点4 ( q 4 ) 只要判断多边形边的顶点是否与待判断点相同，若相同则可以判定点在多 边形边上。 2 6 1 概述 2 6 线段集求交算法 所谓线段集就是线段的集合，本节中仅讨论二维情况下线段集求交；即：对平面上n 条线段，确定其中任意两条线段是否相交，如果相交m 求出交点。由于多边形可以看成平面 上迮续线段的集合，所以多边形是否相交问题就可以装换为线段集是否相交问题。 对于平面上n 条线段，分别检查每两条线段是否相交可以确定n 条线段中哪些相交并求 9 东南大学硕士论文 出交点。这种方法最简单，总共计算n ( n i ) 2 次，时间复杂度为0 ( n 2 ) 。耗费时间过多，因此 需要新算法。 1 9 7 9 年，b e n t l e y - o t t m a n n 提出了基于扫描线的判定线段相交算法。下面就这一算法作 简要介绍。 2 6 2b e n t l e y - o t t m a n n 算法1 1 幻 b e n t l e y - o t t m a n n 算法思想是利用扫描线判断线段是否有可能相交，只对有可能相交的 线段求交。算法想象移动y 轴，从左到右扫过所有线段，在某些事件点求交。 l 、算法思想 平移y 轴可以对所有线段建立全序关系。该次序关系仅以三种方式变化： 1 ) 若扫描线遇见线段s 的左端点，则将线段s 加入序列中。 2 ) 若扫描线遇见线段s 的右端点，则将线段s 从序列中删除。 3 ) 若扫描线遇见线段s l 与线段s 2 的交点，则在序列中将s l 和s 2 交换位置。 如果两线段s 1 和s 2 相交，当移动扫描线接近s 1 与s 2 交点横坐标时，s 1 和s 2 将会成 为序列中相邻的两线段。不需要检查每条线段是否与其它线段相交，只需要检查序列中相邻 线段是否相交即可。 2 、基本数据结构 b e n t l e y - o t t m a n n 算法使用了两个基本数据结构：事件点进度表( e p s ：e v e n tp o i n t s c h e d u l e ) 和扫描线状态( s l s ：s w e e pl i n es t a t u s ) 。 扫描线状态( s l s ) 是线段的一个序列。在平面x 坐标的有限集内变化。显然，扫描线状 态( s l s ) 数据结构t 一定要支持以下操作： 1 ) i n s e r t ( s ，t ) ，表示将线段s 插入序列t 保持的全序关系。 2 ) d e l e t e ( s ，n ，表示从t 中删除线段s 。 3 ) a b o v e ( s ，n ，返回序列t 中s 上面一条相邻线段。 4 ) b e l o w ( s ，n ，返回序列t 中s 下面一条相邻线段。 为实现扫描线状态( s l s ) 这种数据结构，我们选择采用平衡二叉树。这样实现i n s e r t 和d e l e t e 操作的时间与存储的数据个数的对数成比例。 事件点进度表( e p s ：e v e n tp o i n ts c h e d u l e ) 包括线段左右端点和线段交点的x 坐标。当 开始扫描平面时，一定要保持全序关系，这种关系仅在线段两端点和交点处发生改变。为了 找到所有交点，事件进度点数据结构e 必须支持以下操作： 1 ) m i n ( e ) ，确定e 中最小元素，并删除之。 2 ) i n s e r t ( x ，d ，将x 插入由e 保持的全序序列中。 3 ) m e m b e r ( x ，e ) ，确定x 是否为e 中一个成员。 数据结构e 仍旧采用平衡二叉树，因此上面三种操作耗费对数时间。 3 、算法实现 建立数据结构a 存储相交的直线段，a 中每一个元素都是一个直线段对。例如：( s 。， s j ) ； 变量声明： a ：直线段对存数据结构； e ：事件点进度表； t ：扫描线状态： 算法流程图( 图2 - 4 ) ： 1 0 东南大学硕上论文 图2 - 4b e n t l e y - o t t m a r l n 算法流程图 2 7 多边形求交算法嘲儿u 1 本节介绍多边形求交算法，分为凸多边形和一般简单多边形求交算法。对于凸多边形求 交主要介绍三种基本算法和一种基于扫描线的求交算法。对于一般简单多边形求交介绍一种 由凸多边形扫描线算法改进的求交算法。 本节中主要讨论的是如何对多边形边求交点，而计算多边形交集采用了轮流输出多边形 边界的方法。这种方法有很大的缺陷，在下一章中会详细介绍多边形求交集的方法以及针对 其缺陷提出的改进算法。 东南大学硕上论文 2 7 1 凸多边形求交 p 、q 是平面上给定的两个凸多边形：p = 舻，p 2 ，西 和o = g pq 2 ，钿 a 多边形项点按逆时针方向排序，p 和q 的交集记为：p n q = 口q e - pa 口讲。很显然两 个凸多边形的交一定也是一个凸多边形，p 、q 分别有n ，口个顶点，那么p a q 至多有日+ 口个顶点。而且p g q 的边界由p 边和q 边的交错序列构成，p 与q 的交点又恰好是p n q 的 边界序列p 边与q 边交错之处。 2 7 1 1 三种基本求交算法 1 、依次检查每条边，求p n q 算法 对p 的每条边依次检查q 的所有边，判断是否相交，如果相交求出交点。然后轮流输出 交点处p 、q 边构成p n q 的边界。其时间复杂度为d 向一 2 、梯形交组成p n q 算法 算法步骤如下： 步1 ：将p ，q 顶点按x 坐标分类。 步2 ：过四，o ( i = 1 ，2 n ，j = 1 ，2 m ) 作垂直于x 轴的直线，形成数目不超过n + m 一1 个长条域。 步3 ：对每条长条域计算两个梯形各项点和两个梯形的交，记为讯。注意：有的长条域 中只有一个梯形或一个三角形。 步4 ：计算p n q = u w 。 一般情况下，有n + m 一1 个长条域，处理每个长条域为常数时间，如果不计分类时间，则 算法时间复杂度为口白切，。若考虑分类时间，则时间复杂度为口r 白十l o g 囟十，。 3 、沿p 边或q 边寻找p n q 的算法 算法思想如下：开始任选一条边，如选q 中一条边行进。当q 的现时边上已找到一个 交点时，改沿p 边上行进；当p 的现时边找到一个交点时，改沿q 边上行进：如果p 的现 时边上所有交点都已找到，而q 的现时边上还有交点没有找到，则在p 边上进行。最后利 用第一个算法求出p n q 。 该算法循环次数为2 ( m + n ) 次，每次循环耗费常数时间，因此时间复杂度不超过d 伽+ 砂。 2 7 1 2 基于扫描线的求交算法 可以利用2 6 2 节所描述的b e n t l e y - o t t m a n n 算法判断多边形中线段是否相交。考虑到多 边形的一条边的右端点同时又是另一条边的左端点，因此只需在插入边时进行判断，在删除 边时不必进行判断。而且扫描线至多碰到4 条线段。所以将算法作一定改进，伪码如下： 将p 的顶点放入e 1 ，q 的顶点放入e 2 。 w h i l e ( e l 不为空a n de 2 不为空) p m i n ( e 1 u e 2 ) ； 取e l 和e 2 中最小x 坐标煮 i f ( p 为左端点) s - p ；我虱p 是端点的线段 东南大学硕上论文 i n s e r t ( s , d ； s i - a b o v e ( s 1 ) ； s 2 - b e l o w ( s ，n ； i f ( s l 和s 相交) 求交点。 i f ( s 2 和s 相交) 求交点。 ) i f 礤为右端点) s - p ：搠j p 是端点的线段 d e l e t e ( s ，n ； 从点m a x c m i n ( e 1 ) ，m 1 n 2 ) ) 出发，用上一小节所描述的方法求p nq 。 利h ；i 扫描线算法计算多边形交，每边只插入一次，删除时不需要对边进行处理。而交点 个数最多m + n 个，所以其时间复杂度为d 卸+ 圳。 2 7 2 一般简单多边形求交 一般简单多边形( 任意简单多边形) 求交，可以是两个凸多边形也可以是两个非凸多边 形，在或者是一个凸多边形和一个非凸多边形。对简单多边形我们仍旧可以采用扫描线算法 进行求交，只是因为一般多边形情况更为复杂必须对算法进行改进。 下面简单介绍一下改进的思想：对于简单多边形，每次扫描剑的事件点n 可能是一条 边的左端点也可能是两条边的左端点；事件点研可能是一条边的右端点也可能是两条边的 右端点。因此在凸多边形求交的算法中增加：与p ，所关联的为一条边还是两条边的判断， 判断方法如下： 当满足：p i + 1 j p j j p ，i j 时，昴为左端点只关联一条边。 当满足：只j $ 3 - $ 4 - s 5 s 6 - s i ，裁 剪多边形p c 方向与p s 方向相同：c 1 - c 2 - c 3 - c 4 - c 5 - c 6 - c 1 。图中交点标记为：i l 、 1 2 、1 3 ，1 7 ：其中1 2 是s 3 一s 4 边与裁剪多边形的交点，从图中可以看出从s 3 出发经过1 2 到达s 4 是从裁剪多边形外部到其内部的一个过程，因此1 2 是对于裁剪多边形p c 的入点； 对于交点1 7 ，是$ 5 - $ 6 边与p c 的交点，经过1 7 边s 5 一s 6 从多边形p c 的内部到达外部，因 此1 7 为出点。 1 5 东南大学硕士论文 s l s3(湛 辆 图3 - 1 入点和出点定义 3 2 2 算法主要思想和步骤 l 、主要忍想： w e i l e r - a t h e r t o n 算法主要适用于被裁剪多边形与裁剪多边形都是任意多边形时的裁剪。 在此算法中，多边形由有序、首尾相接的环形点序列组成。经过求交运算计算出交点。交点 分为两类：出点和入点。出点是所在弧段从多边形内剑多边形外的点；入点则是所在弧段从 多边形外到多边形内的点。求出被裁剪多边形的出点、入点以后，取被裁剪多边形的一入点， 沿被裁剪多边形追踪，直至碰到山点跳转至裁剪多边形继续追踪，如果遇到入点则在沿被裁 剪多边形追踪，直至返回起始点。经过对每一个入点的追踪，得到被裁剪多边形与裁剪多边 形的交集。如果取被裁剪多边形的出点，当遇到入点时反向追踪裁剪多边形，则可以的到被 裁剪多边形与裁剪多边形的差集。 2 、实现步骡 下面给出w e i l e r - a t h e r t o n 算法的数据定义和实现步骤。 数据定义： 定义一：设p s 为被裁剪多边形，其顶点序列为： p s ( 0 ) ，p s ( o , p s ( n ) ，其中p s ( 0 ) = p s ( n ) ； 外环( 边界) 为顺时针方向，内环( 边界) 为逆时针方向。 定义二：设p c 为裁剪多边形，其顶点序列为： p c ( o ) p c ( 1 ) ，p c ( m ) ，其中p c ( o ) = p c ( m ) ； 外环( 边界) 为顺时针方向，内环( 边界) 为逆时针方向。 定义三：设p 为裁剪出的新多边形，p i n 为内多边形，p o u t 为外多边形。其顶点序列为： p ( o ) ，p ( 1 ) ，p ( m ) ) ，其中p ( 0 产p ( m ) ；外环( 边界) 为顺时针方向，内环( 边界) 为逆时针方向。 算法步骤： 步1 ：对被裁剪多边形p s 和裁剪多边形p c 求交，将交点插入p s 与p c 相应位置，然后将 交点加入交点链表i 。 步2 ：计算交点链表i 中交点与裁剪多边形p c 的出入关系并标记出点、入点。 步3 ：在交点链表i 中取一入点i ，在被裁剪多边形p s 中找剑该点位置，沿顺时针方向追踪 1 6 东南大学硕士论文 p s 直至遇到下一交点i j ，将追踪顶点序列加入新多边形p 中。 步4 ：在裁剪多边形p c 中找到i 所在位置，沿顺时针方向追踪p c 直至遇到下一交点，将 追踪顶点序列加入新多边形p 中。 步5 ：跳转至被裁剪多边形p s ，重复步3 至步4 。直到返回到起始交点。得到新多边形p 。 此时得剑的新多边形为内多边形p i n ，如果从出点开始反向追踪得到的则是外多边形 p o l l t 。 在图3 - 2 中，被裁剪多边形p s = s l ，s 2 ，s 3 ，s 4 ，s 5 。s 6 ，裁剪多边形p c ； c l ， c 2 ，c 3 ，c 4 ，c 5 ，c 6 ，交点链表i = i n ，1 2 ，d ，1 4