（控制理论与控制工程专业论文）电子海图岛屿多边形简化与合并算法研究.pdf

哈尔滨t 挥大学硕十学位论文 摘要 随着电子海图技术的日益发展，其应用领域不断扩大。本论文以电子海 图服务于近水面飞行器航路规划时对岛屿进行规避的特定应用为背景，针对 岛屿的简化与合并问题进行深入的研究。由于矢量电子海图中描述岛屿使用 的是一系列离散的点数据，岛屿简化与合并的目的是在尽可能不损失岛屿形 态特征的前提下尽量减少描述岛屿的数据点个数和减少岛屿的个数，降低应 用岛屿数据进行航线设计时的计算复杂度，提高应用效率。 针对实际岛屿形态各异，弯曲复杂的特点，对岛屿的形态特征进行了仔 细的分析，提出了基于直线段绕动方向的岛屿弯曲识别方法和基于凸壳的岛 屿形态整体识别方法，并建立了有效的数学模型对岛屿形态进行合理的表达。 本论文在对多种经典的曲线化简算法进行比较分析的基础上，结合实际应用 的特点，选择d o u g l a s p e u c k e r 算法作为基本的岛屿简化算法模型，并对基本 模型进行了改进使之充分满足特定的应用。为了提高算法的执行效率，重点 研究了改进后算法的实现方法，提出了切实可行的高效率的实现方法。在岛 屿合并方面，针对合并时多边形间邻近冲突的检测方法和岛屿合并的实施方 法两个关键问题进行了深入的研究，提出了对岛屿数据构建约束d e l a u n a y 三 角网的方式进行岛屿间邻近关系分析的方法，解决了多边形间冲突检测的难 题。提出了“切线演化”岛屿合并方法，可以通过控制演化阈值的方式，得 到满意的符合应用条件的岛屿合并结果。 应用从实际海图中提取的岛屿数据，采用本文提出的岛屿简化与合并算 法，对岛屿进行了化简和合并操作，结合化简与合并后的结果对新算法的正 确性和合理性迸行了分析，并通过具体的应用实例，对比分析新算法和已有 算法在实际应用中的效果差异，验证了新算法的有效性和进步性。 关键词：电子海图；岛屿形态表达；岛屿简化；岛屿合并 哈尔滨丁程大学硕十学位论文 a bs t r a c t a l o n gw i t ht h eg r a d u a ld e v e l o p m e n to fe l e c t r o n i cc h a r tt e c h n o l o g y , i t s a p p l i c a t i o nd o m a i ne x p a n d su n c e a s i n g l y i nt h eb a c k g r o u n do ft h es p e c i f i c a p p l i c a t i o no ft h ee l e c t r o n i cc h a r tf o rp a t hp l a n n i n gi nt h ef l i g h tv e h i c l er o u t e w h e r et h ei s l a n d sa r et h em a i no b s t a c l e s ，t h i sp a p e rm a k e st h et h o r o u g hr e s e a r c h i nv i e wo ft h ei s l a n d s s i m p l i f i c a t i o na n da g g r e g a t i o n a st h ev e c t o re l e c t r o n i c c h a r tu s e sas e r i e so fs e p a r a t e ds p o td a t at od e s c r i b ei s l a n d s ，t h eg o a lo fi s l a n d s s i m p l i f i c a t i o na n da g g r e g a t i o nl i e si nr e d u c i n gt h ed a t ap o i n to fd e s c r i b i n gi s l a n d s a n dt h en u m b e ro fi s l a n d sa sf a ra sp o s s i b l e ，r e d u c i n gt h ec o m p u t a t i o nc o m p l e x i t y o fi m p l e m e n t i n gt h er o u t e d e s i g nu s i n gt h ei s l a n d sd a t a ，a n dr a i s i n gt h e a p p l i c a t i o ne f f i c i e n c y i nv i e wo ft h ei s l a n d s c h a r a c t e r i s t i c so fd i f f e r e n ts h a p ea n dc o m p l e xc u r v e ， t h i sp a p e rh a sc a r r i e do nd e t a i l e da n a l y s i st ot h es h a p ec h a r a c t e r i s t i co fi s l a n d s ， p r o p o s e dt h ei s l a n d s r e c o g n i t i o nm e t h o db a s e do nm o v i n gi nas t r a i g h tl i n e a r o u n dt h ep a r a g r a p hd i r e c t i o na n dt h ei s l a n d s w h o l es h a p er e c o g n i t i o nm e t h o d b a s e do n c o n v e xh u l l ，t h e ne s t a b l i s h e dt h ee f f e c t i v em a t h e m a t i c a lm o d e lt o i m p l e m e n tt h er e a s o n a b l ee x p r e s s i o no ft h ei s l a n d s s h a p e f i r s t ，t h ep a p e rc a r r i e s o n c o m p a r a t i v ea n a l y s i s t o m a n yk i n d s o fc l a s s i c a lc u r v e s i m p l i f i c a t i o n a l g o r i t h m s a n dc h o o s e st h e d o u g l a s p e u c k e ra l g o r i t h ma st h eb a s i c i s l a n d s s i m p l i f i c a t i o na l g o r i t h mm o d e l t h e n ，i no r d e rt os a t i s f yt h es p e c i f i ca p p l i c a t i o n f u l l y , s o m ei m p r o v e m e n tt ot h ef u n d a m e n t a lm o d e la r em a d e f o rt h es a k eo f i m p r o v i n gt h ei m p l e m e n t a t i o ne f f i c i e n c yo fa l g o r i t h m ，t h i sp a p e rh a ss t u d i e dt h e r e a l i z a t i o nm e t h o do ft h ei m p r o v e da l g o r i t h m ，a n dp r o p o s e dt h ep r a c t i c a l ，f e a s i b l e ， h i g he f f i c i e n c yr e a l i z a t i o nm e t h o d i ni s l a n d s a g g r e g a t i o na s p e c t ，w eh a s c o n d u c t e dt h o r o u g hr e s e a r c hi nv i e wo ft h ee x a m i n a t i o nm e t h o do ft h ec o n f l i c t b e t w e e nt h en e i g h b o r i n gp o l y g o na n dt h ei s l a n d s a g g r e g a t i o nm e t h o d ，t h e n p r o p o s e dt h em e t h o do fa n a l y z i n gt h ec o n f l i c tr e l a t i o n s h i pb e t w e e ni s l a n d sb a s e d o nb u i l d i n gc o n s t r a i n e d d e l a u n a yt r i a n g u l a t i o nn e t ，a n ds o l v e dt h ed i f f i c u l t 哈尔滨t 程大学硕士学何论文 p r o b l e mo fd e t e c t i n gc o l l i s i o na m o n gp o l y g o n s t h i sp a p e ra l s op r o p o s e s “t h e t a n g e n te v o l v e m e n t ”a l g o r i t h ma st h em e t h o do fi s l a n d sa g g r e g a t i o n i nt h i sw a y w ec a no b t a i ns a t i s f y i n ga g g r e g a t i o nr e s u l t sw h i c hc o n f o r mt ot h ea p p l i c a t i o n c o n d i t i o nb yc o n t r o l l i n gt h ee v o l u t i o nt h r e s h o l dv a l u e w eu s et h es i m p l i f i c a t i o na n da g g r e g a t i o na l g o r i t h mo fi s l a n dt h a tp r o p o s e d i n t h i sp a p e ra n da d o p td a t af r o mt h ea c t u a l e l e c t r o n i cc h a r tt os i m p l i f ya n d a g g r e g a t ei s l a n d s ，a f t e rt h a tw ea n a l y z et h ea c c u r a c y a n dt h er a t i o n a l i t yo ft h en e w a l g o r i t h m t h r o u g ht h ea c t u a la p p l i c a t i o ne x a m p l e ，t h en e wa l g o r i t h mi sp r o v e d v a l i da n dp r o g r e s s i v e k e yw o r d s ：e l e c t r o n i cc h a r t ；i s l a n d ss h a p ee x p r e s s i o n ；i s l a n ds i m p l i f i c a t i o n ； i s l a n da g g r e g a t i o n 哈尔滨工程大学 学位论文原创性l 声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：沉怎，率 日期：2 一乡年3 月i 曰 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 切在授予学位后即可口在授予学位12 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：1 施杏卑导师( 签字) ：荔骺蒡彩 日期：渊年3 月f 日 f 矽矿罗年多月多留 哈尔滨t 程大学硕士学位论文 第1 章绪论 1 1 课题背景与意义 本课题以我校研制的电子海图系统的二次开发为背景，旨在解决电子海 图应用中的几个重要问题： 一、在电子海图系统数据库中提取岛屿要素信息，并在保证岛屿几何形 态不变的前提下进行特征点的提取，并对岛屿数据进行简化处理。 二、结合应用需要，检测海图中岛屿之间的邻近关系，并在给定的约束 条件下，对满足一定条件的岛屿进行合并，目的在于减少岛屿数目，降低应 用岛屿数据进行计算时的复杂程度。 三、以电子海图服务于近水面飞行器航路规划时对岛屿进行规避的应用 为背景，研究电子海图中岛屿的简化与合并问题，为航路规划时设计最优航 路提供保障。 1 1 1 电子海图岛屿数据存储特点概述 1 电子海图系统的定义 电子海图系统( e l e c t r o n i cc h a r ts y s t e m e c s ) 是随着航海事业及科技的发 展而产生的一种集成式的实时导航信息系统，被认为是继雷达a r p a 之后近 1 0 年来在航海领域又一项伟大的技术革命。按照国际海道测量组织( m o ) 的定义：电子海图系统是一种将海图信息、定位信息、雷达信息、船舶动态 参数集于一体的图文并茂的航海自动化系统。它由电子海图数据文件、控制 显示设备、专用软件和外接传感器构成。作为地理信息系统( g i s ) 成功应 用的电子海图发展到今天，已经完全可以取代纸质海图，完成航线设计、航 线检查、航行作业、航行计算、航行标记、信息处理等航海功能胆1 。 2 电子海图系统中岛屿的存储特点 电子海图系统作为海洋信息的显示平台，可以详尽的描述指定海域的实 际地物特征信息。岛屿作为海图中最重要的要素之一，大量存在于海图中。 在现今的矢量电子海图中，描述岛屿使用的是一系列密集的离散点列。由于 数据点越多，描述原始地物的能力越强，越能真实的反映原物体。因此，在 哈尔滨丁稃大学硕十学位论文 电子海图系统中为了详尽的描述岛屿的形态特征，对于每个岛屿都存储了大 量的数据点。 如图1 1 所示为在图号是c 1 3 9 0 0 的比例尺为l ：2 5 万的海图上提取了部 分岛屿的全部数据点( 图中的实心点) 。从图中可以看出，大量的离散点数据 连接在一起，共同表征了岛屿的几何形态。 图1 1 岛屿数据点提取图 1 1 2 电子海图岛屿数据应用概述 岛屿作为组成电子海图的基本要素之一，对于电子海图的应用具有决定 性的意义。然而，岛屿的应用不可避免的会使用到描述其特征的数据。例如， 在海图上进行舰船等的航线设计时必须考虑岛屿对航线设计的限制和约束， 需要对岛屿进行规避处理，在处理的过程中必然会应用到描述岛屿的点数据。 再例如，在海图上应用岛屿进行目标定位时，岛屿的位置也需要通过存储在 数据库中的数据点确定。总之，描述岛屿的数据点对于岛屿形态的表征和岛 屿的应用具有十分重要的意义。 具体到本课题的应用背景，需要在海图上对近水面飞行器进行航路规划。 规划的目的是在对岛屿进行障碍回避的基础上寻求最优航路。由于我国近海 岛屿星罗棋布，而且由前面叙述可知，描述岛屿的是一系列离散的数据点， 2 哈尔滨工程大学硕士学位论文 对于路径规划来说应用矢量海图中密集的点数据进行航路规划显然数据量太 大，规避时占用机时过多，效率极低。为此，有必要对描述岛屿的大量的点 数据在保证其几何形状不变的前提下进行特征点的提取，即对现状要素进行 简化处理。另一方面，由于一些岛屿彼此之间的距离较近，以岛屿群的形态 存在，所以对岛屿群进行规避时，为了提高规避效率，首先应该对岛屿群进 行合并处理。因此，寻求有效的算法对岛屿数据进行处理，在保持岛屿特征 的基础上减少其数据量，使之满足航路规划应用的要求，以实现高效率的避 障成为对舰船等进行航路规划的关键技术之一。 如图1 2 所示，为我国近海舟山附近的海图，从图中可以清晰的看出凌区 域岛屿众多，在该区域进行航路规划时，对附近的岛屿进行规避非常困难。现 阶段我们仅能实现对指定的岛屿进行自动规避。 一、”：一。一。“ 7， ， ”。 “! ，户气一 _ 一! ” 。 。 、一 ：。 一 一 u 。 一f - 一 r 一1 。 - ， 。j 一 ，￥ ，一 n ：i -可 季1 0 ( c ) 对选中的障碍物规避后( d ) 对多个选中的障碍物规避后 图1 2 航路规划现状 如8 t ( b ) 所示，我们需要人工指定规避的岛屿，被指定的岛屿以一个很粗 略的四边形或八边形代替，这样对岛屿的简化显然太粗略，体现不出岛屿的 原有几何形态特征。例如对岛屿的应用时，有时我们需要保持岛屿大的弯曲 叠一藩 哈尔滨 j 程大学硕士学何论文 特征。图( c ) 为对指定的岛屿进行规避后的结果。按照这种方法，如果对该区 域的所有岛屿都进行避障，则要依次选取所有的岛屿，效率极其低下，而且 避障后的航路很可能不是最优的，如图( d ) 所示。通过分析我们可以发现，该 区域内的岛屿以岛屿群的形式存在，如果我们按照应用的限制对该区域的岛 屿首先进行综合处理，然后在处理后的结果上在进行航路规划，必然会大大 提高规避的效率。因此对岛屿进行适当的简化和合并处理对于航路规划选择 最佳航路具有十分重要的意义。 1 2 岛屿简化与合并算法研究现状 1 2 1 现有曲线化简算法分类 目前，从收集到的文献资料来看，有关岛屿简化和合并的算法大都集中 在地图自动综合领域。 美国学者b m 罗伯特( r o b e r tbm c m a s t e r , 1 9 9 2 ) 将曲线化简的方法分为五 类p 1 ：第一类，独立点算法( i n d e p e n d e n tp o i n ta l g o r i t h m s ) ，其特点是不需要计 算相邻坐标对的数学关系，而用拓扑逻辑的独立性完成，属于此类算法的有 n 阶点程序、点的随机选择等；第二类，局部处理算法( l o c a lp r o c e s s i n g r o u t i n e s ) ，它是利用直接相邻点的特性决定该点是选取还是删除，这类算法的 例子有点与点之间的距离、点与点之间的角度变化、詹克斯( j e n k s ) 算法等； 第三类，受某些条件限制的扩大的局部处理算法( c o n s t r a i n e de x t e n d e dl o c a l p r o c e s s i n gr o u t i n e s ) ，它是通过检索除中间点以外的邻接坐标并估计线划的分 段，按照距离、角度或标准点的数目扩大检索范围，f l g ( l a n g ) 算法、奥普海 姆( o p h e i m ) 算法、约翰森( j o h a n n s e n ) 算法、德韦奥( d e v e a n ) 算法和罗伯杰 ( r o b e r g e ) 算法等，就是这类算法的例子；第四类，不受限制的扩大的局部处 理算法( u n c o n s t r a i n e de x t e n d e dl o c a lp r o c e s s i n gr o u t i n e s ) ，它是检索除中间点以 外的邻接坐标并估计线划的分段数，检索范围的扩大受线划地形复杂性的限 制，而不是受算法标准的限制，属于此法的如雷纽曼一威特卡姆 ( r e u m a n n - w i t k a m ) 算法等：第五类，整体的算法( g l o b a lr o u t i n e s ) ，即化简线 划时考虑的是完整的线划或某一确定的线段，交互地选择特征点， d o u g l a s p e u c k e r 算法就属于此例。 在已有的很多曲线的化简算法中都必须已知阈值，但是用一个阈值作用 4 哈尔滨 程大学硕士学何论文 于不同的曲线，其效果不是很好( b a r b a r ap f e i lb u t t e n f i e l d ，1 9 8 7 ) ，因而阈值的 分配就成了一个难题， b a r b a r ap f e i lb u t t e n f i e l d ( 1 9 8 7 ) 提出应先确定线的结 构，即使是同一条线也应当按类型分成不同的区间，他使用的是古典式聚类 分析方法。 在曲线化简过程中可能出现的自相交和曲线间的互相交是必须考虑的问 题，z h i l i nl ia n ds t a no p e n s h a w ( 1 9 9 2 ) 分析认为d o u g l a s p e u c k e r 方法在进行 “迁回 型的线综合时，会产生线的自交，为了解决这个问题，他提出了基 于自然规律的自动综合方法。m v i s v m i n g a ma n dj d w h y a t l ( 1 9 9 3 ) 提出了基于 最小面积的重复式点删除方法( r e p e a t e de l i m i n a t i o n ) ，为了顾及曲线的地理特 征，应当先搜索“瓶颈”式区域或图形复杂部分( 这部分由人工干预) 。 关于曲线的化简，特征点的保留非常重要，它包括几何特征点和地理含 义的特征点( g e j e n k s ，1 9 7 9 ) 。z h i l i nl i ( 1 9 9 5 ) 在分析了大量曲线特征点的探测 方法后，把它们归为三类：拐角探测法、多边形拟合法和混合方法。特征点在 计算几何、计算机视觉中有大量应用，在g i s 数据压缩方面也起很重要的作 用。 1 2 2 曲线简化算法存在问题分析 从上一小节分析中我们可以看出，对于曲线的简化，还存有一定的问题， 主要表现在： ( 1 ) 自相交问题 在曲线的化简中，由于删除一些点而引起的曲线自相交现象是一个必须 解决的问题，前面已经提到了z h i l i n “( 1 9 9 2 ) 和m v i v s a l i n g a m ( 1 9 9 3 ) 针对此 问题提出的方法，这些方法只是实验上的验证，并未做完备性证明。郭庆胜 ( 1 9 9 8 ) 提出了渐进式综合方法，采用局部探测法解决自相交问题，他同时指 出，“渐进式综合方法的不完备性在于，需要从线状要素的地理含义出发，强 制保留重要特征点，从理论上还没有完全解决因位移而进一步产生的自相交 问题 。 ( 2 ) 图形知识的定性定量化描述 如何从图形中获取知识、怎样描述、如何量化等问题都需进一步探讨。 曲线化简的基本要求是保持图形基本的形状结构特征及目标相互间关系，但 哈尔滨工程大学硕士学位论文 图形的结构特征如何体现，目前尚缺乏适用于计算机处理的模型。 ( 3 ) 阈值自动确定问题 曲线化简算法中，都存在一个阈值确定的问题。阈值的确定与曲线本身 的属性、形态特征和应用需求直接相关。从曲线自身的属性和形态特征及应 用要求获取阈值的大小是需要解决的问题。王桥( 1 9 9 8 ) 对此作了一定的研究， 他采用分形分析法，通过求取曲线的分维值，并建立两者间关系，自适应产 生化简所需阂值。 曲线化简的方法虽然很多，但其根本目的都是在保持曲线基本特征的前 提下，通过减少构成曲线的点的数量，完成图形的化简。对于曲线化简过程， 应遵循“三个保持”：一是保持化简前后图形的相似性，即保持弯曲形状的基 本特征；二是保持弯曲特征转折点的精确性；三是保持不同地段弯曲程度的 对比。 1 2 2 传统多边形合并方法概述 在多边形的合并算法方面，传统的多边形合并方法主要是基于栅格结构， 应用数学形态学的原理来合并多边形。基于数学形态学的方法针对图像采用 膨胀、腐蚀、开运算、闭运算、击中、薄化和厚化等运算，算法速度与区域 大小有关而与区域内目标数量无关，对处理大区域图像，计算量成倍增长， 严重影响算法的效率；同时由于这种方法在扩张方向上可能出现盲目性，使 得合并的多边形形状产生较大的弯曲，而且栅格与矢量格式的转化中的精度 问题也会对结果产生不良的影响垆引。 矢量数据方面，对于相交多边形的合并相对简单，大部分的软件已经实 现。b a d e re ta 1 ( 1 9 9 7 ) 提出了一种解决相离多边形的缓冲区合并方法。 图1 3 缓冲区法合并相离多边形 6 哈尔滨工程大学硕士学位论文 如图1 3 ，向多边形的# i - 便u 作缓冲区，缓冲区的宽度为规定阈值的一半， 如果两个缓冲区相交，则多边形是冲突的，需要合并。将缓冲区的交点分别 投影到多边形的边上，得到投影点的坐标，将两个多边形的对应投影点相连， 就构成了合并多边形的新边。 缓冲区多边形合并算法的关键在于以冲突阈值的一半产生缓冲区，求取 缓冲区边界的交点，将交点投影到对应的多边形上，从而将多边形间的分割 区域合并。但是当缓冲区边界交点邻近，或同一个多边形上的投影点邻近时， 相离多边形的分割区域就只是一条很窄的带相连，如图1 4 。另# 1 - 女n 果缓冲区 边界的交点个数较多时，如何去确定两端的交点也是比较复杂的操作。 图1 4 缓冲区算法合并多边形的局限性 r u a s ( 1 9 9 5 ) 提出一种基于c d t 的s d s 模型相离多边形合并算法。钱 海忠等( 2 0 0 5 b ) 、张晶等( 2 0 0 6 ) 在此基础上对该算法进行了改进。张晶等 则提出统一解决多边形化简和合并的改进方案。他将c d t 剖分后待处理的三 角形分为6 个类别：连接三角形、凹部间三角形、凹部前端三角形、新生成 凹部前端三角形、完全新生凹部前端三角形、岛屿间三角形，对不同类别定 义了相应的操作。c d t 中不可避免存在边缘尖锐三角形，这些三角形不应该 用于多边形之间的合并，但是用欧氏距离或者三角形条边的平均长等参数来 判断不足以排除这些三角形，张晶等研究了对这些三角形进行处理的方法。 基于c d t 的s d s 模型算法是对多边形统一进行约束三角网的剖分，多 边形内部和多边形之间的区域都被分解为简单的三角形区域。剖分的三角网， 不仅可以描述多种邻近关系，检测多边形的邻近冲突，还可以通过对三角网 中的三角形分类操作来实现多边形的合并。但是如何作有利于合并操作的三 角形精确分类，对不同类别的三角形或者三角形组合又如何操作，这些问题 哈尔滨1 二程人学硕十学位论文 在实际进行应用的过程中仍是难点，三角形的多余计入、三角形的误删都会 影响多边形合并的质量。并且现有的基于c d t 的s d s 模型算法只是对规则 多边形( 如建筑物) 的合并效果比较好，对于像海图等这样具有大量不规则的 多边形合并效果并不理想。 综上所述，尽管缓冲区多边形合并算法以及基于c d t 的s d s 模型算法 在解决相离多边形合并问题方面已经取得了一些进展，对于一部分多边形合 并也可以获得比较满意的结果，但是这两种方法在实际应用的过程中还存在 一定的局限性。因此，我们迫切的需要在充分分析、总结现有多边形合并算 法成果的基础上，寻求满足实际应用的岛屿多边形合并算法。 1 3 课题主要研究内容 本课题针对矢量电子海图中岛屿数据的存储特点，结合近水面飞行器在 海图上进行航路规划时对岛屿实施避障的应用需求，研究岛屿多边形的简化 和合并问题。岛屿简化的目的在于保持岛屿基本形态特征不变的条件下减少 描述岛屿的数据点个数，岛屿合并是从满足特定应用特点的前提下尽量减少 岛屿的个数。岛屿简化和合并的意义在于实际应用中减少岛屿数据的处理量， 降低计算的复杂度，提高应用效率。 本课题的主要研究内容有： ( 1 ) 深入研究岛屿多边形的形态特征。为了得到好的岛屿简化和合并效 果，必须对岛屿的形态特点进行透彻的分析。针对实际岛屿形态复杂，弯曲 众多且不规则的特点，仔细研究岛屿弯曲特征的识别与表达方法，提出了基 于直线段绕动方向的弯曲识别方法和基于凸壳的岛屿形态整体识别方法。特 别地，对于复杂弯曲，提出了逐层划分弯曲的思想。为了对岛屿的弯曲形态 进行有效的表达，将组成岛屿的数据进行合理的组织，建立了基于弯曲 d o u g l a s 一- 叉树的岛屿形态表达方法，该方法的建立为岛屿简化与合并的实施 奠定了好的基础。 ( 2 ) 确定岛屿简化算法并提出算法的实现方法。任何一种算法都有其特 定的适用范围和应用条件，针对岛屿简化在近水面飞行器航路规划时避障的 具体应用，在深入研究现有算法的基础上，对多种经典的曲线简化算法进行 了分析和效率比较，选择出实现效率最佳的算法，并结合实际应用特点，对 哈尔滨t 程大学硕士学位论文 算法进行优化和改进。算法执行的效率问题是体现一个算法优劣的重要指标， 因此，课题中重点研究了改进后的算法实现方法，意在最大限度地提高算法 的执行效率。 ( 3 ) 提出切实可行的岛屿合并方法。岛屿合并的关键在于解决以下两个 技术难题：多边形之间邻近冲突关系的判断方法和冲突多边形间合并的方法。 针对多边形邻近冲突关系的分析，提出了构建约束d e l a u n a y 三角网的方法， 并研究了冲突多边形间的组织问题，通过建立“冲突多边形组的方式对存 在邻近冲突的多边形统一组织和管理。提出了“切线演化 多边形合并算法， 结合两个多边形的合并和多边形群间的合并问题分别进行了深入的研究。 ( 4 ) 岛屿简化和合并算法的实现。针对实际电子海图上的岛屿数据，按 照课题中提出的简化与合并算法进行化简和合并操作，结合实际应用效果分 析算法的有效性和可行性。 1 4 论文的组织结构 论文主要包括五章内容： 第一章为绪论部分。首先阐述课题的研究背景与意义，概括地描述了电 子海图中岛屿数据的存储特点和应用情况，然后分析了岛屿简化与合并算法 的国内外研究现状，最后给出了课题研究的主要内容以及论文的组织形式。 第二章重点研究岛屿多边形的形态表达方法。从分析岛屿的弯曲特征开 始，介绍了弯曲的定义和描述弯曲的特征参数，提出弯曲的识别方法，建立 描述岛屿形态的数学模型，充分对岛屿形态进行表达。 第三章首先阐述了国内外当前流行的曲线化简方法，然后对各种算法进 行了详细的分析和比较。在确定岛屿化简原则的基础上，选择出适合岛屿化 简的算法，结合具体应用对算法进行了改进，并提出了改进后算法的实现方 法。最后对岛屿化简时产生的相交问题进行了讨论。 第四章首先描述了约束d e l a u n a y 三角网及其剖分实现方法，然后提出应 用约束d e l a u n a y 三角剖分进行多边形邻近关系分析的方法，接着对剖分后检 测出存在邻近冲突的多边形进行了分类和聚类处理。最后重点研究了岛屿多 边形间的合并方法，并对多边形群的合并方法做了详细的论述。 第五章首先设计了电子海图中岛屿数据的提取方法和存储方案，其次针 9 哈尔滨t 程大学硕十学位论文 对海图中的实际岛屿数据给出了简化和合并的实现方法和实现结果，说明了 算法的可行性及有效性。然后通过具体的应用实例阐述了本文中提出的算法 较原有算法的改进之处，并证明了本文研究的算法在实际应用中具有较高的 应用价值。 1 0 哈尔滨j i ：稗大学硕十学位论文 第2 章岛屿多边形的形态表达 由前一章的叙述可知，岛屿的应用离不开描述岛屿的大量离散数据点。 在应用时为了方便操作我们需要通过各种算法提取一定数量的数据点来表征 岛屿，提取出的数据点要保证描述的岛屿形态特征保持不变。因此，为了在 对岛屿数据进行简化等操作时保持岛屿的形态，应该充分的研究岛屿的形态 特征，设计适当的数据结构表征存储其特征信息，以便在充分的剖析岛屿形 态的基础上，对其进行数据简化等各种操作。 由于实际的岛屿形态各异，岛屿在海图上的描述往往有很多个弯曲组成， 岛屿的弯曲特征主要体现在“曲 上，它们的空间尺度、扭转角度、弯曲方 向都可能不同，其蕴含的地理特征也主要是通过弯曲特征表现的【叼。弯曲是 线状目标形态综合的基本操作单元，一些综合指标也是以此为依托建立的， 如弯曲的大小、弯曲的形状等。通过对弯曲特征的识别，将有助于综合指标 的数量化和模型化。对岛屿而言，其蕴含的地理特征上的结构化信息主要是 通过弯曲特征表现的【习嗍。因此，岛屿上弯曲特征的识别、结构描述和操作对 于其形态的表达以及岛屿简化具有十分重要的意义。 2 1 弯曲的描述 2 1 1 弯曲的定义 2 1 1 1 基于拐点的弯曲定义 拐点是曲线上的一类特殊的点，许多学者将连接拐点的线称为曲线的中 轴线或趋势线，这些都是基于拐点的特殊性。一个弯曲是曲线的一部分，它 是由许多连续的点组成。弯曲上每个点出发的两线段都有转折角，或正或负， 弯曲的两个端点会改变转角的正负性，可称改变转角正负的点为曲线的拐点。 在拐点处曲线改变弯曲的方向，更严格地说是改变弯曲的延续方向，使 之向相反的方向弯曲。如图2 1 ，曲线上局p ：段是逆时针弯曲，而p ：p ，段是 顺时针弯曲，弯曲在拐点办处发生变向。这种基于拐点的弯曲通常连续间隔 的分布在中轴线的两侧。可以通过弯曲的大小和弯曲的形状来描述曲线：弯 曲大小指弯曲和基线间的多边形的面积；弯曲的形状指弯曲和基线构成的凸 哈尔滨t 程大学硕士学何论文 多边形。 图2 1 基于拐点的弯曲 基于拐点的弯曲定义具有如下两个特性： 1 、正角弯曲和负角弯盐相间出现； 2 、弯曲是相邻的，覆盖了曲线的所有点。 2 1 1 2 基于张角的弯曲定义 费立凡( 1 9 9 3 ) 提出一种基于张角的弯曲定义方法，这种方法定义的弯 曲和人们感官认识上是一致的。如图2 2 ，设是弯曲上的一点，在的附 近取一点鼠，以只为原点，作射线只p 。假设a 在既的下方，n i l ：p 从风开 始在曲线上风的前方沿曲线运动，运动过程中，张角勿，风p 有一个最大值， 设最大张角处为点p ：。再以p ：为原点，作射线p ：p 。，让p 从p 。点出发，沿p l 下方的曲线运动，得最大张角点见，。依次类推，得到一系列点胁、p 。、 p ：、p ，、p 4 、p 5 ，直到点见一与以的距离小于预定的限差e ，且成与以卅 的距离也小于限差，则p 一与成就是弯曲的两个端点。 图2 2 基于最大张角的弯曲定义 1 2 哈尔滨丁稃人学硕十学位论文 2 1 2 描述弯曲的特征参数 ( 1 ) 弯曲的宽度w ，也可形象地称之为弯曲的口径，即图2 3 中a b 或者 b c 之间的距离。 ( 2 ) 弯曲的高度h ，也可称之为最大垂距，即图2 3 中弧段a b ( 或者b c ) 上距离点a 和点b ( 或者点b 和点c ) 所构成的直线之间的最远距离。 abc 图2 3 弯曲的宽度和高度 ( 3 ) 弯曲的长度s ，a b 或者b c 之间弧段的总长度就是该弯曲的长度。 ( 4 ) 弯曲的面积s ，线段a b ( 或b c ) 与a 、b ( 或b 、c ) 之间的弧段所形成 的闭合区域的面积是该弯曲的面积。 以上的几个综合参数并不能全面的描述出弯曲的特征，如空间尺度的大 小，一般同时取决于弯曲的宽度和高度，弯曲的复杂程度也不能单单根据一 个特征量就可以做出评判的。因而还需要采用一些复合特征参数p 1 。 ( 1 ) 面积系数e 。设周长为w + j 的圆所围面积是鼠，则e = s s o ，e 的最 大值为1 ，此时线段a b 及a b 间的弧构成一个圆( 在周长一定的条件下，圆 所围面积最大) 。一般e 值最小，弯曲的凸凹性越复杂。 ( 2 ) 弯曲度厂。弯曲的长度j 与宽度w 的比值称为弯曲度，即f = s w 。 弯曲度的最小值是l ，值越大，说明弯曲程度越大。 ( 3 ) 对称度只。设弧a b 与线段a b 所形成的闭合区域中，位于a b 中垂 线左侧与右侧区域的面积分别为s ，足，当墨 最时，定义只= 是s , ，反 之只= s s ，。该参数可反映出弯曲凸凹的对称性，最大值是l ，值越小，说 明该弯曲的对称性越差。 2 2 岛屿弯曲特征的识别 岛屿的边界为一条封闭的曲线，其边界可以分为凸部、凹部两部分( 将岛 屿面域外的弯曲定义为凸部) ，其最小凸壳无疑就是凸部特征点的集合，在岛 哈尔滨丁程大学硕士学位论文 屿的化简中，通常是需要保留的特征点。而当岛屿的凹部非常显著，对其形 状特征影响很大时，则对凹部的识别也是必须的。特别的，当一个大弯曲里 嵌套着一个或多个小弯曲，即形成了复杂弯曲时，如何较好地依次识别出这 些弯曲，然后针对每个弯曲决定其取舍是一个非常值得研究的问题，弯曲识 别的好坏直接决定了岛屿化简的质量。 考虑到岛屿化简的实际应用价值，我们主要关注封闭岛屿的外边界形态 特征，因此在由岛屿多边形组成的曲线中，我们重点识别岛屿面域内侧的弯 曲( 凹部) 。 2 2 1 基于直线段绕动方向识别弯曲 弯曲蕴含着曲线某些重要的结构化信息，是一个基本图形单元，在岛屿 简化中常用弯曲的大小作为图形简化的指标，曲线的地理形态弯曲与数学概 念上的弯曲也是不同的，因此合理地识别弯曲显得极为重要。 弯曲的识别方法有很多种，例如基于拐点识别弯曲和采用斜拉式弯曲划 分的方法识别弯曲等。不同的弯曲识别方法适用于不同的应用环境。针对电 子海图中岛屿数据简化的特点，本文提出了基于直线段绕动方向的方法识别 岛屿弯曲。 岛屿在海图中是由一系列连续的矢量数据点描述的，定义这些数据点按 照顺时针的顺序组成了一个点集c = 墨，e 1 1o - , 9 _ ) ，其中碍为曲线的起点， 为曲线的终点。只和只两点重合，表示该点集是一条闭合的曲线。 定义2 1 给定曲线s - - ( v 0 ，屹) ( 0 刀 0 0 ) ，瓯= ( u ，) s ，( f ) ， 如果结点u ，1 ，与结点u 小，1 ，h 所在直线段的绕动方 向相反，则就是线状目标s 的一个弯曲，结点是 该弯曲的起点，结点 ，；是该弯曲的终点。 如图2 4 所示，该曲线由p 。，p 2 ，a ：共1 2 个点组 成。“+ ”和“ 分别表示线上一条后继直线段相对于 当前直线段的两个不同绕动方向。我们规定：向顺时 针方向绕动为“+ ，例如p ，点处；向逆时针方向绕动 为“ ，例如热点处。则以绕动点方向发生变化的点 1 4 图2 4 弯曲的划分 哈尔滨：r 程大学硕十学位论文 处作为分界点，可以划分出不同弯曲。如图2 4 ，点p ：，p 3 ，p 。，p 。，p 。构 成了一个弯曲；点p 。，p 9 ，p l 。，p ，。也构成了一个弯曲。 2 2 2 考虑视觉形态特征的弯曲识别 基于直线段绕动方向识别弯曲特征的方法，能够很好的划分出给定曲线 上的各种弯曲，但这种方法忽略了弯曲特征在整体结构上的一个重要特 性一一对称性。对称性是对空间图形视觉感知的g e s t a l t 心理学原则之一p 1 。 v 形、u 形、半圆形、开矩形、开三角形的弯曲结构都具有对称性特点。基 于直线段绕动方向划分的弯曲只注重了g e s t a l t 的连续性原则，按这种方法， 当点延伸方向发生改变如不连续时会产生新的弯曲，但它没有考虑变化幅度， 缺乏量的控制。 在实际应用中，如果弯曲端点处连续的转折较小，为了满足g e s t a l t 规则， 保持视觉上弯曲的整体性，可将此弯曲与邻近的弯曲合并。如图2 4 ，点p ， p ，p 。，p ，p 。构成的弯曲中，由于p 。点处的转角较小，将这个弯曲的终 点由p 。纠正到p ，点，使弯曲更适合g e s t a l t 规则。 2 ，2 3 复杂弯曲的识别 我们知道，实际的岛屿形态各异，一个岛屿很可能由很多个弯曲组成。 特别地，还会出现一个大的弯曲中嵌套着许多小弯曲的情况。针对岛屿的这 种实际特点，本文研究了逐层划分弯曲的思想，有效地解决了识别复杂弯曲 的难题。 ( a )( b ) 图2 5 复杂弯曲的识别方法 哈尔滨：r 程大学硕十学位论文 图2 5 ( a ) 为由一个大弯曲中嵌套着许多小弯曲组成的复杂弯曲。首先，应 用2 2 1 节介绍的方法我们可以识别出最小的弯曲，如图中a 、b 、c 、d 、e 、 f 、g 所示围成的区域，我们称这些弯曲为“元弯曲”。其次，将各个“元弯 曲的两端点和原始曲线上的其他点组成新的曲线，如图2 5 ( b ) 所示，在新 的曲线上再次按照基于直线段绕动方向识别弯曲的方法进行弯曲划分，形成 第二层次的弯曲，例如图2 5 ( b ) 中h 、i 、j 中所围成的区域。依此类推，逐 层识别弯曲，直至形成一个大的简单弯曲为止，例如图2 。5 ( c ) 中k 中所围成 的区域。 2 3 基于凸壳的岛屿形态整体识别 凸壳是计算几何中最普遍、最基本的一种结构。不仅它自身具有许多特 性，而且它还是构造其他几何形体的有效工具。在应用中，许多问题可以归 结为凸壳问题。凸壳是物体形状描述、特征抽取的一个重要工具，已被广泛 地应用于计算机图形学、图象处理、设计自动化、模式识别和运筹学等研究 领域例。如机器人学中，一个物体相对于另一个物体无限移动，