一种居民地约束下的道路网综合方法

1.本发明涉及一种居民地约束下的道路网综合方法，属于道路网制图技术领域。


背景技术：

2.道路是构成地图骨架的重要地理要素，是制图综合的重点研究对象。道路网综合的目标是在比例尺缩小的过程中保留重要道路，舍弃不符合目标比例尺的冗余道路，并保持道路网的整体形态和连通性。
3.目前道路网综合方法主要包括：基于语义等级的方法、基于图论的方法、基于stroke的方法、基于网眼密度的方法及其他混合方法。基于语义等级的方法主要依赖道路的语义信息，未对道路网建立有效模型，忽略了道路网的拓扑和几何信息。基于图论的道路重要性评价方法主要侧重于对路网间连接性和拓扑结构的分析，对于保持路网连通性具有重要作用，但对道路的语义和几何信息有所忽略。基于stroke的方法可以有效模拟人工选取过程中道路的视觉长度对道路重要性评价的影响，在道路综合选取过程中保持道路完整性的同时也可以较为全面地顾及道路目标间的延展性、拓扑一致性和上下文信息。基于网眼密度的方法能够较好地保持综合前后道路网的相对密度以及路网拓扑语义一致性。但上述方法大多未考虑道路网与其他地理要素间的关联，会影响地理要素间的协调性甚至出现违背现实规律的情况，道路最主要是为人民生活服务的，若是综合后道路不能保障各个居民地之间的连通性，则脱离现实规律，违背了人的实际需求，进而导致各个居民地之间连通性降低。


技术实现要素：

4.本发明的目的是提供一种居民地约束下的道路网综合方法，以解决现有道路网综合过程中未能充分考虑居民地与道路的地理关联性而导致的居民地之间连通性降低的问题。
5.本发明提出一种居民地约束下的道路网综合方法，该方法包括以下步骤：
6.1)获取目标区内的居民地数据和道路网数据；
7.2)对获取的居民地数据进行聚类得到不同聚落；并根据道路与聚落的拓扑关系对道路进行分类；
8.3)根据聚落所包含的道路类型对聚落进行神经元构建；
9.4)搜索任意两个邻近神经元之间的所有有效路径，找到其中的最优路径，该最优路径是指邻近神经元间所有有效路径中通行时间成本最低的路径，根据最优路径对两个邻近神经元的所有有效路径进行简化，得到邻近神经元间的简化后路径；
10.5)完成所有邻近神经元间的路径简化后，将邻近神经元间的所有有效路径视为整体进行处理，搜索三个相互邻近的聚落构成的三角结构，找到三角结构中每条边的最优路径，判断形成的三角结构中最优路径时间成本最大的边能否被另外两条边的组合替代，若时间成本最大的边对应的时间成本大于另外两条边的时间成本之和，则删除对应时间成本
最大的边所对应的所有有效路径。
11.本发明以居民地要素作为道路综合的约束，对居民地聚类得到不同居民地聚落，考虑道路与聚落之间的拓扑关系对道路进行分类，并组合聚落和与聚落拓扑相连的道路构建神经元，搜索邻近神经元间的有效路径，根据路径通行时间成本最小原则，依次对邻近神经元对和构成三角形结构的邻近神经元组的路径进行简化，使得聚落间的连通性和道路网的功能性能够得到较好地保持，相比于现有技术中主要依靠道路网的语义、几何与拓扑信息进行道路简化，本发明以居民地要素作为道路网综合的约束，充分考虑了道路与居民地之间的地理关联，使得简化后道路网更贴合实际通行需求。
12.进一步地，所述道路被分为e型道路、p型道路、i型道路和o型道路；其中e型道路是指该道路一端位于居民地聚落内部，一端位于居民地聚落外部，p型道路是指该道路贯穿居民地聚落，且道路两端均位于居民地聚落外部，i型道路是指该道路的各端点均位于居民地聚落内部，o型道路是指该道路完全位于居民地聚落外部；
13.所述神经元被分为i型神经元和ii型神经元；i型神经元是指该神经元包括e型道路及i型道路或者仅包含e型道路，ii型神经元是指该神经元仅包含p型道路。
14.通过上述方式根据道路与聚落间的拓扑关系对道路进行分类，方便后续神经元的构建及有效路径的搜索。
15.进一步地，所述邻近神经元间的有效路径是指从起点神经元的e型道路到终点神经元的e型道路所构成的所有路径，其中，当神经元为ii型神经元时，将ii型神经元内的p型道路作为该神经元的e型道路。
16.由于e型道路连接聚落内外，p型道路贯穿聚落，通过这两种道路即可确定连通两个邻近神经元间的通行路径，而i型道路作为神经元的内部路径。
17.进一步地，所述有效路径是指通行时间成本最低的路径，该通行时间成本的计算公式为：
[0018][0019]
式中，l为道路长度，v为不同等级公路的设计速度，st为道路弯曲度。
[0020]
由于一个神经元在聚落的不同方位可能会存在多条e型道路，所以邻近神经元间可能存在多条路径，计算所有e型道路组合之间的通行时间成本，选择符合要求的有效路径，进一步减少数据冗余，更方便后续路径的简化。
[0021]
进一步地，邻近神经元间有效路径简化依据为：
[0022]
α
×
(κf κs κe)＜κ
t
[0023]
式中，α为可容忍成本比；κf为最优路径的通行时间成本；κs为最优路径与当前路径在起点神经元中的内部通行时间成本；κe为最优路径与当前路径在终点神经元中的内部通行时间成本；κ
t
为当前路径的通行时间成本；如果当前路径的通行时间成本大于在可容忍成本比下最优路径通行时间成本与内部通行时间成本的总和，则移除该路径。
[0024]
进一步地，所述邻近神经元组中路径简化依据为：
[0025]
α
×
(κ
e1
κ
e2
)＜κ
em
[0026]
式中，α为可容忍成本比；κ
em
为邻近神经元中最大的通行时间成本；κ
e1
与κ
e2
是另外两个通行时间成本。
[0027]
通过上述方式实现邻近神经元和邻近神经元组之间的路径简化，两种简化方式核心都是选择通行时间成本最小的路径，以此实现冗余路径的剔除。
[0028]
进一步地，所述可容忍成本比是指能够接受最优路径在目标区域的服务能力弱于当前路径的服务能力的程度，代表道路网的简化力度，其取值范围为[0.6,1]，当道路网简化力度越强时，可容忍成本越小。
[0029]
在进行路径简化时，可以利用可容忍成本比调节道路网的简化力度，实现在通行时间成本相差不大的情况下的路径简化。
[0030]
进一步地，在对聚落进行神经元构建前，先根据聚落的重要性对聚落进行筛选，对筛选出的聚落进行神经元构建。
[0031]
通过聚落的重要性进行聚落筛选，以实现在不影响整体道路简化的情况下，淘汰少数弱小聚落，以增强约束效果。
[0032]
进一步地，所述聚落的重要性是根据聚落的面积、居民地密度、voronoi面积、道路指数确定的，其中voronoi面积是指聚落的空间影响范围，道路指数是指聚落的道路连通性。
[0033]
采用四种参数确定聚落重要性，其中，面积和居民地密度越大，可以认为该聚落越重要；voronoi面积表示空间影响范围，voronoi面积越大说明该聚落越具代表性；还考虑道路指数，以更好地保证后续简化后道路在聚落之间的连通性；通过这四种参数更能准确表征聚落的重要性。
[0034]
进一步地，所述聚落的重要性的计算公式为:
[0035]
sp(vi)＝μ
×
[w1×
s(vi) w2×
rd(vi) w3×
vs(vi)] w4×
ri(vi)
[0036]
式中，vi(i＝1,2，
…
,n)为第i个居民地聚落，n为生成的聚落总数，s为聚落面积，rd为居民地密度，vs为voronoi面积，ri为道路指数，w1、w2、w3和w4分别为s、rd、vs和ri的权重，且w1 w2 w3 w4＝1，μ为调节系数，当聚落属于i型神经元时，μ＝1；当聚落属于ii型神经元时，μ《1。
[0037]
通过上述公式确定不同聚落的重要性，并且通过设定不同类型神经元下的调节系数，以实现不同类型神经元下聚落重要性的适应调整。
附图说明
[0038]
图1是本发明居民地约束下的道路网综合方法具体实施流程图；
[0039]
图2(a)是道路类型中的e型道路示例图；
[0040]
图2(b)是道路类型中的p型道路示例图；
[0041]
图2(c)是道路类型中的i型道路示例图；
[0042]
图2(d)是道路类型中的o型道路示例图；
[0043]
图3(a)是典型i型神经元示例图；
[0044]
图3(b)是包含无法直接服务聚落的p型道路的i型神经元示例图；
[0045]
图3(c)是典型ii型神经元示例图；
[0046]
图3(d)是包含无法直接服务聚落的p型道路的ii型神经元示例图；
[0047]
图4是邻近神经元间路径简化示意图；
[0048]
图5是邻近神经元组间路径简化示意图。
具体实施方式
[0049]
下面结合附图对本发明的具体实施方式作进一步地说明。
[0050]
本发明提出一种居民地约束下的道路网综合方法，该方法具体过程如图1所示。首先对居民地数据进行聚类生成聚落，再依据道路与聚落的拓扑关系对道路进行分类；然后，根据聚落所包含的道路类型构建神经元；之后搜索邻近神经元之间的所有有效路径，并找到最优路径；最后根据路径通行时间成本最小原则，依次对邻近神经元间的路径与构成三角形结构的神经元组之间的路径进行简化。
[0051]
步骤1.获取数据
[0052]
本发明首先获取目标区内的居民地数据和道路网数据。这两种数据都可以从已经建好的地理数据库中获取，得到该区域内居民地和道路网的矢量数据。根据实际对道路网精度的需求，在已有数据库中选择适当比例尺的数据。例如，需要生成1:5000的路网数据，可以通过对1:2000的路网数据简化得到。本发明旨在通过获取的居民地数据为约束，根据道路与居民地之间的地理关联性，进行后续路径简化。
[0053]
步骤2.生成聚落和道路分类
[0054]
根据获取的居民地数据和道路网数据，首先对居民地数据进行聚类生成聚落，再根据道路与聚落之间的拓扑关系，对道路进行分类。
[0055]
首先，采用聚类算法对获取的居民地数据进行聚类以得到不同聚落，并提取聚落轮廓，在居民地聚类中，一般采用基于密度的聚类方法。本实施例中，采用dbscan(density-based spatial clustering of applications with noise)算法对居民地进行聚类，并采用滚球法(ball pivoting)提取聚落的轮廓。作为其他实施方式，居民地聚类也可采用cfsfdp算法、k-means算法。作为其他实施方式，聚落轮廓提取也可采用边缘检测方法。
[0056]
然后，按照道路与聚落之间的拓扑关系对道路进行分类，本发明将道路分为e型道路、p型道路、i型道路和o型道路。其中，e型道路如图2(a)所示，该类型道路是指该道路一端位于聚落内部，一端位于聚落外部，可以直接连通聚落内外；p型道路如图2(b)所示，该类型道路是指该道路贯穿聚落，且道路两端均位于聚落外部，同样该类型道路能够连通聚落内外，常见于沿道路分布的小型聚落，偶尔出现在规模较大的聚落；i型道路如图2(c)所示，该类型道路是指该道路的各端点均位于居民地聚落内部，其作用是连通聚落内部的不同区域和e型道路，聚落规模越大，i型道路数量越多、结构越复杂；o型道路如图2(d)所示，该类型道路与目标聚落相离，完全位于聚落外部，不参与后续神经元的构建。此外，道路的分类是面向聚落的，因此同一条道路在不同聚类中类型可能不同。
[0057]
步骤3.聚落筛选
[0058]
根据聚落的重要性进行聚落的筛选，因为本发明是在居民地约束下进行道路网综合，因此选取部分重要聚落作为约束条件，剔除一些弱小聚落，即重要程度低的聚落，以增强约束效果。聚落的重要性是根据聚落的面积、居民地密度、voronoi面积、道路指数确定的，具体计算公式如下：
[0059]
sp(vi)＝μ
×
[w1×
s(vi) w2×
rd(vi) w3×
vs(vi)] w4×
ri(vi)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)
[0060]
式中，vi(i＝1,2，
…
,n)为第i个居民地聚落，n为生成的聚落总数，s为聚落面积，rd为居民地密度，vs为voronoi面积，ri为道路指数，w1、w2、w3和w4分别为s、rd、vs和ri的权重，且w1 w2 w3 w4＝1，μ为调节系数，因为在面积、密度等参数相同时，位于道路交汇处的聚
落比沿道路分布的聚落有着更显著的地理意义，所以当聚落属于i型神经元时，μ＝1；当聚落属于ii型神经元时，μ《1。其中，不同参数的权重值可以根据实际应用需求进行调整。
[0061]
其中，聚落面积是聚落重要性最直观的体现，通常面积大的聚落比面积小的聚落更重要；居民地密度反映聚落内部居民地的疏密程度，在聚落面积相同时，居民地密度大的聚落面积更重要，居民地密度计算如公式(2)所示；voronoi面积是指聚落的空间影响范围，voronoi面积越大说明该聚落越具代表性，被选取的可能性也越大；道路指数是指聚落的道路连通性，聚落所涉及的道路数量越多、等级越高则聚落重要性越高，道路指数是根据聚落之间的道路的等级来确定的，聚落主要依靠e型道路和p型道路连通内外，为此主要根据e型道路和p型道路的数量、等级计算道路指数，其计算公式如公式(3)所示：
[0062][0063]
式中，m为聚落vi中居民地的数量，s(pj)为聚落vi中的居民地pj的面积，s(vj)为聚落vi的面积。
[0064][0065]
式中，k为聚落vi的有效连通道路的总数，rank(rj)为道路rj的数值化等级，道路的数值化等级是指根据道路的等级划分的道路权重值，具体如表1所示：
[0066]
表1：
[0067][0068]
根据公式(1)-(3)确定各个聚落的重要性，根据设定的比例阈值淘汰部分聚落，该比例阈值可以根据得到的聚落的实际情况设定。后续所有过程均以被保留的聚落为基础。作为其他实施方式，聚落重要性也可根据实际需求确定，例如不考虑道路因素，仅采用聚落的面积、居民地密度、voronoi面积进行确定，或者还可以考虑其他因素对聚落的影响，例如人口密度、地形等。作为其他实施方式，若居民地数据为目标比例尺，可以不进行聚落筛选。
[0069]
步骤4.神经元构建
[0070]
根据聚落所包含的道路类型构建神经元，即将聚落和与该聚落拓扑相连的道路相结合。根据神经元中的道路类型将神经元分为两类，i型神经元和ii型神经元。其中，i型神经元是指该神经元包括e型道路及i型道路或者仅包含e型道路，如图3(a)所示；同时本发明遵循“与聚落核心的连通才是真正的连通”的原则，即目标道路只有在聚落内部与其他道路相交或目标道路的影响范围覆盖了聚落的核心区域才可以直接服务于该聚落，如图3(b)所示，在图3(b)中，该聚落中有e型道路和p型道路，但是该p型道路位于聚落边缘处，无法直接服务于该聚落，因此可以将该p型道路视为o型道路，不参与该神经元的构建，则该神经元为i型神经元。
[0071]
其中，ii型神经元是指该神经元仅包含p型道路。绝大部分ii型神经元仅包含一条p型道路，该神经元被这条p型道路贯穿，聚落完全依赖于该道路，如图3(c)所示；少量ii型神经元包含多条p型道路，但同样需要遵循“与聚落核心的连通才是真正的连通”的原则，如图3(d)所示，该聚落被两条p型道路贯穿，但右边的p型道路位于该聚落的边缘位置处，无法
直接服务于该聚落，因此这条p型道路不参与该神经元的构建。
[0072]
步骤5.有效路径搜索
[0073]
搜索任意两个邻近神经元之间的所有有效路径，神经元间的有效路径是指从起点神经元的e型道路开始到终点神经元的e型道路所生成的路径，起点神经元和终点神经元中的其他e型道路和i型道路不参与路径构建，ii型神经元中有效连通聚落内部的p型道路可以视为该神经元的e型道路；由于神经元中可能不止一条e形道路，邻近神经元间的有效路径是指从起点神经元的e型道路直接连接到终点神经元的e型道路所生成的路径，而连接到神经元外部道路或者连接到其他神经元的e型道路不参与本次邻近神经元的路径构建。有效路径是指同行时间成本最小的路径，因为在大型网络中搜索两个网络节点间的所有路径非常耗时，且人们在出行时通常会选择最短、最快的路径，在规划路径时，相比于通行距离，人们更关注通行时间，倾向于选择速度更快的高等级公路，所以采用通行时间作为成本。通行时间主要由道路长度、道路等级及道路曲折度确定，计算公式如下：
[0074][0075]
式中，l为道路长度，v为不同等级公路的设计速度，st为道路弯曲度。
[0076]
由于神经元在聚落的不同方位可能存在多条e型道路，所以一对神经元间可能存在多条路径，搜索一对邻近神经元间的有效路径时，将起点神经元的e型道路与终点神经元的e型道路进行排列组合，采用dijkstra算法搜索所有e型道路组合之间的最小通行时间成本路径，确定有效路径。
[0077]
步骤6.路径简化
[0078]
本发明路径简化主要包括两个阶段，一是邻近神经元间的路径简化，二是邻近神经元组间的路径简化。
[0079]
邻近神经元间的路径简化：
[0080]
在生成的所有有效路径中找到其中的最优路径，该最优路径是指所有有效路径中通行时间成本最低的路径，根据最优路径对两个邻近神经元的所有有效路径进行简化。具体过程如下：
[0081]
任意选择一条有效路径与最优路径进行比较，如果该路径的成本大于最优路径成本与内部通行成本的总和，则认为该路径可以被替代，可形式化表达为：
[0082]
α
×
(κf κs κe)＜κ
t
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(5)
[0083]
式中，α为可容忍成本比；κf为最优路径的通行时间成本；κs为最优路径与当前路径在起点神经元中的内部通行时间成本；κe为最优路径与当前路径在终点神经元中的内部通行时间成本；κ
t
为当前路径的通行时间成本；其中，可容忍成本比表示能够接受最优路径在目标区域的服务能力弱于当前路径的服务能力的程度，即道路网的简化力度，其取值范围为[0.6,1]，当道路网的简化力度越高时，α取值越小，其可以根据道路网的实际化简需求进行选择。
[0084]
例如图4所示，聚落a与聚落b间存在3条路径，路径i从p1出发沿道路ea到达p2，路径ii从p1出发沿道路ec和eb到达p3，路径iii从p1出发沿道路ec和ed到达p4，其中路径i为聚落a与聚落b之间的最优路径。路径ii的起止点分别为p1与p3，其通行成本为4.1。但从p1出发沿路径i到达p2后，再通过内部道路ib到达p3的总成本为2.8，小于路径ii的成本，所以
路径ii可以被路径i替代。减小α的值能够增大化简力度。比如，路径iii的成本为4.7，从p1出发沿路径i到达p2再经道路ib、ia到达p4的总成本为5.0。当α＝1.0时式(5)不成立，路径i不能替代路径iii。但当α＜0.94时式(5)成立，路径i能够替代路径iii。
[0085]
邻近神经元组的路径简化：
[0086]
将邻近神经元间的所有有效路径视为整体进行处理，搜索三个相互邻近的聚落构成的三角结构，对于能够通过有效路径形成三角形结构的邻近神经元组，根据邻近神经元组中简化后路径通行时间成本最大的路径对邻近神经元组中的路径进行简化，判断形成的三角形结构中时间成本最大的边能否被另外两条边的组合替代，若时间成本最大的边对应的时间成本大于另外两条边的时间成本之和，则删除对应时间成本最大的简化后路径。其中，代表三角形各边的路径均是选取的对应边上两个神经元间的通行时间成本最低路径，即两个神经元间的最优路径。该邻近神经元组路径简化的形式化表达为：
[0087]
α
×
(κ
e1
κ
e2
)＜κ
em
(6)
[0088]
式中，α为可容忍成本比；κ
em
为邻近神经元中最大的通行时间成本；κ
e1
与κ
e2
是另外两个通行时间成本。其中，α的取值范围与上述邻近神经元间路径简化中的一致。
[0089]
例如图5所示，图5中聚落a、b、c组神经元组，其中，聚落a与聚落b之间的通行时间成本为4，聚落b与聚落c之间的通行时间成本为2，聚落a与聚落c之间的通行时间成本为8，通过公式(6)可以看出聚落a和聚落c之间的路径可以被聚落a与聚落b的路径和聚落b与聚落c的路径组合替代，因此删除聚落a与聚落c之间的所有路径，实现路径简化。
[0090]
通过上述过程，利用居民地约束道路网综合，充分考虑了道路与居民地的地理关联性，将复杂的路网整体选取分解为相对简单的神经元间路径简化，剔除冗余路径，使得到的综合结果和居民地要素的空间分布高度一致，能够确保聚落间的连通性和道路网的功能性。