基于拓扑一致的地图概括过程和多尺度空间数据库外文翻译资料

 2022-08-08 03:08

英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料

摘要：多尺度空间数据库的一项重要要求是：对于各个尺度（可以检索它们）的所有尺度，都必须在单个要素内以及共同显示的要素之间保持拓扑一致性。在这

里，我们展示如何增强基于三角剖分的分支修剪概括过程，以使其输出可用于构建拓扑一致的多尺度数据结构。缺乏顶点过滤的现有分支修剪方法的主要局限性是通过应用拓扑一致的顶点优先级标记过程来克服的。通过引入边缘重采样技术提供了对修剪的单面和双面应用的控制，而且还改进了分支修剪的泛化方法，展示了使用该技术的实验结果。

  1. 简介

在多个级别上进行可视化和分析空间数据是地理信息许多应用程序的基础。在传统上，通过生成一系列比例尺的地形图系列，可以满足对多个细节级别的要求。当前，这种维护离散的单比例版本或多种表示形式的方法反映在地理信息系统及其关联的空间数据库技术中。因此，GIS中的原始空间对象使用诸如折线和多边形之类的几何原始物来表示特定于比例尺的地图特征。某些GIS确实会以不同的比例维护多个版本，但是数据库访问工具通常仅限于检索少数几个存储的固定比例的表示形式。通常，数据库无法访问中间细节级别的几何图形，因此无法有效适应许多GIS应用程序的特定比例要求。因此，需要提供对空间物体的多个细节级别的逐步访问的多尺度空间数据库。

1.1多尺度空间数据访问方案

建立数据结构以支持对线和多边形等简单空间对象进行多尺度访问的想法可以追溯到1980年代初。条形树（Ballard 1981）在二叉树中分层组织线性特征的几何形状，其节点通过包围矩形（条）来表示近似的线段。弧形树（Gunther 1988）提供了一种变体，其中近似的线段由椭圆索引。在van Oosterom（1994）的Reactive数据结构中，另一种二叉树结构BLG-tree与空间对象的R-tree索引相结合，该对象覆盖了指定的比例范围。在Jones和Abraham（1986）的基于四叉树的多尺度线树和PR文件中（Becker等人1991）引入了分层方法，在该方法中将按比例缩放优先的几何分配给预先指定的比例间隔。

这些技术的实验实现已基于基本的线路简化程序，通常是Douglas-Peucker算法。这导致了所得数据库的一些主要限制。一个问题是由算法生成的顶点的分层排序可能不对应于相应顶点的阈值的单调变化。因此，与较高级别的顶点相比，层次结构中较低的某些顶点可能提供更重要的形状信息。另一个更具挑战性的问题是，不能保证检索到的中间比例尺几何结构本身或与相邻地图要素的拓扑结构保持一致。

Bertolotto和Egenhofer（1999）以及van Putten和van Oosterom（1998）提出了关于完整空间对象（其中可能有多种表示形式）的拓扑一致性问题，他们提出了维持这些完整对象之间一致性的方案 。维护数据库中单个折线和多边形的多个实现之间的拓扑一致性需要线和多边形泛化算法，这些算法可以保证生成拓扑上一致的简化。Jones等人（2000年）曾考虑过此问题，他还提出了一种跟踪拓扑一致性的不同级别的方案。提出了几种以拓扑一致的方式概括线的算法，包括de Berg（1998），Saalfield（1999），van der Poorten and Jones（1999）和Ai等人（2000），但是在算法上却没有什么进展。此类程序在多尺度数据库中对顶点进行优先标记的应用，以确保在检索到的线和面图元细节层次上的拓扑一致性。

在本文中，我们展示了如何增强van der Poorten和Jones（1999）的拓扑一致的“分支修剪”泛化程序，并将其结果用于改善用于构建多尺度数据库的多尺度数据集的质量。本质上，“分支修剪”涉及识别线的“特征”（非常粗略地说，是弯曲之间的线的各个部分）并有选择地删除它们。该方法基于对线周围的空间进行三角剖分。

之所以选择此过程作为多尺度数据库构建的基础，是因为它在控制概化样式和同时进行多个地图要素的概化方面比任何其他拓扑一致的过程都具有更大的灵活性。Ai等人（2000年）的技术非常相似，但它仅在单个地图要素上运行，一次修剪一侧。通常，分支修剪技术的基本局限性在于，尽管简化了形状，但并没有系统地减少顶点数量。因此，需要一种在保持拓扑一致性的同时过滤冗余顶点的方法。分支修剪的先前实现方式在分支删除后引入不连续性（或“树桩”）方面还受到其他限制，并且缺乏对分支是指行的一侧还是另一侧或两侧的明确控制。

在本文的其余部分中，我们将在第2节中概述多尺度空间数据库体系结构的各个方面，这些体系结构为单个折线和多边形的多分辨率表示提供了支持。在第3节中，对基于三角剖分的分支修剪过程进行了描述，该过程基于van der Poorten和Jones的思想，但将其扩展到除折线之外还适用于多边形，以合并引入问题的解决方案。树桩，并为分支修剪过程的单面或双面应用提供一个选项。提供了将其应用于实际数据的示例。第4节描述并说明了基于三角剖分的拓扑一致优先级标记过程的结果，该过程可用于对多个地图要素的分支修剪结果进行后处理，以消除可能会出现的大量冗余顶点。当下。此处实现的方法采用了Douglas-Peucker算法的原理，并且在此仅用于减少点，而不是简化形状。针对分支修剪量度和过滤器公差值的各种组合，给出了将该程序应用于分支修剪数据的实验结果。本文在第5节结束时总结了结果和未来的工作。

  1. 折线和多边形的多尺度空间访问方案

在这里，我们基于Zhou和Jones（2001a）给出了多尺度空间数据库的几何数据存储特性的概述，该数据库可以提供对多个细节级别的单个空间对象的访问。在这里，我们仅关注比例优先级属性几何的存储问题，而不关注其他问题，例如整个地图特征的选择或数据库对象的维护和更新。多尺度空间数据库的概念模型将地图要素表示为多尺度空间对象（MSO），具有特定于应用程序的类，涵盖分辨率范围RMSO，并引用一个或多个多尺度几何对象（MGEO）。MGEO的几何类型为tMGEO，分辨率范围为rMSO，对于简单折线和多边形（我们在此处考虑），则使用一组有序的顶点VMGEO。顶点由组件（MGEOID，vid，R，vsn，x，y）组成，其中MGEOID是父MGEO的标识符，vid是顶点的标识符，R是顶点的分辨率范围的集合，并且 x和y是2D空间中的几何坐标。该实现无需为每个顶点显式存储所有这些项目。

术语“分辨率”是指可用于确定顶点对指定查询比例的适用性的数值。在实践中，它等同于公差值，或者是公差值的函数，该公差值已被用来控制各个几何对象的泛化程度。在Douglas-Peucker（1973）算法的情况下，当其容差值除以地图比例分母时，可以视为对地图上最小可辨别特征的度量。

附加到顶点的分辨率值的重要性会根据用于生成该分辨率值的泛化算法的性质而有所不同。我们可以主要区分子设置和非子设置程序。在前者中，表示中的每个顶点都以最详细的表示形式出现，而在后者中，可以在概括过程中引入新的顶点。我们还可以区分连续和不连续的顶点。连续顶点是出现在单个几何分辨率范围内的顶点。不连续的顶点可能出现在单独的离散分辨率范围内。道格拉斯·皮克（Douglas Peucker）算法产生连续的子设置顶点，因为每个顶点代表从最详细到简化的某些中间或极端级别的分辨率范围。最初的分支修剪过程导致连续的子设置顶点，但是我们在本文中介绍的为避免树桩而对分支修剪进行的修改导致非子设置顶点，因为可以引入新的顶点（有时随后会被引入 删除），然后取消分支。

2.1实施方案

在第1.1节中提到的技术之后，有很多可能的方法来实现空间数据库以支持对MGEO的访问。Zhou和Jones（2001a）证明了分层方案的实用性，类似于Becker等人（1991）的方案，其中MGEO的顶点最初根据比例间隔分区进行分组，然后在相对于比例间隔分区的层次内进行分组 空间，使用R树来索引顶点的子序列。可以将一层内顶点的分辨率值映射到代表整个层的单个值，这在连续子设置顶点的情况下就足够了。替代地，例如在连续的非子顶点的情况下，可以存储代表顶点范围的一对值。

分层方案的替代方案是树方案，该树方案可以包括内部空间索引或以BLG树的方式简单地完成对象索引。

3.带有分支修剪的基于特征的线和面综合

3.1基于三角剖分的分支修剪概述

分支修剪技术基于根据形状标准消除线的明显特征的原理。一个特征对应于一条线中引入隆起或嵌入的一个或多个折弯，就具有多个详细级别的子特征的意义而言，它可以是分层的。在三角剖分方法中，要使用约束的Delaunay三角剖分（CDT）对要泛化的线和面集进行三角剖分。然后，使用相邻三角形序列的路径来近似直线和多边形骨架的分支位置（Ferley等，1997； Gold，2000）。“真实”骨架或中间轴转换表示与边界等距的点的轨迹。它的分支和子分支在其各自的细节层次上可能等同于线条和多边形的特征（Lee 1982）。

在CDT内，代表要素的三角形集可用于计算指标，这些指标可用于区分不同形状的要素。度量基于组成三角形的尺寸和构成相应特征的一组约束边。

3.2三角剖分组件

我们在这里定义了一些用于CDT分析的概念。属于原始线（并因此限制了三角剖分）的三角剖分的边被描述为真实，而属于外部边界框和所有其他边界的那些边则为虚拟。如果边是虚拟的，则两个具有共同边的三角形称为内部邻居，如果是实边，则称为外部邻居。内部邻居的三角形被称为已连接。

三角形分为三种基本类型。一个具有两个实际边的三角形称为叶三角形，而一个具有一个这样的边缘的三角形称为主干三角形，一个不具有边的三角形称为分支三角形。图1说明了这种分类。

一条空线的CDT中的一个分支是一组相连的三角形的连续集合，这些三角形由属于该线的一系列实际边沿以及一个单独的虚拟边（称为分支的基础边）所界定（请参见图2）。实际边的顺序定义为分支所代表的线的特征，理想情况下，它应与上述视觉特征重合。分支基础边缘的两个顶点是要素的第一个和最后一个顶点。

3.3分行统计

对上述三角剖分的分析揭示了特征的隐式层次。特征源自根节点的叶向边缘，从三角形到（连接的）三角形沿叶向连续，而子特征源自分支三角形的叶向边缘。现在，我们可以计算与每个分支和子分支有关的各种统计属性（“指标”），以便可以决定要删除哪些功能。通过将这些决策基于不同的度量标准，我们可以实现不同的概括风格。已经设计了十几种这样的统计数据。本文仅使用这些指标中的两个（路径长度，平均宽度）。这些以及它们派生所必需的那些将在下面描述。列出了真正的错误度量标准，因为该度量标准的可用性对于任何行泛化程序显然都是重要的。本文未讨论其他指标（例如边界长度）。

bull;分支的面积是其所有组成三角形的总面积。

bull;要定义分支的长度，我们定义节点的长度。对于躯干三角形，这是其两个内部边缘的中点之间的距离。对于叶三角形，就是从其（单个）内部边缘的中点到其相对的顶点。一个分支三角形具有两个节点长度，具体取决于正在测量的子分支。分支的长度是通过将形成分支的所有三角形的节点长度相加而获得的。复杂分支的长度被认为是其最长路径的长度–我们从其基线开始跟随该分支，并在每个交汇处取最长分支。

bull;分支高度是通过将分支的组成三角形的节点高度相加得出的。节点高度被定义为相关三角形高度的一半（以朝上的边为底）。

bull;平均宽度定义为分支的总面积除以其高度。

bull;分支的真实错误是如果要删除相关分支将在通用化中引入的位移错误。

3.4方法细节

最初，根据所选度量确定三角剖分的最小分支。删除定义此分支的线段，并用其基线替换，并更新三角剖分的受影响区域。重复该过程，直到最小剩余分支的相关度量值超过给定阈值为止。还可以为不同指标的组合指定阈值，并删除所有低于所有相关阈值的分支。

真实误差度量可以与其他度量组合以确保对位置精度的控制。

4.基于三角剖分的拓扑一致的顶点优先级标记（TCL）

在这里，我们描述了一种基于三角剖分的过程，用

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[257200]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章