（构造地质学专业论文）地学制图综合中多边形对象的合并算法研究与应用.pdf

浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 中文摘要 随着地学图件的数字化及地学数据库的广泛建立，经常会从大比例尺数据生产小比 例尺数据，因此自动制图综合成为了研究的前沿和热点问题。多边形图件是应用中非常 普遍的数据，如地质图、土壤类型图、地籍图，随着图件比例尺的缩小，多边形之间会 产生图形显示方面的冲突，要通过相应的操作消除这些冲突，最常见的操作之一是多边 形的合并。但是目前的多边形合并算法存在许多局限和不足。 本文提出了基于约束d e l a u n a y 三角网剖分的多边形合并改进模型。该模型主要包 括四个部分：多边形的一次聚类分析、约束d e l a u n a y 三角网剖分、多边形的邻近分析 和多边形的合并。首先通过对图件的第一层次聚类，将多边形目标划分成许多独立的小 区域；然后分别对这些区域进行约束d e l a u n a y 三角网剖分，将每个区域划分成简单三 角形连接的区域；接着基于连接三角形，对多边形进行邻近分析即第二层次的聚类，建 立冲突的多边形组；最后将冲突的多边形组和归属于该组的卢类三角形和y 类三角形进 行合并。 基于二次开发控件m a p o b j e c t s 和a r e s d ec - a p i 函数库，在v i s u a lc + + 6 0 环境下 开发了多边形自动合并系统，实现了多边形合并的改进模型，并针对地质图和地籍图进 行了应用，研究表明，本文提出的改进模型在多边形合并方面，取得了比较好的效果。 关键词：制图综合，多边形合并，约束d e l a u n a y 三角网 浙江大学硕士学位论文 地学制图综合中多边形对象的合并算法研究与应用 a b s t ra c t t h e d i g i t a l i z a t i o no f g e o - m a p sa n dt h eb r o a de s t a b l i s h m e n to f g e o - d a t a b a s e sb r i n ga l o n ga f 嘲u c n tn e e dt op r o d u c es m a l l s c a l em a p sf r o ml a r g eo n e s a sar e s u l t , a u t o m a t i c c a r t o g r a p h i cg e n e r a l i z a t i o nh a sb e c o m et h ef r o n t i e ra n dt h em a i nf o c u si nt h i sr e s e a r c hf i e l d p o l y g o n a lm a p sa r eae o m n l o nd a t at y p ei na p p l i c a t i o n s ，s u c ha sg e o l o g i c a ll n a p s ，s o i lm a p s ， a n dc 剐l a s 仃a lm a p s a st h em a ps c a l er e d u c c s g r a p h i ce o n f l i c t sr a i s eb e t w c c np o l y g o n s o p e r a t i o n sh a v et ob e e na d o p t e dt os o l v et h e s ec o n f l i c t s ，a n da g g r e g a t i o ni st h em o s ti n c o m m o nu s e h o w e v e r , t h e r ea r cm a n ys h o r t c o m i n g so fc u r r e n ta l g o r i t h m sf o rp o l y g o n a g g r e g a t i o n i nt h i st h e s i s ，a ni m p r o v e dm o d e lf o rp o l y g o n a g g r e g a t i o nb a s e do nc o n s t r a i n e dd e l a t m a y t r i a n g u l a t i o ni sp u tf o r w a r d t h em o d e lm a i n l yi n c l u d e sf o u rp a r t s ：f i r s tc l u s t e r i n ga n a l y s i so f p o l y g o n s ， c o n s t r a i n e dd e l a a n a y 仃i a n g u l a t i o n ,印o x i m i t ya n a l y s i s o f p o l y g o n s ， a n d a g g r e g a t i o no fp o l y g o n s f i r s t , ac l u s t e r i n ga n a l y s i sw i t hm a pd a t ai sd o n ei no r d e rt od i v i d e w h o l ed a t ai n t os e v e r a lp a r t s s o c o n 正ac o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o ni sc o n s t r u c t e df o r e a c hp a r t t h i r d , p r o x i m i t ya n a l y s i s ( s e c o n dc l u s t e r i n ga n a l y s i s ) i sd o n et oc l a s s i f yp o l y g o n s w i t hc o n f l i c t s a tl a s t , p o l y g o n sw i t hc o n f l i c t s ，卢t r i a n g l ea n dyt r i a n g l eb e l o n gt ot h e ma r e a g g r e g a t e d a na u t o m a t i cp o l y g o n a g g r e g a t i o ns y s t e mf o rt h ei m p r o v e dm o d e li sd e v e l o p e db a s e do n m a p o b j e e t sa n da r c s d ec - a p ii nt h ee n v i r o n m e n to f v i s u a lc + + 6 0 i ti st h e nt r i e do u ti 1 1a g e o l o g i c a lm a pa n dac a d a s t r a lm a p a p p l i c a t i o n ss h o wt h em v a n t a g eo f t h i si m p r o v e dm o d e l 如rp o l y g o na g g r e g a t i o n k e yw o r d s ：c a r t o g r a p h i cg e n e r a l i z a t i o n , p o l y g o na g g r e g a t i o n , c o n s t r a i n e dd e l a u n a y t r i a n g u l a t i o n i i 浙江大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得浙江大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名： 浙江大学学位论文使用授权声明 浙江大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权浙江大学研 究生部办理。 研究生签名： 导师签名：2 蚴日期： 驾进- 哆 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 1 1 研究目的意义 1 绪论 随着地学图件的数字化及地学数据库的广泛建立，经常会从大比例尺数据生产小比 例尺数据，比例尺缩小后，目标问不可避免地产生冲突，因此必须对地理空间数据进行 制图综合处理，以满足现实和生产的需要。目前，自动制图综合成为了研究的前沿和热 点问题。 在地图制图中，化简与合并图形和内容、选取和强调主要内容、舍去和压缩次要内 容等方式，均可理解为制图综合( 弗特普费尔，1 9 8 2 ) 。传统的制图综合是指根据地图 资料制作新地图时所进行的地图图形的综合；计算机技术被引入到地图学领域以来，传 统的制图综合得到了延伸和扩展，人们称之为数字综合或计算机综合( 焦健等，2 0 0 5 ) 。 数字综合包括两个主要分支，国际上一般称为数据库综合( d a t a b a s eg e n e r a l i z a t i o n ) ( 或 模型综合( m o d e lg e n e r a l i z a t i o n ) ) 以及制图综合( c a r t o g r a p h i cg e n e r a l i z a t i o n ) 。为了避 免混淆，分别称之为属性数据综合和图形综合。属性数据综合可以不考虑图形显示方面 的问题，仅产生简化的数据集；而图形综合则强调图形显示的清晰性和艺术性( 焦健等， 2 0 0 5 ) 。 多边形图件是地学应用中非常普遍的数据( b a d e r e t a l ，1 9 9 7 ) ，如地质图、土壤类 型图、地籍图等，都存在着大量的多边形对象。随着图件比例尺的缩小，多边形对象之 间会产生压盖等冲突，因此需要一系列的综合操作比如删除、合并、移位等来解决比例 尺缩小后图形的清晰性问题。而其中对多边形的合并问题，是整个自动制图综合的关键 和难点，是自动制图综合中最为重要的算法( m a r t i n ，2 0 0 1 ) 。 因此，结合制图综合、计算几何、计算机图形学等学科和技术，研究多边形对象在 自动综合过程中的合并算法，是发展自动综合技术的关键之一。本文旨在研究相离多边 形对象合并的实现算法，解决多边形对象在综合过程中的图形冲突问题，为地质图、土 壤类型图、地籍图等地学图件中面元对象的合并问题提供可行的解决方法。 1 2 研究现状 1 2 1 制图综合 制图综合领域，已有的研究主要集中在概念模型的建立，综合算子的提出，综合算 法的实现。 l 、概念模型 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 制图综合是在比例尺减小的过程中降低地图的复杂度，强调主要的对象而忽视次要 的，保留地图对象间合理、明确的关系，平衡精度、信息量及可读性之间的关系，以生 产出更好的地图( a l e s s a n d r o ，2 0 0 3 ：b a s a r a n e re ta 1 ，2 0 0 4 ) 。 为了更好地理解制图综合的过程和原理，许多学者提出了制图综合的概念模型。 b r a s s e le t a l ( 1 9 8 8 ) 发展了最为详细的概念模型。为了能够模拟制图综合的过程， 必须能够很好地理解重要的对象。一方面可以通过抽象空间信息的特征结构来认知这个 过程；另一方面，可以将过程分解成若干个操作步骤。这个概念模型提出了5 个独立的 综合过程：结构认知、过程认知、过程建模、过程执行、数据显示。 r u a sc ta 1 ( 1 9 9 6 ) 提出了由一系列约束环境控制的框架模型。这些环境包括：地理 对象本身、他们之间的关系、限制条件。 m a r t i n ( 2 0 0 3 ) 认为制图综合是从空间和属性两个层次对数据集进行变换。空间层 次，要根据小比例尺的限制来调整图形对象的视觉效果；属性层次方面，要根据约束条 件对对象进行属性的修改。m a r t i n 定义了多边形综合必须遵循的约束条件，这些约束条 件包括空间和属性两个层次。将约束条件分为了四个类别：距离约束( m e t r i c c o n s t r a i n t s ) 、拓扑约束( t o p l o g i c a lc o n s t r a i n t s ) 、结构约束( s t r u c t u r a lc o n s t a i n t s ) 、过 程约束( p r o c e d u a lc o n s t r a i n t s ) 。这些约束条件既控制综合的过程，也可以评价综合的 结果。 2 、综合算子 为实现自动制图综合，通常的做法是将制图综合的过程分解，每一个分解的过程针 对一类制图综合过程中特定的问题，尽可能将分解的计算过程自动化。这些分解的过程 在制图综合领域被称为综合算予。 常见的有三算子模式( 选取、概括、位移) 和四算子模式( 选取、概括、合并、位 移) ( 王家耀等，2 0 0 6 ) 。 w i l s o n e ta 1 ( 2 0 0 3 ) 和w a r ee ta 1 ( 2 0 0 3 ) 认为地图综合过程中典型的算子包括： 线划和面边界细节的化简；次要对象的删除；对象的夸大；邻近对象的合并；面状对象 降维成线或点；对象概括；移位以保持邻近对象间的距离。 算子的应用受到一些条件的限制。b a s a r a n e re ta 1 ( 2 0 0 4 ) 认为不同的地理对象影响 综合算子的选取，在多边形综合中应用的算子是降维、符号化、化简、夸大、合并、聚 合、典型化、删除、移位；线状对象的基本操作是化简、平滑、选取。a l e s s a n d r o ( 2 0 0 3 ) 则提出地图比例尺及用途的不同也会影响综合算子的应用。 算子应用顺序的不同会引起综合结果的差异。根据大量制图综合的实践，a l e s s a n d r o ( 2 0 0 3 ) 给出了实用的算子应用顺序： ( 1 ) 选取：删除一些不相关的信息来增加可用的空间。 ( 2 ) 合并：将选中的对象结合起来，可能导致拓扑关系变化。 ( 3 ) 化简：减少细节。 2 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 ( 4 ) 平滑：跟随化简，调整视觉效果。 ( 5 ) 移位：解决上述算子导致的拓扑冲突。 由于对综合过程理解的方式不同，不同的学者对算子的数量及其定义是不同的，但 是他们的目的都在于细化制图综合过程，通过算子的组合来替代整个制图综合过程。 3 、综合算法 综合算法是进行综合变换的工具，算法必须是精确的、清晰的，可以被计算机执行 的。综合算法的重点在于能够模仿制图员的工作，以达到综合的目的。综合算法与综合 算子的区别在于：综合算子是为达到某种目的而定义概念性的变换，而综合算法是用来 实现这些具体的变换；对于每个算子来说，可以有多种综合算法( a l e s s a n d r o ，2 0 0 3 ) 。 长期以来对综合算法的研究主要集中在选取算子、化简算子方面。 选取算予是用来减少对象数目，已经有不少算法提出。t o p f e r 方根规律( 弗特普费 尔，1 9 8 2 ) 是首次尝试以数学的形式来概念化不同的规则，公式可以应用到地形图的综 合过程中。对河系的选取，r u s a ke ta 1 ( 1 9 9 0 ) 提出使用h o r t o n 规则。t h o m p s o ne ta 1 ( 1 9 9 5 ) 介绍一个用于网络分析的原型，它支持道路网的抽象和处理，支持查找关键的 有代表性的特征。 就线化简而言，有许多成熟的算法，如l a n g 算法、d o u g l a s p e u c k c r ( d p ) 算法、 r e u m a n n - w i t k a m 法、l i & o p e n s h o w 算法等。国内一些学者根据实际应用需要提出了自 己的线简化算法，或者在前入的基础上进行了算法的改进从而使算法得到完善，如基于 遗传算法的线要素自动化化简模型( 武芳等，2 0 0 3 ) 、基于圆特征的线要素自动综合算 法( 钱海忠等，2 0 0 5 a ) 等等。 1 2 2 多边形合并 合并操作是随着比例尺的缩小，制图物体的图形及其间隔缩小到不能详细区分时， 将具有邻近冲突的相同类别的对象结合成一个大的多边形，来反映制图物体的主要特征 ( l e e ，2 0 0 4 ) 。因此多边形的合并可以简单地分为两部分工作，一是多边形的邻近分析， 二是多边形的合并。 1 、邻近分析 邻近分析是制图综合的重要组成部分，它为制图综合提供相当重要的信息( b a d c re t a 1 ，1 9 9 7 ；j o n e se ta 1 ，1 9 9 9 ) 。 通常采用欧氏距离的方法进行邻近分析，即采用对象顶点间的最小距离作为邻近分 析的指标( 史佳顺等，2 0 0 3 ：钱海忠等，2 0 0 5 b ) 。设两个对象f 和_ ，分别拥有p 和g 个顶点，则对象间的最小距离d 为： r 1 。 d = i n i n ( ( 】一工加) 2 + 0 ，蛔一y 胂) 2 ) ，o m p ，o n q 。 如果水k 。，则这两个对象是邻近的。k m 为制图综合中要求的目标间的最小距离， 3 浙江大学硕士学位论文 地学制图综合中多边形对象的合并算法研究与应用 它与制图比例尺和对象的类别有关。 p e t e r e t a l ( 1 9 9 9 ) 提出了两种邻近分析的方法。一是计算每个对象的缓冲区，缓冲 区的距离设置为阈值距离的一半，缓冲区相交的对象是邻近的。另一种方法是通过三角 网剖分。 三角网在邻近分析中是非常重要的数据结构。j o n e se ta 1 ( 1 9 9 9 ) 分析了三角网剖 分的四个优点： ( 1 ) 完整表达地图空间，整个区域的三角网建模，包括对象之间的区域，都被很 清楚的表达。 ( 2 ) 保持源数据的精确性。 ( 3 ) 具有丰富的邻近关系，邻近的对象通常都有三角形连接，邻近关系的搜索可 以相当的简单，具有很高的效率。 ( 4 ) 容易进行表面修改。 j o n e se ta 1 ( 1 9 9 9 ) 提出了基于c d t ( c o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o n ) 剖分的 s d s ( s i m p l e d a t as t r u c t u r e ) 模型，用于邻近冲突检测。s d s 模型是一个由约束d e l a u n a y 三角网r 以及一个点和直线边的集合s 组成。点和直线边用来描述一个对象集合。对象 可以是点、线和面三种类型。一个点对象是一个几何点；一个线对象是可以由一条或多 条边组成；一个面对象则至少由3 条边来描述。由此可以根据点和边组成的三角网丁来 描述几种邻近关系。如果两个对象共用一个元素，那么这两个对象就是相接。这种相接， 如果共用一个顶点，就称为点相接：如果共用一条边，则称为边相接；两种情况统称为 0 级邻近，而不相接的邻近关系则被称为r 级邻近( 舢，r 为从一个顶点移动到另一个 顶点所需经过的三角网的边数的最小值) 。 计算对象顶点间的最小距离和缓冲区法在邻近分析方面简单、有效，但是三角网表 达邻近关系的方法有非常经典的数据结构，一次计算之后，可以有多项应用，因此它成 为邻近分析比较常用的方法( 应申等，2 0 0 5 ) 。 2 、多边形的合并 在多边形的合并算法方面，传统的多边形综合方法主要是基于栅格结构，应用数学 形态学的原理来合并多边形。基于数学形态学的方法针对图像采用膨胀、腐蚀、开运算、 闭运算、击中、薄化和厚化等运算，算法速度与区域大小有关而与区域内目标数量无关， 对处理大区域图像，计算量成倍增长，严重影响算法的效率；同时由于这种方法在扩张 方向上可能出现盲目性，使得合并的多边形形状产生较大的弯曲，而且栅格与矢量格式 的转化中的精度问题也会对结果产生不良的影响( 钱海忠等，2 0 0 5 b ；张晶等，2 0 0 6 ) 矢量数据方面，对于相接多边形的合并相对简单，大部分的g i s 软件已经实现。b a d e r e ta 1 ( 1 9 9 7 ) 提出了一种解决相离多边形的缓冲区合并方法。向多边形的外侧作缓冲区， 缓冲区的宽度为规定阈值的一半，如果两个缓冲区相交，则多边形是冲突的，需要合并。 将缓冲区的交点分别投影到多边形的边上，得到投影点的坐标，将两个多边形的对应投 4 浙江大学硕士学位论文 地学制图综合中多边形对象的合并算法研究与应用 影点相连，就构成了合并多边形的新边( 如图1 1 ) 。 j 厂、 图i i 缓冲区法台并相离多边形 r u a s ( 1 9 9 5 ) 提出一种基于c d t 的s d s 模型相离多边形合并算法。钱海忠等 ( 2 0 0 5 b ) 、张晶等( 2 0 0 6 ) 在此基础上对该算法进行了改进。 钱海忠等( 2 0 0 5 b ) 根据三角形的归属和位置对其进行了分类，按归属划分为四类， 按位置划分为两类，它们分别具有的性质如下： ( 1 ) 按归属分 i 类三角形；面目标内部的三角形。 i i 类三角形：面目标外部的，且3 个顶点属于同一个面的三角形。 类三角形：面目标外部的，且3 个顶点属于两个面的三角形。 类三角形：面目标外部的，且3 个顶点属于3 个面三角形。 ( 2 ) 按位置分 边界三角形：三角形的3 条边中至少有一条边没有相邻三角形。 内部三角形：三角形的3 条边都有相邻三角形。 对不同的三角形类别或类别组合，实行不同的综合操作( 如表1 - 1 ) 。 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 表1 1 三角形类别组合及其对应的操作 三角形组合是否结束生命周期 i 类三角形+ 边界三角形 否 i 类三角形+ 内部三角形 是 i i 类三角形否 m 类三角形+ 边界三角形否 i 类三角形+ 内部三角形 是 类三角形+ 边界三角形 否 类三角形+ 内部三角形是 张晶等( 2 0 0 6 ) 则提出统一解决多边形化简和合并的改进方案。他将c d t 剖分后 待处理的三角形分为6 个类别：连接三角形、凹部间三角形、凹部前端三角形、新生成 凹部前端三角形、完全新生凹部前端三角形、岛屿间三角形，对不同类别定义了相应的 操作。c d t 中不可避免存在边缘尖锐三角形，这些三角形不应该用于多边形之间的合并， 但是用欧氏距离或者三角形3 条边的平均长等参数来判断不足以排除这些三角形，张晶 等研究了对这些三角形进行处理的方法。 钱海忠等( 2 0 0 5 b ) 、张晶等( 2 0 0 6 ) 的改进方案关键都在于对c d t 剖分后三角形 类别的划分以及针对不同的三角形类别( 或类别组合) 实行不同的处理。 1 3 研究内容 尽管缓冲区多边形合并算法以及基于c d t 的s d s 模型算法在解决相离多边形合并 问题方面已经取得了一些进展，对于一部分多边形合并也可以获得比较满意的结果，但 是这两种方法在实际应用的过程中还存在一定的局限性。 缓冲区多边形合并算法的关键在于以冲突阈值的一半产生缓冲区，求取缓冲区边界 的交点，将交点投影到对应的多边形上，从而将多边形间的分割区域合并。但是当缓冲 区边冕交点邻近，或同一个多边形上的投影点邻近时，相离多边形的分割区域就只是一 条很窄的带相连( 如图1 2 ) 。另外如果缓冲区边界的交点个数较多时，如何去确定两端 的交点也是比较复杂的操作。 基于c d t 的s d s 模型算法是对多边形统一进行约束三角网的剖分，多边形内部和 多边形之间的区域都被分解为简单的三角形区域。剖分的三角网，不仅可以描述多种邻 近关系，检测多边形的邻近冲突，还可以通过对三角网中的三角形分类操作，来完成多 边形的合并。但是如何作有利于合并操作的三角形精确分类，对不同类别的三角形或者 三角形组合又如何操作，这些问题在实际进行应用的过程中仍是难点，三角形的多余计 入、三角形的误删都会影响多边形合并的质量。并且现有的基于c d t 的s d s 模型算法 6 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 只是对规则多边形( 如建筑物) 的合并效果比较好，对于像地质图，土壤类型图等这样 具有大量不规则多边形的地学图件其合并效果并不理想。 一 _ 一 图1 - 2 缓冲区算法合并多边形的局限性 鉴于缓冲区多边形合并算法以及基于c d t 的s d s 模型算法在应用中存在的局限 性，研究拟在前人的经验基础上，结合对多边形合并的研究实践，建立基于c d t 剖分 的相离多边形合并改进模型( 简称为基于c d t 的多边形合并改进模型) ，并基于该模型 开发多边形的自动合并系统，最后对地质图的地质体合并及地籍图的建筑物合并进行应 用研究。 1 4 关键技术和创新点 本文的关键技术如下： l 、c d t 剂分 通过第一层次聚类，把地图数据分成一系列的数据块，在第一层次聚类的基础上对 数据块进行基于网格索引的c d t 剖分。c d t 剖分是进行多边形聚类和多边形合并的关 键。 2 、基于c d t 的多边形聚类模型 这里指的是多边形的第二层次聚类，即多边形的邻近分析。通过基于c d t 的多边 形聚类模型自动识别需要合并的多边形。 3 、基于c d t 的多边形合并模型 通过基于c d t 的多边形合并模型实现多边形的自动合并。 本文的创新点如下： 1 、提出了基于c d t 的多边形聚类改进模型 在对多边形图件c d t 剖分的基础上，提出了基于连接三角形的多边形聚类模型。 2 、提出了基于c d t 的多边形合并改进模型 基于c d t 的多边形合并改进模型包括四个部分：多边形的一次聚类分析、c d t 剖 分、多边形的邻近分析、多边形的合并。在进行多边形的合并时，不是只针对剖分后的 三角形或三角形组合处理，而是结合考虑c d t 剖分后的三角形和原始多边形来获得合 7 浙江大学硕士学位论文 地学制图综合中多边形对象的合并算法研究与应用 并的最终结果。 3 、将多边形合并的改进模型应用于地质图和地籍图中 基于提出的多边形合并改进模型对地质图的地质体合并及地籍图的建筑物合并进 行应用研究。 8 浙江大学硕士学位论文 地学制图综合中多边形对象的合并算法研究与应用 2 基于c d t 的多边形合并改进模型 2 1 基于c d t 的多边形合并改进模型 基于c d t 的多边形合并的改进模型包括四个部分：多边形的一次聚类分析、c d t 剖分、多边形的邻近分析、多边形的合并。 1 、多边形的一次聚类分析 对多边形图件综合的过程中，多边形的聚类是非常重要的操作( m a r t i n ，2 0 0 1 ) 。聚 类分析是研究多要素事物分类问题的数量方法。通过对图件上要合并的目标进行聚类， 一方面可以得到聚类信息，加强对目标分布情况的认识；另一方面通过聚类，每个类被 认为是独立的，类间不存在任何依赖性，从而把整个区域的操作转化为对每个类单独地 操作，从而使效率大大提高( 钱海忠等，2 0 0 5 b ) 。 合并模型需要进行两个层次的聚类，这里论述的是第一层次的聚类。第一层次的聚 类是采用诸如道路网、河流等对多边形目标进行划分，即一个类不能跨越道路或河流， 以防止出现跨越道路或河流的错误合并结果。因此利用道路网和河流等对合并的区域进 行划分，将多边形目标分割为相互独立的集合，对这些独立的集合再分别合并。 第一层次的聚类主要通过人机交互的方式完成。 2 、c d t 剖分 通过第一层次聚类，把地图数据分成了一系列的数据块，要在第一层次聚类的基础 上对数据块进行c d t 剖分。c d t 剖分是模型的关键步骤，是进行多边形邻近分析和多 边形合并的基础。 d e l a u n a y 三角网具有“圆规则”或“最大最小角规则”，即任意三角形的外接圆不 包含其它结点，这使它最大限度地避免了尖锐内角的出现( 普雷帕拉塔等，1 9 8 8 ) 。c d t 是传统d e l a u n a y 三角网的一个改进，它将属于多边形对象的矢量边强制为三角网的边。 c d t 将地图区域分割成了许多简单的三角形区域。这些三角形对于制图综合而言最 重要的一个属性之一就是它能表达丰富的邻近关系，可以用来检测各种空间关系，包括 邻接关系、距离关系、方向关系等。 3 、多边形的邻近分析 第一层次聚类根据道路网、河流等对象的限制，划分出一系列的数据块；接着要对 这些数据块进一步划分，分析相互问的邻近关系，以确定哪些对象需要合并，这也就是 第二层次的聚类。 制图综合中的邻近概念与空间拓扑关系的邻近不同。如果两个多边形共享公用边 界，在拓扑关系上它们互为邻近；而在制图综合中邻近关系是以视觉距离来描述的，比 9 浙江大学预士学位论文地学制图综合中多边形对象的合并算法研究与应用 例尺缩小后，视觉难以分辨其间距离时，就视其为邻近( 艾廷华等，2 0 0 2 ) 。 “将邻近的多边形合并”是制图综合中的一个基本准则，然而如何判断邻近是一项 非常复杂的决策。空间认知中，邻近概念至少受拓扑、几何、语义和g e s t a l t 原则4 个 因素的影响，邻近通常表现为4 种因素综合影响的结果。如果两多边形共享公用边界， 在拓扑关系上它们互为邻近；如果两多边形在拓扑关系上相离，但相互间距离小于规定 阈值，在几何关系上它们是邻近的；当相互间距离十分接近且难以区分时，具有相同或 相近语义特征的多边形具有语义层次的邻近；当相互间距离、语义均难以区分时，确定 邻近关系判断的是方向、大小、形状上相似的g e s t a l t 识别原则( 艾廷华等，2 0 0 2 ) 。 本文是解决相离多边形的合并问题，因此不可能通过拓扑关系来判断邻近。而 g e s t a l t 原则在无规则多边形群邻近关系判断中影响不明显，而且建立g e s t a l t 原则的计 算机模型还是有相当的难度。为了简化模型，也未考虑从语义特征来识别邻近的多边形， 而是限定在几何关系上的邻近。 第二层次聚类是在c d t 剖分的基础上，计算两个多边形之间的连接三角形来进行。 将顶点只归属两个不同多边形的三角形称为连接三角形，即连接三角形有一个性质，就 是连接三角形的有且只有一条约束边e 是属于一个多边形的。通过计算e 边对应的顶点 到e 边的距离d ，如果d o ，说明点v 在v ，蚴的右边。 如果d = o ，说明点v 在v j 也上。 如果d o ，说明点v 在1 ，”的左边。 聊、助、均是三角形的三个顶点，v 卜”、功存储是按照逆时针方向。依次计算内插 点1 ，与三角形三条边”，坳、屹功、v ，v ，的a t e a 2 m ，功，v ) 、a r e a 2 ( v 2 ，功，v ) 、a r e a 2 m ， ，们值为西、而、西。 如果西、西、西都大于零，则点在三角形内。 如果有两个大于零，第三个等于零，则点在三角形的一条边上。 如果仅有一个大于零，另外两个等于零，则点与三角形某个顶点重合。 否则点在三角形外部。 由于三角形也是分块进行网格管理的，为了快速找到点p 所在的三角形，通过搜索 与点p 所在块号相同及与其相邻的三角形链表，计算与链表中三角形三边的西、坊、西， 来获得约束线段起点所在的三角形乃。 确定约束线段的影响区域 与约束线段相交的三角形即约束线段的影响区域。 线段与三角形的相交可以简化为线段与线段的相交，线段与线段相交的条件是：如 果第一条线段的两个端点分别在第二条线段的两侧，同时第二条线段的两个端点在第一 条线段的两侧时，这两条线段是相交的。 线段与线段的相交同样可以借助计算a r e a 2 值来判断。 设线段a b ，其顶点是、v 6 ；线段c d ，其顶点是、坳分别计算： d ：j a r e a 2 ( k ，v c ) ， d d = a r e a 2 ( v 口，访， d a - - a r e a 2 ( r , ，v d ，) ， d b = a r e a 2 ( v e ，1 0 ，v b ) 。 如果以d a = o 并且磊d b = o 那么线段a b 和c d 是相交的。函数b o o l g e t l i n e c r o s s e d ( e d g e s t r u e tc d g c l ，e d g e s t r u c te d g e 2 ) 实现了判断两条边是否相交的功 能，相交返回t r i 甩，否则返回f a l s e 。 如图2 5 ( a ) ，由约束线段的第一个端点4 所在的三角形乃出发，按线段与线段 相交的条件，可以知道乃中与约束线段a b 相交的边是p 2 n ，由相交边可以得到其邻接 的三角形乃，再由乃与约束线段相交的边p 2 p 5 得到下一个三角形乃，这样直到找到约 束线段另一个端点占所在的三角形乃为止。这样就可以确定约束线段的影响区域 i 弘 乃，乃，乃，实际上就是由m t 中三角形的外围边构成的多边形。 1 8 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 在搜索约束线段的影响区域以对其进行三角网局部重建时，将与约束线段相交的所 有边( p 2 p 3 、p 2 p s ) 用一个边链表存储，所经过的三角形( 7 1 ，乃，t d 也用一个三角 形链表存储，影响区域的外围边( p j p z 、p i p 3 、p z p z 、p t 如) 用一个边链表存储，影响 区域的所有点也用一个点链表存储。一旦该约束线段的影响区域完成了三角网局部重 建，就清空这些链表，进行下一条约束边的操作。 要考虑两种特殊情况，一是点在三角形的边上；二是点与三角形的顶点重合。 对于点爿在三角形边上有两种情况，如图2 5 ( b ) 和( c ) 。其中( b ) 又可以分两 种情况进行，如果搜索约束线段起点4 所在的三角形是乃，以后的过程与点在三角形内 一样处理；如果搜索点4 所在的三角形乃时，要进行转换，即将点a 所在的三角形改 为乃，以后的过程与点在三角形中一样处理，否则会把乃排除在约束线段的影响区域 之外。 对于图2 5 ( c ) ，约束线段起点4 所在的边只有一个邻接三角形乃，下一步要找的 三角形是乃中另一条与约束线段相交边p 2 p 3 的邻接三角形乃，以后的过程与点在三角 形内一样。 点彳与三角形顶点重合的情况比较复杂，如图2 5 ( d ) 。搜索彳点所在的三角形 不是乃，而是三角形乃。要快速的由非相交的三角形乃找到与约束线段a b 相交的三 角形乃，其实现主要是依靠边链表中存储了两个邻接三角形的号及三角形链表中三边的 号。在三角形乃中，由包含一点的两边，一个顺时针、另一个逆时针方向去找邻接的 三角形，并记录下来，三角形号不能重复，最多一周就可以将包含4 点的所有三角形都 找到。然后可以确定哪一个三角形与约束线段a b 相交，这样就得到乃。以后的过程与 点在三角形内一样。 b 佥 b 金p tp s 毋岛垒毋圈 图2 - 5 约束边存在的几种情况 约束线段影响区域三角网局部重建 确定了约束线段的影响区域，就要对影响区域进行三角网局部重建。 1 9 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 如图2 - 6 显示了约束线段a b 的影响区域。把约束线段a b 作为起始边，按最大角法 则就可以实现三角网局部重建。 图2 - 6 影响区域三角网局部重建 重建的具体过程如下： a 、在影响区域点集中，以a b 为基边，在它的右边找一个满足与a 、b 两点构成最 大角的点p ，构成第一个三角形4 b p ，。 b 、分别以三角形的两条新边( 如p 口、a p j ) 作为基边，重复上一步扩展生长，当 扩展边是外围边或是使用了两次，结束该边向外扩展，如果新生成的三角形( 爿户j 巴) 的某边是影响区域的外围边( 尸j 2 ) ，就要对该边的两个邻接三角形进行l o p ( 局部优 化处理) ，如两个三角形共圆，需要交换对角线，以保证三角网最优。 l o p 优化时，首要的问题是对两个邻接的三角 形组成的多边形进行空外接圆检测，当数据量较大 时，空外接圆的检测所占用的时间不容忽视，因而在 计算稳定可靠的前提下，尽量减少计算次数和低效的 函数，提高执行效率( 吴宇晓等，2 0 0 5 ) 。下面提出 ” 了一个简化的空外接圆检测算法( 钱海忠等，2 0 0 5 b ) 。 已知四边形4 个顶点j 、肥、飓、肌的坐标分 别是o ，y 1 ) 、，蚴、，y 3 ) 、，助，a l = z n i n v v ：， a 2 = l m 肌地，如图2 7 ，由余弦定理得： 图”l o p 优化 s i n ( a l + 啦鄹5 x l 找由蹿办心蹿如b r y 3 ) ) x ( ( x r x 4 ) ( x r x , ) - o r y 4 ) ( , v t - y 4 ) ) + ( ( x r x 3 ) ( x 2 - x j ) - ( r r x z ) ( y 2 - y 3 ) ) x ( ( x ：- x 4 ) o , l - y d 一( x i x 4 ) ( y 2 - y 3 ) ) 。 m 、飓、飓确定一个圆，根据圆准则可作如下判断： 当点肌位于圆周外，即i - i - a 2 ) o ，不交换对角线； 当s i n ( a 1 坳户0 ，可交换也可不交换对角线； 当s i n ( a 1 + a 2 o ，必须交换对角线。 c 、重复以上两步，将新生成的边作为基边进行扩展生长，直到所有的边都被处理 了一次为止，这样就结束了该约束线段影响区域三角网局部重建。 d 、进行下一约束线段的加入，重复以上三步，直到所有的约束线段都被嵌入为止。 要指出的是如果约束线段a b 刚好将其影响区域分为了两部分，在对a b 扩展之后 要对a b 的反方向即b a 以相同的方式进行扩展。 2 3 多边形的邻近分析 多边形的邻近分析，即多边形的第二层次聚类。在c d t 剖分的基础上，提出了基 于连接三角形的第二层次聚类模型。具体包括以下几个步骤：三角形的分类、冲突检测、 多边形对识别、多边形聚类。 2 3 1 三角形的分类 从三角形的顶点归属和邻接三角形的个数对割分后的三角形分类。 1 、按顶点归属分 i f , 类三角形：三角形的顶点只归属于一个多边形。 类三角形：三角形的顶点归属于两个不同的多边形，卢类三角形也称为连接三角 形。 1 ，类三角形：三角形的顶点归属于三个不同的多边形。 a 类三角形又可以细分为两类三角形： a l 类三角形：在面目标内部的a 类三角形。 毗类三角形：在面目标外部的q 类三角形。 可以通过判断a 类三角形的重心是否存在于一个多边形内部来确定是a l 类三角形 还是a 2 类三角形。 2 、按邻接三角形的个数分 边界三角形：三角形的邻接三角形个数小于3 ，即三角形至少有一条边没有邻接的 三角形。 内部三角形：三角形的邻接三角形个数等于3 ，即三角形的每一条边都有邻接的三 角形。 2 l 浙江大学硕士学位论文 地学制图综合中多边形对象的合并算法研究与应用 如图2 - 8 ，在约束d e l a u n a y 剖分三角网中标出了这几类三角形。 图2 - 8 三角网中三角形的分类 2 3 2 冲突检测 冲突检测就是要判断随着比例尺的缩小，哪些多边形会发生图形显示上的冲突。 冲突检测首先要识别连接三角形，它连接了两个多边形( 如图2 - 8 灰色三角形) 。 根据连接三角形的定义可以推导出一个性质：如果剖分三角形是连接三角形，那么它有 且只有一条边e ( 包括约束线段和新生成的边) 属于多边形d f ，且与约束边e 相对应的 顶点v 属于多边形q ( ，f ) 。 通过计算连接三角形顶点v 到其对边e 的距离d 来判断多边形。和d ，是否是邻近 冲突的。 如果有一个连接三角形的距离冰乙所，那么d f 、d ，就具有邻近冲突，这两个多边形 就要进行合并操作。厶咖为制图综合中要求的目标间的最小距离，它与制图比例尺以及 对象所属的类别有关。 设e 边两个端点的坐标分别是o ， ) 、，y 力，顶点v 的坐标是似，弦) ，计算v 到e 的距离d 。 如图2 - 9 ，过点v 作e 的垂线，与p 的交点坐标为，y d ，v 到e 的距离存在两种情 况： 1 、如果( x , - x j ) 韵 0 ，即交点不在线段上，如图2 - 9 ( b ) ， , 1 。= ( x 2 - x ，) x 咖) 叫y f y ，) 0 2 - y 3 ) ， 以。= 嘞) ( x t - x s ) + ( y l - y 3 ) x ( y l - y o ， a u = r a i n ( d r 。，a j ) 。 浙江大学硕士学位论文地学制图综合中多边形对象的合并算法研究与应用 编程实现时只需要比较和厶，这样可以减少开方运算，提高效率。 ( a ) 图2 - 9 点到线段的距离 ( b ) 2 3 3 多边形对的识别 连接三角形顶点v 到其对边p 的距离d 满足, 2 ，那么连接三角形的顶点归属 的两个多边形是冲突的，将这两个多边形的m 用链表存储起来。将冲突的两个多边形 称为多边形对。 函数v o i d g e t t d p o l y l d ( t r i a n g l e s t r u e t t r i ，i n t & i d l ，i n t & i d 2 ) 实现获取连接三角形归 属的多边形i