概述

各大地图厂商都拥有自己的一套电子地图，也向一般用户、开发者供给了途径规划的接口，根据带起结尾坐标的恳求信息，接口会返回分段的途径坐标串信息。将这些途径信息标准为多段线然后运用GIS软件进行可视化后，能够明晰的看到路网的轮廓。从视觉效果上来看，这就是一套完好的导航路网，可是从底层数据来看，这不是一套符合标准的可复用、可核算的路网系统，节点层缺失、拓扑不完善、线层堆叠等等问题，是没法投入实践出产运用的…

是否有或许根据途径成果的坐标串信息来逆向构建一套拓扑正确、线型合理、点线相关的可核算路网图层呢？

所谓正确的路网，先从最根本的拓扑特点来说，即为每一个路段都标示上拓扑的起结尾节点编号，标示其是否为双向行进路段，明确其行车方向是否与拓扑方向共同，以及根据这些节点之间的衔接联系结构出的有向图能否与真实国际匹配，除开拓扑的合理性，还有视觉感官上的合理性，比如两个路段应该是首尾相连的，可是在你的处理下，本应该在同一个方位的节点，却相隔数十米，尽管他在拓扑上是联通的，这样也是不可行的。

经过最近的一些开发测验，发现根本可行，大约分为以下几个过程：

1. 结构尽或许多的OD对运用接口获取途径数据；
2. 根据途径最小线段单元进行去重；
3. 空间相关生成点层；
4. 兼并2度节点；
5. 去除堆叠路段，还原线型；
6. 极小间隔节点优化。

开发过程

运用的库主要是：geopandas、shapely、networkx

1.结构OD进行途径规划恳求

这个，各大地图厂商都有自己的开发者接口，参照平台文档进行途径规划恳求即可获得分段途径的坐标串信息，然后将其转化为多段线即可:

2.根据途径最小线段单元进行去重

根据返回的坐标串信息，咱们将轨迹线中相邻的两个坐标点位看作一个路段，将其进行拆分，生成多个不包含折点的路段，标示该路段的仅有标识索引字段为起结尾坐标(当作字符串处理)，然后依照该索引字段进行暴力去重，即可减少大部分的堆叠路段。

3.空间相关生成点层

提取路段的起结尾坐标信息，构成集合，然后依然是根据坐标进行去重，然后别离赋予node_id,生成点层后与线层的起点、结尾tag相关，为路段增加拓扑起结尾的节点编号，即路段的from_node和to_node编号。这儿需求留意的是，有部分点位，两个点位之间：经纬度坐标小数点前6~7位都是一样的，在小数点最终一位不共同，这种点位运用纯字符串去重的办法是无法去重的，这样会得到视觉上同一个方位有两个不同node_id的节点，还会导致该点处拓扑不连通：

这种状况处理的办法是：对一切的点层做一个半径为0.1~0.8m的buffer后进行空间自相交运算然后识别出这些简直堆叠的点的组别，这儿的优化处理我放在最终一步去做。

还有需求留意的一点是：在为路段增加拓扑起结尾的节点编号后，某些路段的起结尾节点编号刚好相反，那么阐明该处是一条可双向行进的路段，咱们需求将他们找出来，然后只保存其间一条，同时方向字段dir标记为0.

4.兼并2度节点

1~3过程较为简略，从这儿开始，就要和复杂多变的途径线型斗智斗勇了，总会有意想不到的bug线型呈现！由于现在的路网十分碎，一个一两百米的路段或许会有十多个节点，且这些节点都是度为2的节点，即这些节点大部分都没有存在必要，一般节点的呈现是在不同道路的交叉方位处、路段特点的变化处。这块的功能之前在某个项目正好写过一次，所以算是复用了之前的模块。

大约的思路是：过程3输出的线层和点层构建整个网络的无向图和有向图，根据无向图找出一切的度为2的节点，然后抽取子图，再遍历子图进行兼并操作：

在剖析每个子图时，愈加精准的兼并需求考虑方向约束(即行车方向不共同的link是否答应兼并)、是否答应兼并后呈现环(上图中的子图6中的节点兼并后就会构成一个环)、特点约束，找出能够兼并的link组，然后在几何上对路段进行兼并，同步也需求更新其拓扑联系，如上图子图2所相关的4个路段会变为1个路段：

兼并前的拓扑联系：

兼并后的拓扑联系：

这样能够删去许多的非必要节点，减少咱们的网络规划，在途径搜索的时分会更快。

考虑方向约束的办法

咱们一般运用dir来表明路段的实践行车方向，假如dir=1代表该路段的实践答应的行车方向与拓扑方向共同，假如dir=-1代表该路段的实践答应的行车方向与拓扑方向相反，假如dir=0代表该路段的实践答应的行车方向为双向，所以假如有两个相邻路段的行车方向不共同(简直很少)，那么这种兼并是不被答应的： 在考虑这种状况的约束时，咱们最好在数据预处理时将一切的dir为-1的路段转化为1，那么此刻一切路段的dir值只或许为1或者0，那么对于开始筛选的能够兼并的link组，只有dir值接连为1或者0的才有或许进行兼并：

然后再考虑每个节点的不平衡度：

5. 去除堆叠路段，还原线型

找到一切的堆叠link组

做完过程4，得到的路网还有部分问题，大多是一些相同方位的link堆叠(没有彻底堆叠，相隔间隔很近,经过QGIS查看发现，间隔一般在0~0.2m左右，堆叠形状十分多，这儿仅罗列一种状况)：

一般来说这种状况，假如不放大看很难发觉，可是这会导致拓扑有问题，并且作为一个细节控!这种问题有必要解决!消除堆叠路段的思路是：对于每一条link做0.5m左右的缓冲区，然后去和其他每一条link(除开自身)做空间相交运算，然后核算相交面积占比自身面积的比率，咱们设定一个阈值60%,当两条link的相交比率超过了这个阈值，咱们即能够为他们是堆叠的，此刻咱们把这两条link看做无向图的两个节点，以为他们是联通(堆叠)的，重复以上过程，咱们得到了一个无向图,其间应该包含了多个相互不连通的子图，每个子图内是联通的，这就是咱们要找的堆叠link组别：

以上图路网为例，咱们得到的无向图的节点(实践是link的编号)衔接联系为：(2,4),(2,5),(4,6),(2,6),(3,7)

运用连通图算法找到其间有两个联通图：

图1：(2,4),(2,5),(4,6),(2,6)，图2：(3,7)

这样一来咱们就对堆叠的link组进行了分组，然后遍历每一个组别，生成新的线型。

根据堆叠link组生成新线型

(1).取出堆叠组中最长的那条link作为base_link

(2).将堆叠Link组所涉及的node信息取出来，别离沿着base_link的拓扑方向核算其与base_link的方位联系(在base_link上的投影点间隔拓扑起点的间隔$L$)，在起点外侧标记为head_beyond，$L$为负数)，在尾部外侧标记为tail_beyond（$L$大于base_link的线型长度），其他标记为within内部

(3).运用节点在base_link上的投影切割base_link：

一切的节点都需求去对base_link做切割操作嘛？不是的。假如间隔十分近的点，咱们只保存度最大的那一个用于切割base_link，由于度最大的点他很大或许还衔接了其他的link，咱们不期望破坏原有的拓扑联系，如图，经过检测算法，假如节点1和节点9被识别为在一组内，他们的间隔小于规则的间隔阈值，咱们会优先剔除节点1(度为1)，保存节点9(度为2)，节点2、3、4被识别为一组，三个节点的度都是1，随机保存一个节点，所以咱们最终会运用节点9、节点(4).节点5在base_link上的投影点来打断base_link，生成的新节点和link：

(5).删去原有堆叠link组，增加新线型

删去本来的堆叠link组，增加新的link，这样一来这一组内的堆叠现象就被消除，遍历一切的组做相同的操作即可：

可是从成果中能够看到，这样带来的问题是，也会生成一些2度节点，咱们假如愿意，能够对当时的link图层再做一次过程4(兼并2度节点)

为何挑选这样的办法更新呢？由于堆叠路段的形状多种多样，远不止上图所示，这种更新机制简直能够面临一切的堆叠景象，且能最大程度的坚持原有线型。

6. 极小间隔节点优化

在 3.空间相关生成点层 中，咱们提到了有部分点位简直重合(地理坐标仅仅小数点最终一位不一样)，由于之前的暴力字符串去重，这种点位依然被看成是两个点，这会导致路网的拓扑不连通，所以咱们仍是运用点缓冲区的办法核算点与点之间的相交百分比的办法来识别这种点集，然后任意保存其间一个即可，同时记载{删去点ID：保存点ID}的哈希表，用于更新线层的from_node和to_node，几何线型也能够刷新，可是可做可不做，由于肉眼简直分辩不出来。

北京某片区逆向成果

只作了一次2度节点兼并操作：

只要咱们结构的OD对足够多，就能确保某区域范围内的路网齐备性，一个较好的思路是：先根据一定量的OD逆向一个基础版别的路网，然后做一个路网增量更新的机制，当今后每进来一条新的途径，就将其和基础路网进行比照剖析，增量变化，逐渐完善路网。