温 永 宁，闾 囯 年，陈 旻

矢量空间数据渐进传输研究进展

温 永 宁1，2，闾 囯 年1，陈 旻3

（1.南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210046;2.苏州工业园区测绘有限公司，江苏 苏州 215021;3.香港中文大学太空与地球信息科学研究所，香港 沙田）

渐进传输被认为是解决目前海量空间数据传输与实时用户体验之间矛盾的有效方法。栅格数据渐进传输的相关研究比较成熟，但矢量数据的渐进传输理论和技术还存在问题。为了推进矢量数据渐进传输的相关研究，该文对与矢量数据渐进传输密切相关的二维矢量数据、三维表面模型两种数据的多分辨率表达和渐进传输的研究现状进行归纳与总结，指出相关研究的发展方向，为海量空间数据适用于分布式网络传输提供参考依据。

空间数据;矢量数据;渐进传输

0 引言

传统意义上，空间数据模型可分为矢量和栅格两种;按照数据生产的目标，又可分为4D产品，即数字线画图（DLG）、数字正射影像（DOM）、数字高程模型（DEM）和数字栅格地图（DRG）。如何协调计算机有限的内存、带宽与海量空间数据传输之间的矛盾是当前GIS研究的重要课题。虽然空间数据的类型不同，但在解决海量数据的应用与传输问题上存在一些通用方法：1）对数据进行处理，建立数据的多分辨率表达，根据不同显示需求所采用的比例尺或分辨率，传递相应分辨率的数据。2）采用数据渐进传输的方法，即如果高分辨率的数据可以通过低分辨率数据增加细节增量而得到，则传输时先传递低分辨率的数据，然后根据需要依次传递细节增量，最终得到合适分辨率的数据。

目前，栅格数据渐进传输研究比较成熟，相关国际标准和商业软件已经出现，部分算法和产品也已经实用化。但矢量数据的渐进传输还不是很成熟，主要原因有以下方面：

（1）矢量数据本身存在复杂性。影像/栅格数据结构单一，可以认为是一种结构化数据。矢量数据则比较复杂，可分为要素和要素集合两个层次。其中，要素又包括几何和属性两部分，几何部分包括点、线、面3种对象类型;几何要素之间存在拓扑关系。

（2）矢量数据传输存在多目标与多层次特征。影像/栅格渐进传输的目标仅考虑可视化，以最终的视觉结果为判定标准。矢量数据的应用包含制图输出和空间分析两种不同的功能，其渐进传输与制图综合问题相关联，不仅涉及单个地理要素的多分辨率组织与渐进传输，还涉及多要素之间渐进传输结果可视化的逻辑一致性问题。

（3）缺乏坚实的理论基础。传统的矢量数据渐进传输通常被看做制图综合的逆向过程进行研究。目前，虽然制图综合算法和数据模型被大量引入到渐进传输与数据的多分辨率组织之中，但是制图综合本身尚有很多问题需要解决，如在拓扑一致性、化简结构的适用性方面尚有难以克服的困难。

（4）缺乏集成性。现有的矢量数据渐进传输算法较少考虑现代GIS体系结构，为达渐进传输目的而设计的独立体系的数据结构与模型很难融入GIS主流体系中。此外，基于关系数据库存储是GIS工程中矢量数据的通用存储方案;在制图综合领域虽然设计了一些多分辨率的矢量数据存储结构，但以上结构仍难以方便地映射为GIS关系存储模型。

1 二维矢量数据渐进传输的相关研究

Buttenfield等指出矢量数据渐进传输应该与制图综合紧密相连，是制图综合的逆过程［1－4］。因此，某些制图综合的算法、数据结构经过改造可以应用于矢量数据的渐进传输。

1.1 二维矢量数据渐进传输框架研究

Buttenfield针对线特征提出了GIS数据渐进传输的实现流程［1］，其思想是基于制图综合方法对原始数据进行预处理，生成矢量数据的多分辨率表达模型。该模型的建立步骤：1）根据专题建立图层，图层基于文件方式分离存储;2）对图层中的要素按照重要度排序;3）建立每个几何要素的多分辨率模型。Buttenfield使用D-P算法对线要素进行化简，并基于条带树进行线要素的多分辨率存储，该方法的缺陷在于只能针对线要素保持拓扑关系，不能保持其他空间对象间的拓扑关系。如果要保持拓扑关系，则需附加算法对数据进行预处理。

Bertolotto等提出了基于胞腔复形矢量数据模型的渐进传输组织方案［2－4］，该方案定义了线收缩、面收缩、区域细化、线合并、区域合并、点抽取、线抽取等地图化简基本算子;通过上述算子，可以对地图进行递归化简，建立多分辨率模型。为了维护要素间的拓扑一致性，所有的矢量数据都保存在一个图层中。该方法的效果相当于建立地图级的离散LOD模型，但无法支持要素级别的渐进传输。

与Bertolotto的方案相似，杨必胜等［5］提出了一种基于顶点删除模式的矢量数据渐进传输组织方案，该方案使用“面条模型”表达地图，包含点、线和多边形3种几何对象，其中线和多边形对象由顶点构成。为了建立顶点、线与多边形之间的拓扑关系，将顶点分为3种基本类型：1）一个或两个同层对象共享的顶点;2）两个以上同层对象共享的顶点;3）一个以上多层对象共享的顶点。基于顶点类型和原有拓扑关系，对顶点进行删除操作。类似于Visvalingam-Whyat算法［6］，对删除的顶点进行排序，并将删除的顶点压入堆栈结构中供后续渐进传输使用。该方法较之Bertolotto方法完整地实现了曲线的渐进传输，在删除过程中保持拓扑关系不变，但是没有考虑其它制图综合算子。由于算法需要对整个地图进行渐进式化简，所以最大的问题在于无法根据可视区域组织渐进数据流。

Ai等提出了一种基于变化累积模型的矢量数据渐进传输组织方案［7］，定义了“加”、“减”和“替换”3种基本的变化累积操作，通过这3种操作将客户端的实时综合与服务器端的离线综合统一起来。对多边形特征利用层次分解技术，化简成一系列的凸壳和矩形，基于层次树建立几何对象的多分辨率表达。该算法适用于离散的多边形对象（如湖泊、房屋等）的渐进传输。此外，Cecconi等提出了实现矢量数据渐进传输框架，并列出了3个核心研究点［8］：1）渐进传输相关的地图综合算法;2）在客户服务器模型下的数据传输机制;3）客户端矢量数据组合的问题。David等提出了面向服务的矢量数据渐进传输框架［9］，该框架融合了在线制图综合技术，不仅可以在服务器端生成客户端需要显示的SVG文档，还可以为客户端提供下载文档服务，并在后续传输时，通过XML DOM更新客户端的显示。

1.2 矢量数据制图综合与几何化简

目前，制图综合算法被大量应用于矢量数据渐进传输研究中。综合的目的是为了获得特定分辨率的空间数据，由于矢量数据以要素集合的形式组织，所以多分辨率矢量数据被分为两个级别：1）要素级的算法主要是针对曲线和多边形边界的化简;2）要素集合级的算法则是要素之间制图综合过程，包括合并、移位、夸张等过程。

制图综合的基础在于空间数据的化简算法，其中最重要的是曲线的化简。曲线的化简算法类型较多，如点删除算法（以 D-P算法和 Visvalingam－Whyat算法为代表）、重采样算法（以Li-Openshaw算法为代表）、基于小波分析的算法、曲线层次结构方法、分形方法、组合优化方法、网格化方法等。

Douglas-Peucker算法（简称 D-P算法）是最常用的一种曲线数据压缩算法。该算法基于点删除原理，通过递归地删除距离曲线两个端点连线距离最近的点实现曲线压缩。大量曲线压缩和曲线化简算法是基于对D-P算法的改进而实现的［10］。另外一种点删除算法是Visvalingam-Whyat算法（简称VW算法），该算法的原理是利用曲线上相邻的3个点构成三角形，如果该三角形是所有三角形中面积最小的，则可以将中间的点从三角形删除，化简过程迭代到曲线中剩下两个点为止［11］。Wang等对V-W算法进行了扩展，称为Bend Simplification算法;该算法通过分析几何对象的特征，删除时的判断因子不再是三角形面积，而是边界围成的凸壳和凹陷部分，同时该算法还集成了删除、膨胀和合并的制图综合算子［12］。Yang等的算法均是在V-W算法基础上考虑要素间拓扑关系的改进版本［13－16］。基于点删除的算法与条带树、BLG树、多尺度线性树等多分辨率的数据结构联系紧密，算法的迭代运行过程可以由这些结构记录，并通过“回放”实现渐进传输。

Li-Openshaw算法［17］是一种基于自然规律的自适应线状要素综合算法，其原理是用与比例尺相关的圆在原有曲线上滑动，对曲线进行重采样，获得综合结果。其过程是对于特定的显示分辨率，随着比例尺变小，一个大的多边形会形成一个小多边形;当该多边形只能用一个点表示时，就达到了极限尺寸。朱鲲鹏等对算法做了进一步改进，主要考虑了曲线上极大值和采样圆与曲线多点相交的问题［18］。

基于小波的算法是实现曲线化简的另一条途径。Saux将B－样条与小波分析相结合，针对需要光滑和连续性的曲线，进行曲线化简研究［19］。吴凡利用Mallat算法，研究了获取整数尺度上曲线的综合问题，通过建立多尺度表达的一致性约束模型，对细节信息进行增补和阈值调控，实现了介于任意两个整数尺度之间的线状特征空间数据近似表达［20］。Wang等基于小波分析理论，研究了基于小波多尺度分析的等高线数据压缩模型和算法，利用D-P算法对小波变换的边界进行预处理，提取特征点，并在小波压缩之后恢复特征点，保持了等高线的拓扑一致性［21－23］。

构建曲线的层次结构并以此为化简依据是矢量数据化简的另一种策略。Guo提出了一种基于线对象结构的渐进式化简算法，该算法基于线上的特征（极值点、凸点、拐点、单调区间）建立线结构及其层次关系，以此为约束对曲线进行化简［24］。艾廷华等基于曲线弯曲层次的概念，通过将曲线自身作为约束，建立曲线的带约束Delaunay三角网，并根据三角形与顶点、曲线的关系对其进行分类;在分类基础上，对Delaunay三角网应用剥皮算法，记录剥皮的过程，根据被剥皮的三角形类型，迭代构建曲线的二叉树组织结构，再根据弯曲的层次结构，对曲线进行化简［25］。王桥等利用分形原理对线状要素化简的步长选择问题进行研究，所提出的方法顾及了制图综合的目的，强调图形形状结构特征，调整自动综合的效果，并能与其它方法配合使用［26，27］。Poorten等提出的算法能够同时对多条曲线进行综合，通过三角形之间的联通关系，维护曲线之间的拓扑一致性［28］。杜维等提出了一种基于组合优化策略的多边形化简算法，其基本思想是以多边形轮廓为目标，依据曲线特征点将其分解为一系列的弯曲特征，并对此弯曲特征集实施组合优化;通过将入围的弯曲首尾相连，该算法可被应用于多边形的化简［29］。

网格法是将地理坐标表示成一系列的网格单元，利用网格单元作为控制结构实现要素的化简。在这一方面，Dutton提出了层次坐标系统（Hierarchical Coordinate System）的概念，同时基于地球表面的结构采用QTM（Quaternary Triangular Mesh）加以描述［30－32］。QTM是相互嵌套的层次性三角形网格，覆盖全球;其网格单元按照一定规则编码，一个网格单元可以代表一定分辨率下确定的地理位置。在某一分辨率下，一条曲线可以用一系列的顶点所经过的单元ID表示;低分辨率的几何要素由高分辨率的要素综合得到，综合过程受到QTM层次结构的控制，通过将同属于一个低分辨率网格单元的顶点进行合并实现线状要素的化简。Wang等提出了适应性网格模型（Adaptive Lattice Model），并基于此建立了线和多边形的综合算法［33－35］。适应性网格类似于一个CCD相机阵列，提供了一个固定分辨率控制机制，在该网格分辨率下，点的坐标可以被四舍五入到网格上，某些顶点可以被合并，多边形可以被聚合或者转换成线状要素。

1.3 二维矢量数据的多分辨率组织

矢量数据的多分辨率包含要素集合和要素两个层次。通常通过树结构的层次性生成要素集合多分辨率，常采用反应树及其变种实现要素集合的多分辨率组织;通过化简综合算法生成线要素的多分辨率组织，常采用基于D-P算法所产生的多分辨率曲线存储模型，包括STRIP树、BLG树和多叉树。

反应树（Reactive Tree）采用空间数据库中进行多分辨率空间对象管理和索引的结构［36－38］，它是一种多路树，其入口可分为对象和子树两种。每个节点包含若干入口，非叶子节点可以同时包含两种节点，而叶子节点只能包含对象入口;每种入口都包含一个重要值指标以反映节点的多分辨率特性。反应树可基于R树、球树、KD树实现。李爱勤［39］讨论了一种基于四叉树的多分辨率数据组织模型，被认为是反应树的四叉树变种。

GAP树（Generalized Area Partitioning tree）是管理平面分割的多分辨率组织结构［40］。在GAP树中，一个节点对应一个被综合的多边形区域，节点下还可以包含不重要的低级多边形，追踪叶子到根的过程反映了多边形综合的过程。C-Tree是基于GAP树的一种实现［41］。

STRIP树也称条带树，是一种二叉树［42］，它通过记录低精度曲线到高精度曲线的增量来表示多分辨率数据，可存储任意的曲线结构。该树可应用于D-P算法，通过记录条带树抽取结点过程实现多分辨率的表达。

BLG树（Binary Line Generalization tree）作为反应树的补充［43，44］，也是基于二叉树结构，其主要思想在于将D-P算法执行的中间过程按尺度特征进行记录，建立细节累加模型。

多尺度线性树（Multi-Scale Line Tree，MSLT）借鉴了STRIP树的思想［45］，但它是多路树而非二叉树，结构的每个层次对应一个隐含的最大条带宽度。此外，MSLT是面向节点的，在每个层次存储节点，这些节点是更高层次的细节的中间层次。

多叉树常应用于多边形的多分辨率组织［46］，将按D-P算法抽取的不同层次细节的节点存储在多叉树结构索引矩阵中，在矩阵同一行中描述的具有等值偏移量的节点属于同一等级，从而实现数据的层次细节存储。基于多叉树结构，任应超等提出了一种面向线的多尺度表达的数据结构，该结构使用VW算法生成多分辨率曲线模型，支持曲线数据的编辑，利用关系模型将不同分辨率的数据存储于不同的关系表中，以提升数据库的访问效率［47］。

2 三维表面模型的化简与渐进传输

不规则三角网（Triangulated Irregular Network，TIN）也称为三角形网格（Triangle Mesh）或简称网格（Mesh）。因为任何三维表面都可以使用不规则三角网进行逼近，所以不规则三角网是最为常用的一种三维表面建模方法。TIN是三维虚拟场景对象建模的基本模型，也是除栅格之外另一种表示DEM的数据结构，所以TIN的多分辨率表达和渐进传输既包括空间数据领域的研究工作，也包括计算机图形学及三维动画、游戏方面的工作。

2.1 三维表面模型的化简算法

TIN的化简是生成多分辨率模型的关键，将化简后的模型组成序列就是该模型的多分辨率表达。按照在生成过程中使用的算子，可以将TIN的化简算法分为顶点删除法、重新布点法、顶点聚合法、区域合并法、边折叠法、三角形折叠法以及基于小波分析的算法等。

顶点删除法基本思想是删除满足一定条件的顶点，并对由此产生的空洞重新三角化，从而达到简化模型的目的［48］。该算法首先将网格中的顶点划分为简单顶点、复杂顶点、边界顶点、拐点和内部边界顶点，然后根据相邻顶点拟合局部切平面，计算顶点到拟合切平面的距离。若距离小于指定阈值，则删除该顶点，对删除顶点后所遗留的空洞进行局部三角剖分，压缩过程中不能改变模型的拓扑关系。此后，Schroeder对算法进行了改进，通过剪切、缝合等操作，使得算法在构建LOD模型的过程中可以实现拓扑关系的修改［49］。

重新布点法基本思想是首先确定简化模型中的顶点个数，按照一定的规则将一些顶点插入原始模型中，形成新旧模型共存的模型，然后删除原始模型中的点，对删除顶点后的空洞进行三角化，得到新顶点构成的简化模型［50］。该算法中新点的分布采用排斥力算法，即先随机分布新点，然后计算新点间的排斥力，根据排斥力在网格上移动这些新点，使它们重新分布。排斥力的大小与新点间的距离、新点所在三角面片的曲率、面积等有关。

顶点聚合法的基本思想是通过空间划分将模型中的顶点划分为一系列顶点簇，然后把簇内的点集聚合为一个顶点。该操作不依赖于原始模型的拓扑关系，仅与其几何信息有关。最早的顶点聚类方法是均匀顶点聚类方法，该算法根据顶点的重要性对模型的顶点进行分类，并将模型所在的空间按用户定义的大小剖分为若干个规则格网，把构成模型的所有顶点划分到相应的子格网单元中，遍历划分的格网单元，按照一定的规则（如距离单元内所有顶点的加权平均距离）选择可以代表整个格网单元中所有顶点的聚合顶点，最终得到由代表性顶点构成的LOD模型［51］。Luebke等通过建立空间自适应八叉树剖分对上述算法进行了改进［52，53］。Low等提出利用立方体、球等任意简单的形状作为空间剖分的基本单元，并将单元的中心定位于单元内重要度最高的顶点，对于同时被包含在多个单元内的顶点，根据其与各单元中心的距离远近进行分配［54］。

区域合并算法通过合并表面模型中的相邻面片以达到降低模型复杂度的目的。其中的超面算法是比较经典的区域合并算法，该算法基于共面准则把表面模型分割成连通区域，分别用多边形面片代替各个区域，并对多边形面片的边界进行简化，最后重新生成三角化多边形面片［55，56］。

边折叠法是一个迭代的化简算法，它按照一定的准则删除三角网中的边并重构三角网，以达到化简模型的目的。边折叠可以在化简过程中形成自然的层次结构，便于多分辨率模型的构建。Hoppe最先提出了边折叠化简方法，该方法综合考虑了顶点数目、近似表达误差以及网格结构优化，可以获得非常好的结果，但运算效率较低，后续研究主要集中在如何提高边折叠的效率［57］。Ronfard等相继提出了新的边折叠的判别标准［58－62］。

三角形折叠法也是一种迭代化简方法。该方法先将满足折叠条件的三角面片的三个顶点合并为一个顶点，然后删除退化的三角面片。一次三角形折叠相当于两次边折叠，因此三角形折叠的效率要优于边折叠。Hamann首先提出了基于三角形折叠的表面LOD模型构建算法，该算法是基于三角形三个顶点曲率和三角形的形状确定三角形权值，权值最低的三角形最先被折叠为一个顶点［63］。Isler以顶点的重要度决定基本操作算子（边折叠或三角形折叠），以三角形的视觉重要度确定三角形折叠顺序［64］。周昆利用折叠后的新点与被折叠三角形相关的三角形集合中各三角形所在平面的距离最大值的倒数作为权值，确定三角形的折叠顺序［65］。

小波方法利用小波的多分辨率分析特性（Multi-Resilution Analysis，MRA），将模型分解为拟合域（即化简后的模型）和细节域。Lounsbery最早将小波方法应用于三维表面模型化简，他将具有分割连通性的曲面进行了小波分解［66，67］。此后，Eck等提出了将任意曲面转换为分割连通性的方法，使得MRA可以应用于任意形状的三维模型［68］。

2.2 三维表面模型的调度与传输策略

虽然网格化简方法可以有效降低三维表面模型的数据量，但在处理海量数据时依然不能满足绘制效率和用户交互的要求，需与LOD、渐进传输等优化策略相配合，实现三维表面模型的调度与传输。

视点相关的LOD通过区域视觉重要度来定义，可以根据需要对局部格网区域有选择地进行加密或者简化，使得视觉重要度比较高的区域利用较高的分辨率表示。Gross在地形渲染中提出了地形表面模型的自适应视相关LOD表示法，并定义了用于改变局部区域模型质量的小波空间滤波算子［69］。Lindstrom等针对大数据量的地形渲染也提出了类似的方法［70－72］。Wang等设计并实现了一种具有拓扑保持特性的自适应视相关LOD模型的动态构建及实时更新方法［73］。

渐进网格（Progressive Mesh，PM）技术通过记录迭代TIN的化简过程形成化简模型和增量数据的形式，通过化简的逆向过程逐步恢复网格，实现网格的渐进传输［74］。Pajarola等进一步提出了压缩渐进网格算法，在传输之前对数据进行压缩［75，76］;Southern等结合视点相关传输方法进一步提高了渐进传输 效 率［77，78］。渐 进 几 何 压 缩 （Progressive Geometry Compression，PGC）通过对规则或者半规则网格进行小波变换，并在各个子带的小波系数间建立零树结构，进行零树编码生成渐进压缩码流，在码流的任意位置截断，解码后可以获得原始模型的一个近似表示［79］。

由以上研究可以看出，三维表面模型的化简与压缩的核心是通过某种判别规则从模型中删除顶点、边或者三角形等几何单元，并对删除后模型进行空洞填补处理，最后通过迭代式的化简及其逆向过程从而实现模型的渐进传输。渐进网格技术确立了三维表面模型渐进传输的基本方法，经过多年发展已成为三维数据压缩与传输的经典算法。

3 结论

目前，渐进传输已经成为解决海量空间数据与网络用户交互、快速响应之间矛盾的基本方法。虽然影像/栅格的渐进传输已经得到比较好的解决，但矢量数据的渐进传输问题尚未得到真正的解决。通过与三维表面模型渐进传输的研究对比，矢量数据渐进传输研究需要克服如下问题：

（1）明确矢量地理数据渐进传输的目标与定位。当前大量研究将矢量地理数据的渐进传输与制图综合相联系，试图应用制图综合的相关技术解决渐进传输问题。但制图综合的首要目的是生产满足制图需求的多比例尺地图，而矢量地理数据渐进传输的首要目标是在保证可视化结果正确的前提下，降低网络负载，提升用户的交互操作体验效果。这两种技术存在应用需求方面的差异，因此需要针对矢量数据渐进传输的目标需求，设计相关算法。

（2）平衡矢量数据化简算法效率与拓扑关系保持之间的依赖性。矢量地理数据化简是渐进传输的基础，但是当前无论是多要素制图综合还是单要素几何化简都在纯几何层次考虑问题，算法需要大量的浮点运算，难以保证效率。仅对单个地理要素进行化简，难以维持要素间的拓扑关系;但考虑要素间的拓扑关系保持问题，则又势必极大地增加计算量。新的算法设计关键在于确定矢量数据化简与拓扑关系保持的平衡点，寻找新的控制结构，解除两者之间的依赖。

（3）设计新型的数据结构，降低数据冗余和存储的复杂性。当前的相关算法都是基于树的数据结构，需要指针维护层次关系，还需要额外的存储空间，无法真正实现无冗余传输。同时树结构与矢量地理数据的关系数据的存储结构难融合，实际应用困难。因此需要寻找多分辨率之间的插入隐含关系，将增量数据的插入位置隐含在数据流中，实现增量数据的无冗余传输。

［1］BUTTENFIELD B P.Transmitting vector geospatial data across the Internet［EB/OL］.Proceeding GIScience′02.http：//www.springerlink.com/content/4kgffqdnmk962brv/fulltext.pdf.2011－09－27.

［2］BERTOLOTTO M，EGENHOFER M J.Progressive vector transmission［EB/OL］.7th ACM Symposium on Advances in Geographic Information Systems，1999.http：//delivery.acm.org/10.1145/330000/320172/p152-bertolotto.pdf ip＝137.189.162.186＆CFID＝44877011＆CFTOKEN＝80335071＆＿＿acm＿＿＝1317107472＿fcb8f0aa11cfa6c579111a684300ad9e.2011－09－27.

［3］BERTOLOTTO M，EGENHOFER M J.Progressive transmission of vector map data over the World Wide Web［J］.GeoInformatica，2001，5（5）：345－373.

［4］BERTOLOTTO M.Geometric Modeling of Spatial Entities at Multiple Levels of Resolution［D］.University of Genova，1998.

［5］杨必胜，李清泉.World Wide Web（WWW）上矢量地图数据的多分辨率传输算法［J］.测绘学报，2005，34（4）：355－360.

［6］VISVALINGAM M，WHYATT J D.Line generalization by repeated elimination of points［J］.Cartographic，1993，30（1）：46－51.

［7］AI T H，LI Z L，LIU Y L.Progressive transmission of vector data based on changes accumulation model developments［EB/OL］.11th International Symposium on Spatial Data Handling 2005.http：//www.springerlink.com/content/u371gh8w85865mkm/fulltext.pdf.2011－09－27.

［8］CECCONI A，WEIBEL R.Map generalization for on-demand web mapping［EB/OL］.GIScience 2000.http：//citeseerx.ist.psu.edu/viewdoc/download;jsessionid＝ 85FD7EF9788A744D815 CFCE6A21BD8A7？doi＝10.1.1.90.9161＆rep＝rep1＆type＝pdf.2011－09－27.

［9］DAVID C C，MARIO M T，ANSELMO C，et al.Aservice-oriented architecture for progressive transmission of maps［EB/OL］.IX Brazilian Symposium on GeoInformatics.http：//www.geoinfo.info/geoinfo2007/papers/S5P2.pdf.2011－09－27.

［10］DOUGLAS D H，PEUKER T K.Algorithms for the reduction of the number of points required to represent aline or its caricature［J］.The Canadian Cartographer，1973，10（2）：112－122.

［11］VISVALINGAM M，WHYATT J D.Line generalization by repeated elimination of points［J］.Cartographic Journal，2003，30（1）：46－51.

［12］WANG Z，MULLER J C.Line generalization based on analysis of shape characteristics［J］.Cartography and Geographic Information Science，1998，25（1）：3－15.

［13］YANG B S，PURVES R S，WEIBEL R.Implementation of progressive transmission algorithms for vector map data in webbased visualization［A］.Proceedings XXth ISPRS Congress，Commission IV，2001.25－31.

［14］YANG B S.A multi-resolution model of vector map data for rapid transmission over the internet［J］.Computers ＆ Geosciences，2005，31（5）：569－578.

［15］YANG B S，PURVES R S，WEIBEL R.Efficient transmission of vector data over the internet［J］.International Journal of Geographical Information Science，2007，21（2）：215－237.

［16］任应超，李文雯，杨崇俊.一种用于渐进传输的多分辨率曲线模型［J］.计算机工程，2008，34（8）：25－28.

［17］LI Z L，OPENSHAW S.Linear feature′s self-adapted generalization algorithm based on impersonality generalized natural law［J］.Translation of Wuhan Technical University of Surveying and Mapping，1994（1）：49－58.

［18］朱鲲鹏，武芳，王辉连.Li-Openshaw算法的改进与评价［J］.测绘学报，2007，36（4）：450－456.

［19］SAUX E.B-spline functions and wavelets for cartographic line generalization［J］.Cartography and Geographic Information Science，2003，30（1）：33－50.

［20］吴凡.基于小波分析的线状特征数据无级表达［J］.武汉大学学报（信息科学版），2004，29（6）：488－491.

［21］WANG Y H，ZHU C Q.The vector relief data compression based on the mulit-band wavelet［J］.Science of Surveying and Mapping，2003，28（3）：66－68.

［22］朱长青，王玉海，李清泉，等.基于小波分析的等高线数据压缩模型［J］.中国图象图形学报（A辑），2004，9（7）：841－845.

［23］王玉海，朱长青.基于小波分析的线状要素压缩优化的综合性研究［J］.武汉大学学报（信息科学版），2007，32（7）：630－632.

［24］GUO Q S.A progressive line simplification algorithm［J］.Wuhan Technical University of Surveying and Mapping，1998（1）：52－56.

［25］艾廷华，郭仁忠，刘耀林.曲线弯曲深度层次结构的二叉树表达［J］.测绘学报，2001，30（4）：343－348.

［26］王桥，吴纪桃.制图综合方根规律模型的分形扩展［J］.测绘学报，1996，25（2）：104－109.

［27］王桥，吴纪桃.一种新分维估值方法作为工具的自动制图综合［J］.测绘学报，1996，25（1）：10－16.

［28］POORTEN V D，JONES C B.Customisable line generalization using Delauney triangulation［EB/OL］.Proceedings of the 19th ICA conference in Ottawa，1999.http：//www.comp.glam.ac.uk/pages/staff/pmvander/.2011－09－27.

［29］杜维，艾廷华，徐峥.一种组合优化的多边形化简方法［J］.武汉大学学报（信息科学版），2004，29（6）：548－550.

［30］DUTTON G，BUTTENFIELD B P.Scale change via hierarchical coarsening：Cartographic properties of quaternary triangular meshes［A］.Proc.16th Int.Cartographic Conference［C］.1993.847－862.

［31］DUTTON G.Digital map generalization using a hierarchical coordinate system［A］.Proc.Auto Carto 13.（Seattle，WA）Bethesda，MD：ACSM/ASPRS，1997.367－376.

［32］DUTTON G.Scale，sinuosity and point selection in digital line generalization［J］.Cartography and Geographic Information Science，1999，26（1）：33－53.

［33］WANG P T，DOIHARA T，LU W.Spatial generalization：An adaptive lattice model based on spatial resolution［EB/OL］.Symposium on Geospatial Theory，Processing and Applications，2002.http：//www.isprs.org/proceedings/XXXIV/part4/pdfpapers/291.pdf.2011－09－27.

［34］WANG P T，DOIHARA T，LU W，et al.A resolution-driven generalization approach for linear and areal object［EB/OL］.Geoscience and Remote Sensing Symposium.http：//ieeexplore.ieee.org/stamp/stamp.jsp？tp＝＆arnumber＝1294431.2011－09－27.

［35］DOIHARA T，WANG P T，LU W.An adaptive lattice model and its applications to map simplification［EB/OL］.Symposium on Geospatial Theory，Processing and Applications，2002.http：//www.isprs.org/proceedings/XXXIV/part4/pdfpapers/301.pdf.2011－09－27.

［36］OOSTEROM P V.The reactive-tree：A storage structure for a seamless，scaleless geographic database［A］.Auto-Carto 10［C］.1991.393－407.

［37］OOSTEROM P V.A storage structure for a multi-scale database：The reactive-tree［J］.Computers，Environment and Urban Systems，1992，16（3）：239－247.

［38］OOSTEROM P V.Reactive Data Structure for Geographic In-formation Systems［M］.Oxford University Press，1994.

［39］李爱勤.无缝空间数据组织及其多比例尺表达与处理研究［D］.武汉大学，2001.

［40］OOSTEROM P V.The GAP-tree，an approach to on-the-fly map generalization of an area partitioning［A］.MULLER J C，LAGRANGE J P，WEIBEL R.GIS and Generalization：Methodology and Practice［C］.Taylor ＆ Francis，London，1995.120－133.

［41］田鹏，郑扣根，张引，等.基于C-Tree的无级比例尺GIS多边形综合技术［J］.中国图象图形学报（A辑），2001，6（8）：765－770.

［42］BALLARD D H.Strip trees：A hierarchical representation for curves［J］.ACM Communications.1981，24（5）：310－321.

［43］OOSTEROM P V.A reactive data structure for geographic information systems［EB/OL］.Auto-Carto 9，1989.http：//www.mapcontext.com/autocarto/proceedings/auto-carto-9/pdf/a-reactive-data-structure-for-geographic-information-systems.pdf.2011－09－27.

［44］OOSTEROM P V.Reactive Data Structures for Geographic Information Systems［D］.Leiden University，1990.

［45］JONES C B，ABRAHAM I M.Line generalization in a global cartographic database［J］.Cartographica，1987，24（3）：32－45.

［46］毋河海.基于多叉树结构的曲线综合算法［J］.武汉大学学报（信息科学版），2004，29（6）：479－483.

［47］任应超，李文雯，杨崇俊.一种用于渐进传输的多分辨率曲线模型［J］.计算机工程，2008，34（8）：25－28.

［48］SCHROEDER W J，ZARGE J A，LORENSEN W E.Decimation of triangulation meshes［J］.Computer Graphics，1992，26（2）：65－70.

［49］SCHROEDER W J.A topology modifying progressive decimation algorithm［A］.Proceedings of Visualization′97［C］，IEEE Computer Society Press，1997.

［50］TURK G.Retiling polygonal surface［J］.Computer Graphics，1992，26（2）：55－64.

［51］ROSSIGUAC J，BORREL P.Multi-resolution 3D approximation for rendering complex scenes［A］.FALCIDIENO B，KUNII T.Geometric Modeling in Computer Graphics［C］.1993.455－465.

［52］LUEBKE D.Hierarchical structures for dynamic polygonal simplification［A］.SIGGRAPH′96［C］.1996.96－106.

［53］LUEBKE D，ERIKSON C.View-dependent simplification of arbitrary polygonal environments［A］.ACM Computer Graphics，31（Proc.of SIGGRAPH′97）［C］.1997.199－208.

［54］LOW K L，TAN T S.Model simplification using vertex-clustering［A］.COHEN M.Proceedings of 1997 Symposium on Interactive 3D Graphics［C］.1997.75－82.

［55］KALVIN A D，TAYLOR R H.Superfaces：Polyhedral approximation with bounded error［A］.Medical Imaging：Image Capture，Formatting and display，SPIE［C］.1994，2164：2－13.

［56］KALVIN A D，TAYLOR R H.Superfaces：Polyhedral mesh simplification with bounded error［J］.IEEECG＆A，1996，16（3）：64－77.

［57］HOPPE H，DEROSE T，DUCHAMP T，et a1.Mesh optimization［J］.Computer Graphics，1993，27（SIGGRAPH′93）：19－26.

［58］RONFARD R，ROSSIGNAC J.Full-range approximation of triangulated polyhedral［A］.Proceedings of EUROGRAPH′96［C］.1996.67－76.

［59］GARLAND M，HECKBERT P S.Surface simplification using quadric error metrics［A］.SIGGRAPH′97［C］.1997.209－216.

［60］LINDSTROM P，TURK G.Fast and memory efficient polygo-nal simplification［A］.ROBERT M.Proceedings of IEEE Visualization′98［C］.1998.279－286.

［61］陶志良，潘志庚.复杂场景中动态简化层次的构造［J］.中国图象图形学报（A辑），1998，3（12）：1032－1036.

［62］盛业华，王永波，闾国年，等.一种基于边收缩的3维表面模型数据压缩算法［J］.中国图象图形学报，2007，12（1）：159－163.

［63］HAMANN B.A data reduction scheme for triangulated surface［J］.Computer Aided Geometric Design，1994，11（3）：197－214.

［64］ISLER V，LAU W H，GREEN M.Real-time multi-resolution modeling for complex virtual environments［EB/OL］.Proceedings of Virtual Reality Software and Technology′96.http：//www.cs.cityu.edu.hk/～rynson/papers/vrst96.pdf.2011－09－27.

［65］周昆，潘志庚，石教英.基于三角形折叠的网格简化算法［J］.计算机学报，1998，21（6）：506－513.

［66］LOUNSBERY M.Multiresolution Analysis for Surfaces of Arbitrary Topological Type［D］.University of Washington，1994.

［67］LOUNSBERY M，DEROSE T D，WARREN J.Multiresolution analysis for surfaces of arbitrary topological type［J］.ACM Trans.on Graphics，1997，16（1）：34－73.

［68］ECK M，DEROSE T，DUCHAMP T，et a1.Multiresolution analysis of arbitrary meshes［A］.ACM Computer Graphics（Proc.of SIGGRAPH′95）［C］.1995.173－182.

［69］GROSS M H，GATTI R，STAADT O.Fast multiresolution surface meshing［A］.NIELSON G M，SILVER D.IEEE Visualization′95 Proceedings，1995.135－142.

［70］LINDSTROM P，KOLLER D，RIBARSKY W，et a1.Real-time，continuous level of detail rendering of height fields［A］.Proc.SIGGRAPH′96［C］.1996.109－118.

［71］LINDSTROM P，PASCUCCI V.Visualization of large terrains made easy［A］.Proc.IEEE Visualization 2001［C］.2001.363－370.

［72］DUCHAINEAU M，WOLINSKY M，SIGETI D E，et a1.Roaming terrain：Real-time optimally adapting meshes［A］.Proc.IEEE Visualization′97［C］.1997.81－88.

［73］WANG Y B，SHENG Y H，ZHANG K，et a1.Efficient implementation of adaptive view-dependent mesh simplification［A］.Proceeding of SPIE，Geoinformatics′2007.Cartographic Theory and Models［C］.2007，16751：1－13.

［74］HOPPE H.Progressive meshes［A］.Proceedings of SIGGRAPH′96［C］.1996.99－108.

［75］PAJAROLA R，ROSSIGNAC J.Compressed progressive mesh［J］.IEEE Transactions on Visualization and Computer Graphics，2000，6（1）：79－93.

［76］ALLIEA P，DESBRUN M.Progressive compression for lossless transmission of triangle meshes［A］.Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques［C］.2001.195－202.

［77］SOUTHERN R，PERKINS S，BARRY S，et a1.A stateless client for progressive view-dependent transmission［A］.Proceedings of the Sixth International Conference on 3D Web Technology［C］.2001.43－50.

［78］KIM J，LEE S，KOBBELT L.View-dependent streaming of progressive meshes［A］.Proceedings of the Shape Modeling International 2004［C］.2004.209－220.

［79］KHODAKOVSKY A，SCHRODER P，SWELDENS W.Progressive geometry compression［A］.Computer Graphics Proceeding，Annual Conference Series，ACM SIGGRAPH［C］.2000.85－94.

An Overview on Progressive Transmission of Vector Spatial Data

WEN Yong－ning1，2，LV Guo－nian1，CHEN Min3
（1.KeyLaboratoryofVirtualGeographicEnvironment（MinistryofEducation），NanjingNormalUniversity，Nanjing210046;2.SuzhouIndustrialParkSurveyCO.LTD，Suzhou215021;3.InstituteofSpaceandEarth InformationScience，TheChineseUniversityofHongKong，ShatinH.K.，China）

The progressive transmission strategy is considered to be an effective way to balance contradiction between scheduling the massive spatial data and the real time user experience.Research on the progressive transmission of raster data is fairly sophisticated and mature，while various problems of the theory and technology of vector data′s progressive transmission are still required to be tackled.Aiming at promoting the research of vector data′s progressive transmission，and providing references for research of the distributed network transmission of massive spatial data，this paper focuses on leveraging and summarizing the complementary past and ongoing research of the multi-resolution expression and the progressive transmission of 2D vector data and 3D surface model data which is closely related to the progressive transmission of vector data.

spatial data;vector data;progressive transmission

P208

A

1672－0504（2011）06－0006－07

2011－07- 28;

2011－10－27

国家“863”重点课题子课题项目“基于广域网的虚拟月球环境构建研究”（2010AA122202）;国家自然科学基金项目“像素无损的矢量地理数据高效传输机制研究”（41001223）;江苏高校优势学科建设工程资助项目

温永宁（1977－），男，博士，讲师，主要研究方向为虚拟地理环境、3D GIS。E－mail：wenyn＠msn.com