CN111078919B - 一种基于九宫格的大规模矢量数据悬挂处理方法 - Google Patents

Abstract

本发明公开了一种基于九宫格的大规模矢量数据悬挂处理方法，包括以下步骤：a)读取矢量数据，获取空间信息；b)建立基于九宫格的首节点和末节点的数据模型；c)结合基于权重的快速搜索技术，进行悬挂节点快速查找；d)根据查询结果处理悬挂节点。本发明基于九宫格的大规模数据悬挂处理技术是针对大规模矢量数据，运用空间四叉树对矢量数据进行存储，并对每个节点进行九宫格切分，从而实现大规模矢量数据的快速查询，为道路边线等要素拓扑关系处理提供技术支撑。

Description

一种基于九宫格的大规模矢量数据悬挂处理方法

技术领域

本发明属于测绘技术领域，具体涉及一种基于九宫格的大规模矢量数据悬挂处理方法。

背景技术

随着新型基础测绘体系的建立，需要建设以资源数据库为中心的测绘产品体系，在功能上由突出图面地形表达转变为地理实体表达，这就使得道路等要素以面状要素表达。现有的处理方法为：

(1)读取要素

逐条读取交通线要素，获取各线要素的首节点和末节点。

(2)获取悬挂节点

对于首节点和末节点，将其分别与要素类中的所有其他交通线要素的首节点和末节点进行比对，判断是否有缝隙存在，即在阈值范围内，当存在与其他任意节点距离为零时，意味着该节点在与其他要素相接，反之则该节点就是悬挂点。

(3)处理交通线缝隙。

对于悬挂点，找到与其距离最近的节点，将该悬挂节点移至此节点即可。

上述传统的道路边线处理方法主要是基于要素的逐个比对，需要较大的内存空间，运算量大，处理时间长，难以满足大规模矢量数据处理的要求。由于传统基础测绘产品的道路均以边线表示，数据量大，亟需研究快速高效地处理道路边线等要素拓扑关系的处理方法。

发明内容

本发明提供了一种基于九宫格的大规模矢量数据悬挂处理方法，快速高效地处理道路边线等要素拓扑关系。

本发明的技术方案为：一种基于九宫格的大规模矢量数据悬挂处理方法，包括以下步骤：

a)读取矢量数据，获取空间信息；

b)建立基于九宫格的首节点和末节点的数据模型；

c)结合基于权重的快速搜索技术，进行悬挂节点快速查找；

d)根据查询结果处理悬挂节点。

作为优选，所述步骤a)中，包括以下步骤：

a1)通过属性查询，利用要素的分类代码获取需要处理的矢量数据；

a2)逐个读取矢量数据，获取首节点和末节点的空间位置，并连同要素ID存储在节点集合中；

a3)根据节点的空间坐标获取集合中所有节点的外包矩形。

作为优选，所述步骤b)中，包括以下步骤：

b1)根据集合的外包矩形初始化空间四叉树；

b2)将集合中的所有节点加入到空间四叉树。

作为优选，所述步骤b1)中，对于初始的空间四叉树，根据悬挂阈值将其空间分为九个宫格，每个宫格用于存储与之相对应的节点。

作为优选，将每个叶节点的空间分为九宫格，九宫格的第一排从左往右分别命名为宫格1、宫格2以及宫格3，九宫格的第二排从左往右分别命名为宫格4、宫格5以及宫格6，九宫格的第三排从左往右分别命名为宫格7、宫格8以及宫格9。

作为优选，所述步骤c)中，包括以下步骤：

c1)非悬挂节点标示：

每个叶节点都为其添加莫顿码和父节点信息，对于空间四叉树的每个叶节点的每个宫格，如果有节点与同一宫格内的其他节点重合，将这两个节点进行非悬挂节点标识；

c2)相邻宫格查询：

对于每个宫格，利用叶节点的莫顿码，先查询本宫格所在节点的兄弟节点，再查询本宫格所在节点的父节点，采用基于权重的快速搜索技术，实现相邻宫格快速查询；

对于宫格1、宫格3、宫格7、宫格9，通过宫格的角点获取相邻宫格；如果目标节点的基准点与其他节点的左下角点重合，则获取目标节点的宫格7；如果目标节点的基准点与其他节点的左上角点重合，则获取目标节点的宫格1；如果目标节点的基准点在其他节点的左边线上，则获取目标节点的宫格4；如果目标节点的基准点与其他节点的右上角重合，则获取目标节点的宫格3；如果目标节点的基准点与其他节点的右下角重合，则获取目标节点的宫格9；如果目标节点的基准点在其他节点的右边线上，则获取目标节点的宫格6；如果目标节点的基准点在其他节点的上边线上，则获取目标节点的宫格2；如果目标节点的基准点在其他节点的下边线上，则获取目标节点的宫格8；

对于宫格5，其相邻的宫格即为同一节点内的其他宫格；

对于宫格2、宫格4、宫格6、宫格8，通过宫格的外边线中点获取相邻宫格；如果目标节点的基准点在其他节点的上边线上，则获取目标节点的宫格1、宫格2、宫格3；如果目标节点的基准点在其他节点的下边线上，则获取目标节点的宫格7、宫格8、宫格9；如果目标节点的基准点在其他节点的左边线上，则获取目标节点的宫格1、宫格4、宫格7；如果目标节点的基准点在其他节点的右边线上，则获取目标节点的宫格3、宫格6、宫格9；

c3)获取悬挂节点：

将本宫格中的节点与相邻宫格的节点进行比对，若其空间距离小于悬挂阈值，则此两节点为悬挂节点。

作为优选，为每个叶节点赋长度值，若其莫顿码长度为N，则叶节点长度为1/(2N)；设当前叶节点的长度为lc，权重为Wc；目标节点的长度为lt，权重为Wt；

对于叶节点中的宫格1、宫格3、宫格7、宫格9，对于任意目标节点，如果lt>lc，则其权重为2；如果lt≤lc，则其权重为1；若搜索目标的权重之和为3，则搜索完成；

对于叶节点中的宫格2、宫格4、宫格6、宫格8，对于当前叶节点和任意目标节点，其权重与其长度相同；若∑Wt≥Wc，则完成搜索。

作为优选，所述步骤d)中，包括以下具体步骤：

d1)根据节点中的要素ID在矢量数据库中查询到相关的要素；

d2)根据节点位置修改要素的首节点或末节点，从而消除悬挂节点。

与现有技术相比，本发明的有益效果体现在：

(1)本发明在悬挂节点处理的过程中，只应用要素的首节点和末节点的空间位置和要素ID，占内存空间小。

(2)本发明在建立空间四叉树以后，通过相邻宫格搜索，悬挂节点查询运算量小，可以实现对大规模悬挂节点快速处理。

(3)本发明基于九宫格的大规模数据悬挂处理技术是针对大规模矢量数据，运用空间四叉树对矢量数据进行存储，并对每个节点进行九宫格切分，从而实现大规模矢量数据的快速查询，为道路边线等要素拓扑关系处理提供技术支撑。

附图说明

图1为本发明中九宫格的叶节点模型。

图2为本发明中节点都加入到空间四叉树的示意图。

具体实施方式

实施例1

本实施例为基于九宫格的大规模矢量数据悬挂处理方法，包括以下步骤：

a)首先读取矢量数据，获取空间信息；

b)然后建立基于九宫格的首末节点数据模型；

c)结合基于权重的快速搜索技术，实现悬挂节点快速查找；

d)最后根据查询结果处理悬挂节点。

以上步骤a)包括以下具体步骤：

a1)通过属性查询，利用要素的分类代码获取需要处理的矢量数据；

a2)逐个读取矢量数据，获取首节点和末节点的空间位置，并连同要素ID存储在节点集合中。

a3)根据节点的空间坐标获取集合中所有节点的外包矩形。

以上步骤b)包括以下具体步骤：

b1)根据集合的外包矩形初始化空间四叉树；

对于初始的空间四叉树，根据悬挂阈值将其空间分为九个宫格，每个宫格用于存储与之相对应的节点，如图1所示，其中r为悬挂阈值。

b2)将集合中的所有节点加入到空间四叉树。

先通过节点的空间位置获取其所在象限的索引，将其加入到对应的叶节点上；然后在加入到叶节点之后，还需要根据空间位置获取其所在叶节点的宫格索引，将其加入到对应宫格之中。

若某一叶节点上的节点数量达到上限，可将此叶节点所在的空间再分割成四个区域，形成新一级别的子叶节点，并将此象限中的节点放入到对应的子叶节点中。如此反复，直到把所有的节点都加入到空间四叉树中，见图2。

每个叶节点都为其添加莫顿码(即图中每个格网中间的数字)和父节点信息，可用于悬挂节点的快速搜索。

以上步骤c)包括以下具体步骤：

c1)非悬挂节点标示；

对于空间四叉树的每个叶节点的每个宫格，如果有节点与同一宫格内的其他节点重合，将这个两个节点进行非悬挂节点标识，用以提高数据处理效率。

c2)相邻宫格查询

对于每个宫格，利用节点的莫顿码，先查询本宫格所在节点的兄弟节点，再查询本宫格所在节点的父节点，采用基于权重的快速搜索技术，实现相邻宫格快速查询。

对于宫格1、宫格3、宫格7、宫格9，通过宫格的角点获取相邻宫格。如果目标节点的基准点与其他节点的左下角点重合，则获取目标节点的宫格7；如果目标节点的基准点与其他节点的左上角点重合，则获取目标节点的宫格1；如果目标节点的基准点在其他节点的左边线上，则获取目标节点的宫格4；如果目标节点的基准点与其他节点的右上角重合，则获取目标节点的宫格3；如果目标节点的基准点与其他节点的右下角重合，则获取目标节点的宫格9；如果目标节点的基准点在其他节点的右边线上，则获取目标节点的宫格6；如果目标节点的基准点在其他节点的上边线上，则获取目标节点的宫格2；如果目标节点的基准点在其他节点的下边线上，则获取目标节点的宫格8。

对于宫格5，其相邻的宫格即为同一节点内的其他宫格。对于宫格2、宫格4、宫格6、宫格8，通过宫格的外边线中点获取相邻宫格。如果目标节点的基准点在其他节点的上边线上，则获取目标节点的宫格1、宫格2、宫格3；如果目标节点的基准点在其他节点的下边线上，则获取目标节点的宫格7、宫格8、宫格9；如果目标节点的基准点在其他节点的左边线上，则获取目标节点的宫格1、宫格4、宫格7；如果目标节点的基准点在其他节点的右边线上，则获取目标节点的宫格3、宫格6、宫格9。

c3)获取悬挂节点

将本宫格中的节点与相邻宫格的节点进行比对，若其空间距离小于悬挂阈值，则此两节点为悬挂节点。

以上步骤d)包括以下具体步骤：

d1)根据节点中的要素ID在矢量数据库中查询到相关的要素。

d2)根据节点位置修改要素的首节点或末节点，从而消除悬挂节点。

本实施例中建立基于九宫格的叶节点模型：

将每个叶节点的空间分为九个宫格，且左上、左下、右下、右上四个宫格的边长均为悬挂阈值。

基于权重的快速搜索技术：

为每个叶节点赋长度值，若其莫顿码长度为N，则节点长度为1/(2N)。设当前节点的长度为lc,权重为Wc,目标节点的长度为lt，权重为Wt,

对于叶节点中的宫格1、宫格3、宫格7、宫格9，对于任意目标节点，如果lt>lc，则其权重为2；如果lt≤lc，则其权重为1；若搜索目标的权重之和为3，则搜索完成。

对于叶节点中的宫格2、宫格4、宫格6、宫格8，对于当前节点和任意目标节点，其权重与其长度相同；若∑Wt(搜索目标的权重之和)≥Wc，则完成搜索。

Claims (6)

1.一种基于九宫格的大规模矢量数据悬挂处理方法，其特征在于，包括以下步骤：

a)读取矢量数据，获取空间信息；

b)建立基于九宫格的首节点和末节点的数据模型；

c)结合基于权重的快速搜索技术，进行悬挂节点快速查找；

d)根据查询结果处理悬挂节点；

所述步骤b)中，包括以下步骤：

b1)根据集合的外包矩形初始化空间四叉树；

b2)将集合中的所有节点加入到空间四叉树；

所述步骤b1)中，对于初始的空间四叉树，根据悬挂阈值将其空间分为九个宫格，每个宫格用于存储与之相对应的节点；

通过节点的空间位置获取其所在象限的索引，将其加入到对应的叶节点上；并根据空间位置获取其所在叶节点的宫格索引，将其加入到对应宫格之中；

若某一叶节点上的节点数量达到上限，可将此叶节点所在的空间再分割成四个区域，形成新一级别的子叶节点，并将此象限中的节点放入到对应的子叶节点中；

为每个叶节点添加莫顿码和父节点信息，用于悬挂节点的快速搜索。

2.如权利要求1所述的基于九宫格的大规模矢量数据悬挂处理方法，其特征在于，所述步骤a)中，包括以下步骤：

a1)通过属性查询，利用要素的分类代码获取需要处理的矢量数据；

a2)逐个读取矢量数据，获取首节点和末节点的空间位置，并连同要素ID存储在节点集合中；

a3)根据节点的空间坐标获取集合中所有节点的外包矩形。

3.如权利要求1或2所述的基于九宫格的大规模矢量数据悬挂处理方法，其特征在于，将每个叶节点的空间分为九宫格，九宫格的第一排从左往右分别命名为宫格1、宫格2以及宫格3，九宫格的第二排从左往右分别命名为宫格4、宫格5以及宫格6，九宫格的第三排从左往右分别命名为宫格7、宫格8以及宫格9。

4.如权利要求3所述的基于九宫格的大规模矢量数据悬挂处理方法，其特征在于，所述步骤c)中，包括以下步骤：

c1)非悬挂节点标识：

每个叶节点都为其添加莫顿码和父节点信息，对于空间四叉树的每个叶节点的每个宫格，如果有节点与同一宫格内的其他节点重合，将这两个节点进行非悬挂节点标识；

c2)相邻宫格查询：

对于每个宫格，利用叶节点的莫顿码，先查询本宫格所在节点的兄弟节点，再查询本宫格所在节点的父节点，采用基于权重的快速搜索技术，实现相邻宫格快速查询；

对于宫格1、宫格3、宫格7、宫格9，通过宫格的角点获取相邻宫格；如果目标节点的基准点与其他节点的左下角点重合，则获取目标节点的宫格7；如果目标节点的基准点与其他节点的左上角点重合，则获取目标节点的宫格1；如果目标节点的基准点在其他节点的左边线上，则获取目标节点的宫格4；如果目标节点的基准点与其他节点的右上角重合，则获取目标节点的宫格3；如果目标节点的基准点与其他节点的右下角重合，则获取目标节点的宫格9；如果目标节点的基准点在其他节点的右边线上，则获取目标节点的宫格6；如果目标节点的基准点在其他节点的上边线上，则获取目标节点的宫格2；如果目标节点的基准点在其他节点的下边线上，则获取目标节点的宫格8；

对于宫格5，其相邻的宫格即为同一节点内的其他宫格；

对于宫格2、宫格4、宫格6、宫格8，通过宫格的外边线中点获取相邻宫格；如果目标节点的基准点在其他节点的上边线上，则获取目标节点的宫格1、宫格2、宫格3；如果目标节点的基准点在其他节点的下边线上，则获取目标节点的宫格7、宫格8、宫格9；如果目标节点的基准点在其他节点的左边线上，则获取目标节点的宫格1、宫格4、宫格7；如果目标节点的基准点在其他节点的右边线上，则获取目标节点的宫格3、宫格6、宫格9；

c3)获取悬挂节点：

将目标宫格中的节点与相邻宫格的节点进行比对，若其空间距离小于悬挂阈值，则此两节点为悬挂节点。

5.如权利要求4所述的基于九宫格的大规模矢量数据悬挂处理方法，其特征在于，为每个叶节点赋长度值，若其莫顿码长度为N，则叶节点长度为1/(2N)；设当前叶节点的长度为lc，权重为Wc；目标节点的长度为lt，权重为Wt；

对于叶节点中的宫格1、宫格3、宫格7、宫格9，对于任意目标节点，如果lt>lc，则其权重为2；如果lt≤lc，则其权重为1；若搜索目标的权重之和为3，则搜索完成；

对于叶节点中的宫格2、宫格4、宫格6、宫格8，对于当前叶节点和任意目标节点，其权重与其长度相同；若∑Wt≥Wc，则完成搜索。

6.如权利要求5所述的基于九宫格的大规模矢量数据悬挂处理方法，其特征在于，所述步骤d)中，包括以下具体步骤：

d1)根据节点中的要素ID在矢量数据库中查询到相关的要素；

d2)根据节点位置修改要素的首节点或末节点，从而消除悬挂节点。