CN110059210A - 一种带拓扑的矢量地图瓦片组织方法 - Google Patents

Abstract

本发明涉及一种带拓扑的矢量地图瓦片组织方法，包括以下步骤：对全球海图的图层进行地理分割，将分割后的图层归类成为分片图层，进行瓦片边界的存储；建立翼边拓扑组件，使用翼边遍历算法构建图层的边和面，创建基于翼边的跨片拓扑。本发明设计合理，其以全息化通用要素为基本单元进行数据的分片组织，并利用翼边拓扑模型实现边界拓扑信息的完整性，从而对全球海图进行矢量瓦片的有效组织，提高了跨图幅区域调度时的效率，其空间分析结果准确可靠，可广泛应用与全球海图处理领域。

Description

一种带拓扑的矢量地图瓦片组织方法

技术领域

本发明属于矢量地图处理技术领域，尤其是一种带拓扑的矢量地图瓦片组织方法。

背景技术

矢量地图数据组织的核心问题在于全球范围的地图数据组织策略。传统地图数据组织是以图幅为单元，其全球范围内的数据调度只能以图幅为单位，其存在的问题是：当以统一数据服务接口提供地图数据服务时，会导致数据调度索引效率低下，尤其在跨图幅区域调度时效率影响更明显，同时还存在要素压盖；另外，还存在各幅地图之间的拓扑连接问题，因为以图幅为单位的组织模式，每个图幅边界的要素的拓扑信息都是不完整的，这将导致大范围跨图幅的空间分析结果不准确。

发明内容

本发明的目的在于克服现有技术的不足，提出一种设计合理、效率高且分析结果准确的带拓扑的矢量地图瓦片组织方法。

本发明解决其技术问题是采取以下技术方案实现的：

一种带拓扑的矢量地图瓦片组织方法，包括以下步骤：

步骤1、对全球海图的图层进行地理分割，将分割后的图层归类成为分片图层，进行瓦片边界的存储；

步骤2、建立翼边拓扑组件，使用翼边遍历算法构建图层的边和面，创建基于翼边的跨片拓扑。

所述分片图层根据分片模式在物理上进行分片，分片模式的每片具有唯一的瓦片ID；分片图层包含了与非分片图层相同的属性信息；每片图层均成为图层目录下的一个单独子目录，且包含那些要素各自的基元表；分片图层均包含每一要素类的单个要素表；瓦片ID和基元ID的结合使该表中的要素和他们相一致的基元连接起来。

所述基元表包括边、面和连接型节点：

所述边的属性为：当边被瓦片边界打断时，一个连接型节点就会被置于边线-瓦片的交汇处；相同的连接型节点在形成边界的两瓦片中重现；所有沿瓦片边界分布的边都将有穿越瓦片的拓扑；相同的边在形成边界的两瓦片中重现；

所述面的属性为：被瓦片边界分割的面有一个重建的边，并在每个瓦片的边界为了封闭面而插入新边界；

所述连接型节点的属性为：所有位于瓦片边界的连接型节点都有穿越瓦片的组件。

所述瓦片ID采用三元组ID，该三元组ID包括如下属性：对于基线，三元组ID用于维护跨瓦片的拓扑：跨瓦片的拓扑只在库内的各瓦片之间发生。

所述步骤2建立翼边拓扑组件的方法为：在边基元表中使用三个规定的组件以提供结点、边和面之间的连续性；给定三个拓扑等级，边基元中将包含对应于每一拓扑层次的专门列；每条边包含结点信息、边信息和面信息。

所述结点信息定义为：每条边都将包含一个起始结点和一个终止结点列，其拓扑信息应用于定义边的方向；所述边信息定义为：右边和左边将边和它的邻边连接起来作为翼边，右边是环绕结点以逆时针方向起算，连接末尾结点的第一条边；左边是环绕结点以逆时针方向起算连接起始结点的第一条边；所述面信息定义为：每条边都将包含一个左面和右面，左面和右面仅依靠边的方向来区分，该信息允许通过边来得知它的邻面，面的外环和内环的组成是由翼边拓扑规则决定的，面内的浮动边将当作内环来对待。

所述使用翼边遍历算法构建图层的边和面的方法为：

①确定绘制哪个面，然后用面和环表的码来联系区域面；

②识别起始边：

③遍历左边以追踪左面；遍历右边以追踪右面；

④根据起始边，从而完成图层的边和面的构建。

所述确定绘制哪个面是由具有属性需要的区域面要素选取来给定的。

所述创建基于翼边的跨片拓扑应遵循以下规则：

①当边与瓦片边界相交被裁切时，在每块瓦片的相交处都设置连接节点，如果有一条边存在于邻接瓦片，所有由该连接结点终结的边都将含有跨瓦片拓扑；

②跨瓦片边将是从该结点相关边逆时针方式邻接联结瓦片上的第一条边；

③所有边与瓦片边界一致的边将同时出现在两个瓦片中，而且含有跨瓦片左面、右面拓扑，以及跨瓦片左边、右边拓扑；

④当瓦片边界将面分裂开，沿着瓦片边界封闭面来创建多个；

⑤出现在瓦片边界的相连结点，如果边存在，将同时存在于两个瓦片并且参考外部及内部第一条边，该第一条边是同时在内部和外部瓦片中任意选择的。

本发明的优点和积极效果是：

本发明设计合理，其以全息化通用要素为基本单元进行数据的分片组织，并利用翼边拓扑模型实现边界拓扑信息的完整性，从而对全球海图进行矢量瓦片的有效组织，提高了跨图幅区域调度时的效率，其空间分析结果准确可靠，可广泛应用与全球海图处理领域。

附图说明

图1是瓦片边界的存储示意图；

图2是分片模式的结构示意图；

图3是跨瓦片的匹配原理图；

图4是翼边组件的结构图；

图5a是一个内环示例(面5表示为环表中的一个单独环)；

图5b是一个内环示例(两个内面及连接边构成的独立环)；

图6是一个外环示例；

图7是一个面和伴随边的集合；

图8是跨瓦片边规则示意图；

图9是瓦片边界基元行为示意图；

图10是跨瓦片边的实例。

具体实施方式

以下结合附图对本发明实施例做进一步详述。

一种带拓扑的矢量地图瓦片组织方法的设计思路如下：

由于全球范围的地图矢量数据无可避免地包括大量数据，在处理这些地图数据的过程中，矢量数据集常常需要在内存中管理，这对矢量数据的大小有明确的限制。为了突破这种限制，本发明将采用矢量瓦片技术实现全球海图数据的分片组织。

为了准确描述地图矢量数据的分片组织策略，首先给出以下定义：

几何基元：地图矢量数据中有三种几何基元：点、线和面；其中，点有两种类型：实体型节点和连接型节点。

制图基元：三种几何基元和制图基元结合起来，通过使用矢量几何可以模拟任一地理现象，除文本外所有的基元均可以通过拓扑关系相互连接。

拓扑基元：为保持瓦片之间的湖岸线基元的关系，需要一个跨瓦片边界的基元来使两者依赖于瓦片边界本身(为了保持瓦片的拓扑关系)和它用来简化基元特征的恢复的跨瓦片扩展。本专利通过在当前瓦片里包含边界或边缘的内部参考的三元组ID的边界来达到这种需求，而当合适的时候，三元组ID也可以包含邻接瓦片边缘的外部参考。

瓦片技术是针对硬件和存储限制的底层实现方式，同时应该对像全息化通用要素这样的概念结构没有影响。因为瓦片技术导致的基元被分割到独立的表格中时，他们对应的属性也破坏了，所以本专利通过保证属性表以及要素类表不被破坏以及合理组织来解决上述问题。它们不是一次全部而是顺序被处理，因此可以避免因为满足硬件限制而破坏要素本身。这些表存储在一个图层中，实际表示瓦片的矢量数据集分割部分出现在图层的下级目录中。关注问题是把存储在众多的小矢量数据集中的基元与存储在一个独立的大矢量数据集中属性连接起来。这是通过相关设计原则标准实现的，即为每一个要素增加一列关于基于矢量数据集的列，包括存有那个基元的属性的母表中的行id。如果五个要素类都来源于基元拓扑图层，基元表中需要增加五个附加的列。为每个要素类增加一列会导致表很大，因为要素的种类有将近500个。不是所有的要素类都会应用于三个基元维度或所有产品，或所有图层，但是对于垂直或专题整合数据来说数目也是很容易接近100的。回溯到要素的指针仅仅是因为性能的需求。

本发明在基元层面上处理分片和数据分割问题，通过三元组ID保持跨片拓扑以及在基元上附加的要素类列来保证更多逻辑一致性的独立属性表之间的连接。同时需要保证瓦片本身以及存储关于瓦片的参考数据、尺寸、模式等等，这些是在瓦片参考图层中完成的。

“瓦片参考图层”仅用来表达瓦片的多边形图层。除了瓦片边界和瓦片标签之外，不涉及到其他数据。在库层次上作为一个单独的图层进行存储，同时作为瓦片模式的图形索引，描述所有的瓦片和那些只在库中的瓦片、瓦片的名称以及他们之间的关系。这个图层的面要素表有着重要的作用。因为它存储了每个瓦片的属性，可以用于控制每个要素类的数据密度、瓦片数据容量以及概要内容，和在瓦片层次上管理矢量数据的其他元数据。

本发明的具体实现方法包括以下步骤：

步骤1、对全球海图的图层进行地理分割，将分割后的图层归类成为分片图层，进行瓦片边界的存储。

分片是为了加强数据的管理而将图层进行地理分割；图层以这样的方式被分割后归类成为分片图层。分片图层包含了与非分片图层相同的属性信息。分片图层的逻辑解释也和非分片图层相同。每一片都将成为图层目录下的一个单独子目录，且在片中包含那些要素各自的基元表。分片图层将包含每一要素类的单个要素表。通过瓦片ID和基元ID的结合使该表中的要素和他们相一致的基元连接起来。对于图层中缺乏数据的瓦片，则在图层目录中没有子目录，分片图层根据分片模式在物理上进行分片，分片模式的每片有一个唯一的瓦片标识，如图1所示。

基元定义作为一个整体在瓦片中出现。以下段落阐述了瓦片的影响：

(1)边：当边被瓦片边界打断时，一个连接型节点就会被置于边线-瓦片的交汇处。相同的(地理坐标)连接型节点在形成边界的两瓦片中重现。所有沿瓦片边界分布的边都将有穿越瓦片的拓扑。相同的(地理坐标)边在形成边界的两瓦片中重现。

(2)面：被瓦片边界分割的面有一个重建的边，并在每个瓦片的边界为了封闭面而插入新边界。这些便会在多个瓦片的拓扑关系中有所体现。

(3)面1(全域面)：如图1所示，面1(全域面)描述了分片边界的一个特殊情况。在那些面1是唯一被分割的面的情况下，实际的瓦片边界将不会被存储。例如，在面2被瓦片边界分割且剩余的瓦片均被面1标识的情况下，只有瓦片边界上对于封闭面2是必须的边线才会被存储。瓦片的边文件将只存储边1、2、3和4。全域面的虚线边线是隐含的，但没有存储。

(4)连接型节点：所有位于瓦片边界的连接型节点都有穿越瓦片的组件。

另外两种需要考虑的情况就是只包含点要素或者不包含要素的3级拓扑级图层的瓦片。在这些情况下，瓦片可能包含实体型基点和面1，或者仅包含面1。3级拓扑需要包含面、环、边线、连接型节点、面外接矩形表以及一个边可变长索引。面、环、面外接矩形表仅仅参照全域面(面1)。由于环表参照边表，那么边表必须存在。由于边表参照连接节点表，那么连接节点表也必须存在。边表的存在需要一个边可变长索引，面表的存在需要一个面外接矩形表。边表、连接节点表和边可变长索引不包含任何记录。

如图2所示，由于分片图层中每一片的基元都是与在其它瓦片中那些基元分开管理的，因而给出基元的标记仅在该瓦片是唯一的。为了支持逻辑连续的空间数据库，可以利用三元组ID代替整数码来参照瓦片边界多种瓦片的基元。

(1)对于基线，三元组ID用于维护跨瓦片的拓扑。左面、右面、左边和右边列都被定义为三元组ID以支持分片图层。三元组ID包含了当前瓦片中内部拓扑的参照；另外两个部分则参照外部瓦片目录和瓦片中的基元。例如，对于被瓦片边界分割的面，图3中左面区域的外部ID部分将包括包含其它瓦片中的连续面。包含了内外部瓦片的参考使得软件可以检测瓦片的边界并操作跨瓦片边界或者只在当前瓦片中操作。如果图层未被分片，左面、右面、左边和右边这些列可能被定义为整数列；否则三元组ID子区域中的外部瓦片ID和基元ID都将不存在。

(2)跨瓦片的拓扑只在库内的各瓦片之间发生。跨瓦片的组件将仅被增加用于库内边线跨越的瓦片。与库边界一致的瓦片边界上的边不会使得跨瓦片的组件有所增加。

步骤2、建立翼边拓扑组件，使用翼边遍历算法构建图层的边和面，创建基于翼边的跨片拓扑。具体实现方法如下：

翼边拓扑模型是数据模型的一个重要组成部分，它的功能是提供线状网络、面拓扑以及保持跨瓦片图层的拓扑无缝性。以下部分将详细定义翼边拓扑的组件，翼边网络遍历的算法，以及跨瓦片拓扑。

(1)建立翼边组件

翼边拓扑在边基元表中使用三个规定的组件以提供结点、边和面之间的连续性。给定1，2，3三个拓扑等级，边基元中将包含对应于每一拓扑层次的专门列。如图4所示，有三个拓扑构造：每条边包含结点、边和面的信息。以下将对该定义进行详细阐述。

①结点信息。每条边都将包含一个起始结点和一个终止结点列。该拓扑信息应用于定义边的方向(数字化方向)。

②边信息。右边和左边将边和它的邻边连接起来(因此称为“翼边”)。右边是环绕结点以逆时针方向起算，连接末尾结点的第一条边。左边是环绕结点以逆时针方向起算连接起始结点的第一条边。

③面信息。由于三级拓扑的划分，每条边都将包含一个左面和右面。左面和右面仅依靠边的方向来区分。该信息允许通过边来得知它的邻面。

④内环及外环。一个面的外环和内环的组成是由翼边拓扑规则决定的。不仅如此，由于在面内部不考虑边而只考虑面的边界，面内的浮动边将当作内环来对待。图5a、图5b给出了内环的示例(图5a中面5表示为环表中的一个单独环，图5b中的两个内面及连接边构成的独立环)图6给出了一个外环示例(浮动边)。

(2)使用翼边遍历算法构建图层的边和面

给定翼边的定义，每个图层包含的面和边都是以相同方式创建的。随着平面拓扑模型的加强，相应的浏览算法就可以应用了。图7给出了一个面和伴随边的集合。为了构建一个面，需要使用以下算法：

①决定哪个面应该绘制。确定哪个面应该绘制将由具有属性需要的区域面要素选取来给定；然后用面和环表的码来联系区域面。下表给出了与图7一致的面要素表实例。

使用面3作为436面要素的基元来标识瓦片95，如下所示

关于瓦片95对应于图7的面表如下所示：

图7的环表如下所示：

表3.3环表实例

②识别起始边：(在该示例中，为边12)

③遍历左边以追踪左面；遍历右边以追踪右面。因为面3是边12的左面，读取左边记录(边11)。边11连接边10，边10连接边9，边9连接边8，边8连接边7，边7连接边6，边6连接边5，边5连接边12。

④边12是起始边，因此环得以完成。

假定一个线状要素表存在于示例中，而且每个线状要素都含有用于区分网络中正确边选择的属性列。线状要素的值将会决定遍历的规则以及遍历终止的时机。遍历中的起始点和终止点依赖于用户的使用。一个网络可以有各种各样的遍历策略。以下的例子将描述一个深度优先的搜索，算法如下：

①根据用户使用确定当前边：(边12)。

②读入当前边的终止结点然后搜集所有在该结点中出现的边。

③对于结点中出现的每条边，读入相关线状要素的属性值。判断属性是否含有需要的值，是的话，继续进行步骤5。

④转到步骤3，重复以上过程。

⑤判断，网络是否被完全遍历，是的话，退出整个网络，否则转到步骤2。

(3)创建基于翼边的跨片拓扑

使用翼边的网络浏览可以拓展到跨物理组成的瓦片。如果它们存在图层中，通过使用先前实例的信息，可以引入跨瓦片结构。假定图7已经和瓦片边界进行相交运算，而且新的图层在图10中创建(沿着图7中的边5的广义边)。

图10描述了一个单独的面通过与四个瓦片的相交，裁切成四个面。以下将讨论区分不同瓦片边界例子，包括通过翼边拓扑从基元面(未分片)到瓦片面的检索。

创建跨瓦片拓扑时，应遵循以下规则：

①当边与瓦片边界相交被裁切时，在每块瓦片的相交处都设置连接节点。如图9的B和C。如果有一条边存在于邻接瓦片，所有由该连接结点终结的边都将含有跨瓦片拓扑。如图8的A和B。

②跨瓦片边将是从该结点相关边逆时针方式邻接联结瓦片上的第一条边。如图8的A和B。

③所有边与瓦片边界一致的边(边的所有坐标都在边界线上)将同时出现在两个瓦片中(如图9的A，D，E和F)，而且含有跨瓦片左面、右面拓扑，以及跨瓦片左边、右边拓扑。如图8的A和B。

④当瓦片边界将面分裂开，沿着瓦片边界封闭面来创建多个，见图9的A。在边界上用于封闭面的边以c中所述的方法同样处理。如图8的B。

⑤出现在瓦片边界的相连结点，如果边存在，将同时存在于两个瓦片并且参考外部及内部第一条边。第一条边是同时在内部和外部瓦片中任意选择的。

图9和图10给出了瓦片边界原初始行为的实例：

三元组ID中实际上并不包含瓦片ID，详细步骤如下所示：

①从MJ21瓦片的边1开始，读入左边，选择跨入瓦片MJ11，边6；

②从边6，5，4，3，2和1得到的链包含在瓦片MJ11中；

③从MJ11中的边1，跨入到瓦片MJ12，边1；

④从MJ12的边1跨入到瓦片MJ22的边3；

⑤通过边3、2和1的链；

⑥从MJ22的边1，跨入到瓦片MJ21的边1；

⑦当遇到面环的终点，跳出。

需要强调的是，本发明所述的实施例是说明性的，而不是限定性的，因此本发明包括并不限于具体实施方式中所述的实施例，凡是由本领域技术人员根据本发明的技术方案得出的其他实施方式，同样属于本发明保护的范围。

Claims (9)

1.一种带拓扑的矢量地图瓦片组织方法，其特征在于包括以下步骤：

步骤1、对全球海图的图层进行地理分割，将分割后的图层归类成为分片图层，进行瓦片边界的存储；

步骤2、建立翼边拓扑组件，使用翼边遍历算法构建图层的边和面，创建基于翼边的跨片拓扑。

2.根据权利要求1所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述分片图层根据分片模式在物理上进行分片，分片模式的每片具有唯一的瓦片ID；分片图层包含了与非分片图层相同的属性信息；每片图层均成为图层目录下的一个单独子目录，且包含那些要素各自的基元表；分片图层均包含每一要素类的单个要素表；瓦片ID和基元ID的结合使该表中的要素和他们相一致的基元连接起来。

3.根据权利要求2所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述基元表包括边、面和连接型节点：

所述边的属性为：当边被瓦片边界打断时，一个连接型节点就会被置于边线-瓦片的交汇处；相同的连接型节点在形成边界的两瓦片中重现；所有沿瓦片边界分布的边都将有穿越瓦片的拓扑；相同的边在形成边界的两瓦片中重现；

所述面的属性为：被瓦片边界分割的面有一个重建的边，并在每个瓦片的边界为了封闭面而插入新边界；

所述连接型节点的属性为：所有位于瓦片边界的连接型节点都有穿越瓦片的组件。

4.根据权利要求2所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述瓦片ID采用三元组ID，该三元组ID包括如下属性：对于基线，三元组ID用于维护跨瓦片的拓扑：跨瓦片的拓扑只在库内的各瓦片之间发生。

5.根据权利要求1所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述步骤2建立翼边拓扑组件的方法为：在边基元表中使用三个规定的组件以提供结点、边和面之间的连续性；给定三个拓扑等级，边基元中将包含对应于每一拓扑层次的专门列；每条边包含结点信息、边信息和面信息。

6.根据权利要求5所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述结点信息定义为：每条边都将包含一个起始结点和一个终止结点列，其拓扑信息应用于定义边的方向；所述边信息定义为：右边和左边将边和它的邻边连接起来作为翼边，右边是环绕结点以逆时针方向起算，连接末尾结点的第一条边；左边是环绕结点以逆时针方向起算连接起始结点的第一条边；所述面信息定义为：每条边都将包含一个左面和右面，左面和右面仅依靠边的方向来区分，该信息允许通过边来得知它的邻面，面的外环和内环的组成是由翼边拓扑规则决定的，面内的浮动边将当作内环来对待。

7.根据权利要求1所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述使用翼边遍历算法构建图层的边和面的方法为：

①确定绘制哪个面，然后用面和环表的码来联系区域面；

②识别起始边：

③遍历左边以追踪左面；遍历右边以追踪右面；

④根据起始边，从而完成图层的边和面的构建。

8.根据权利要求7所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述确定绘制哪个面是由具有属性需要的区域面要素选取来给定的。

9.根据权利要求1所述的一种带拓扑的矢量地图瓦片组织方法，其特征在于：所述创建基于翼边的跨片拓扑应遵循以下规则：

①当边与瓦片边界相交被裁切时，在每块瓦片的相交处都设置连接节点，如果有一条边存在于邻接瓦片，所有由该连接结点终结的边都将含有跨瓦片拓扑；

②跨瓦片边将是从该结点相关边逆时针方式邻接联结瓦片上的第一条边；

③所有边与瓦片边界一致的边将同时出现在两个瓦片中，而且含有跨瓦片左面、右面拓扑，以及跨瓦片左边、右边拓扑；

④当瓦片边界将面分裂开，沿着瓦片边界封闭面来创建多个；

⑤出现在瓦片边界的相连结点，如果边存在，将同时存在于两个瓦片并且参考外部及内部第一条边，该第一条边是同时在内部和外部瓦片中任意选择的。