一种基于衍生平行线段的大规模路网方向判定方法及系统

摘要

本发明涉及电子地图技术领域，公开了一种基于衍生平行线段的大规模路网方向判定方法及系统,根据路网数据经纬度范围，将路网平面划分为不同的网格，将路网内各几何对象相邻两点形成的索引线段存储至各网格，构建一级索引网格，根据每一条索引线段构建二级索引矩形，对于每条索引线段，在一级索引网格中遍历查找位于二级索引矩形范围内且满足衍生平行条件的其他索引线段，并判断其相对位置，从而构建了由索引线段以及该线段所关联的平行线段组成的衍生平行集合，每条路段将生成多个衍生平行集合，然后进行路段的连通关系检查，最终根据平行线段相对位置出现的次数以及索引线段经纬度坐标确定路段方向，可提升大规模路网方向判定的效率和准确性。

权利要求

1.一种基于衍生平行线段的大规模路网方向判定方法，其特征在于，包括如下步骤：S1、获取矢量路网文件中的几何对象信息以及构成几何对象的要素信息，几何对象信息包括编号、类型，构成几何对象的要素信息包括点编号、点经纬度坐标；

S2、根据路网数据经纬度范围，将路网平面划分为不同的网格，将构成每一个几何对象的相邻两点所构成的线段称为索引线段，识别该索引线段所处的网格，将该索引线段的索引存储至该网格，形成的网格称为一级索引网格；

S3、从S2中确定的索引线段中任意获取一条线段，称为主线段；构建以主线段的中点为中心对称点的矩形区域，称为二级索引矩形；

S4、依次遍历一条路段的各个主线段，识别该主线段所在一级索引网格，进行下述循环：建立空集合，将主线段存入该集合；于该主线段所在的一级索引网格中，遍历网格中的其他索引线段，从中挑选一条线段作为待分析索引线段，首先判断该待分析索引线段是否位于该主线段的二级索引矩形中，再判断该集合中是否存在与该待分析索引线段平行的线段，若不存在，则重新挑选待分析索引线段继续搜索，若存在，则判断该待分析索引线段与主线段的相对位置，将带相对位置判定的该索引输出并加入该集合，继续搜索；循环终止后，各主线段生成的集合称为衍生平行线段集合Qi，衍生平行线段集合Qi表示第i条主线段对应的二级索引矩形内该主线段和与其平行的索引线段集，将与主线段平行的索引线段称为平行线段；衍生平行线段集合Qi结构为(主线段信息，平行线段1信息，平行线段2信息……)，所有的衍生平行集合Qi构成大集合Q；

S5、从大集合Q中获取一条线段，遍历其他线段并挑选出一条，对这两条线段的角度和距离进行判断，识别这两条线段是否属于同一路段，若是，则给这两条线段添加同样的连通属性值，直至所有属于同一路段的线段连通属性值添加结束；

S6、从第一个衍生平行线段集合Q1开始，对后面的衍生平行线段集合Q2、Q3...Qi进行判断，如延伸方向相同则执行集合合并操作，如延伸方向不同则停止当前合并操作并开始新的合并操作，合并后的集合称为分段集合；

S7、根据分段集合内的主线段延伸方向、主线段与平行线段的相对位置结果统计次数，判断主线段的方向。

2.根据权利要求1所述的基于衍生平行线段的大规模路网方向判定方法，其特征在于，步骤S2中，在一级索引网格四周添加缓冲区域，构建一级索引缓冲区；步骤S4中，在主线段对应的一级索引网格和一级索引缓冲区内搜索平行线段，构建衍生平行线段集合。

3.根据权利要求1所述的基于衍生平行线段的大规模路网方向判定方法，其特征在于，步骤S3中，根据每一条主线段的斜率添加该主线段的延伸方向识别标志：一条主线段Lmn所在直线的方程为

y‑Kmnx‑Bmn＝0

若主线段Lmn斜率为0，则添加该线段延伸方向识别标志为“vertical”；

若主线段Lmn斜率大于0，则添加该线段延伸方向识别标志为“positive”；

若主线段Lmn斜率小于0，则添加该线段延伸方向识别标志为“negative”；

在步骤S6中，根据主线段的延伸方向识别标志进行判断，若两个集合的主线段延伸方向识别标志则进行合并。

4.根据权利要求1所述的基于衍生平行线段的大规模路网方向判定方法，其特征在于，步骤S4中，进行判断该待分析索引线段与主线段的相对位置时，平行线段lto1两端点Pto1(xto1，yto1)、Pto2(xto2，yto2)，主线段Lmn方程y‑Kmnx‑Bmn＝0，计算yto1‑Kmnxto1‑Bmn，yto2‑Kmnxto2‑Bmn，若yto1‑Kmnxto1‑Bmn＞0，且yto2‑Kmnxto2‑Bmn＞0，判定该平行线段位于主线段的上方，相对位置判定标记为“above”；若yto1‑Kmnxto1‑Bmn＜0，且yto2‑Kmnxto2‑Bmn＜0，判定该平行线段位于主线段的下方，相对位置判定标记为“below”。

5.根据权利要求1所述的基于衍生平行线段的大规模路网方向判定方法，其特征在于，步骤S5中，将大集合Q内的任一线段作为待判断线段，从同一集合内其他线段中选取一条线段，计算：

待判断线段的第一个点与选取线段的第一个点的距离；

待判断线段的第一个点与选取线段的第二个点的距离；

待判断线段的第二个点与选取线段的第一个点的距离；

待判断线段的第二个点与选取线段的第二个点的距离；

若上述四个距离中最小值小于预设阈值dset，最小值为待判断线段的第一个点与选取线段的第一个点的距离：标记待判断线段的第一个点为“起点”，选取线段的第一个点为“起点”；

最小值为待判断线段的第一个点与选取线段的第二个点的距离：标记待判断线段的第一个点为“起点”，选取线段的第一个点为“终点”；

最小值为待判断线段的第二个点与选取线段的第一个点的距离：标记待判断线段的第一个点为“终点”，选取线段的第一个点为“起点”；

最小值为待判断线段的第二个点与选取线段的第二个点的距离：标记待判断线段的第一个点为“终点”，选取线段的第一个点为“终点”；

若待判断线段的第一个点为起点，以起点为计算起点，在待判断线段所在的几何对象上，顺序后推预设的计算点个数Npoint为计算终点，当相邻两点的距离大于设定阈值时，计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

若待判断线段的第一个点为终点，以终点为计算起点，在待判断线段所在的几何对象上，逆序前推预设的计算点个数Npoint为计算终点，当相邻两点的距离大于设定阈值时，计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

若选取线段的第一个点为起点，以起点为计算起点，在选取线段所在的几何对象上，顺序后推预设的计算点个数为计算终点，当相邻两点的距离大于设定阈值时，计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

若选取线段的第一个点为终点，以终点为计算起点，在选取线段所在的几何对象上，逆序前推预设的计算点个数为计算终点，当相邻两点的距离大于设定阈值时，计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

计算上述扩展后的待判断线段与扩展后的选取线段相邻两线段的夹角平均值之差并取绝对值：

若该绝对值小于设定阈值angle_aveset，则判定待判断线段与选取线段属于同一线段，将待判断线段与选取线段的连通编号均设置为待判断线段的几何类型编号；

若该绝对值大于设定阈值angle_aveset，则判定待判断线段与选取线段属于同一线段，将选取线段的连通编号设置为选取线段的几何类型编号。

6.根据权利要求1所述的基于衍生平行线段的大规模路网方向判定方法，其特征在于，步骤S6中，设定一个平行长度占比阈值，若平行线段在主线段上的投影距离占主线段长度的比例小于该平行长度占比阈值，则将该平行线段剔除出该分段集合。

7.根据权利要求1所述的基于衍生平行线段的大规模路网方向判定方法，其特征在于，若主线段的延伸方向为向上，统计分段集合内相对位置位于该主线段上方和下方的平行线段的数量，若位于该主线段上方的平行线段多于位于该主线段下方的平行线段，则该主线段的方向为“由东往西”，否则为“由北往南”；

若主线段的延伸方向为向下，统计分段集合内相对位置位于该主线段上方和下方的平行线段的数量，若位于该主线段上方的平行线段多于位于该主线段下方的平行线段，则该主线段方向为“由西往东”，否则为“由南往北”。

8.一种基于衍生平行线段的大规模路网方向判定系统，其特征在于，包括：数据读取模块，用于读取矢量路网文件中的几何对象信息以及构成几何对象的要素信息，几何对象信息包括编号、类型，构成几何对象的要素信息包括点编号、点经纬度坐标；

一级索引网格构造模块，用于根据路网数据经纬度范围，将路网平面划分为不同的网格，将构成每一个几何对象的相邻两点所构成的线段称为索引线段，识别该索引线段所处的网格，将该线段的索引存储至该网格，形成的网格称为构建一级索引网格；

二级索引矩形构造模块，用于从一级索引网格构造模块存储的索引线段中任意获取一条线段，称为主线段，构建以主线段的中点为中心对称点的矩形区域，称为二级索引矩形；

平行线段集合构造模块，用于建立大集合Q，其中大集合Q由衍生平行线段集合Qi构成，衍生平行线段集合Qi表示第i条主线段对应的二级索引矩形内该主线段和与其平行的索引线段集，将与主线段平行的索引线段称为平行线段；

平行线段连通模块，用于对每一个大集合Q内的任意两条线段的角度和距离的判断，判定这两条线段是否属于同一路段，若是，则给这两条线段添加同样的连通属性值，直至所有属于同一路段的线段连通属性值添加结束；

分段集合构造模块，用于从第一个衍生平行线段集合Q1开始，对后面的衍生平行线段集合Q2、Q3...Qi进行判断，如延伸方向相同则执行集合合并操作，如延伸方向不同则停止当前合并操作并开始新的合并操作，合并后的集合称为分段集合；

平行路段方向判断模块，用于根据分段集合内的主线段延伸方向、主线段与平行线段的相对位置结果统计次数，判断主线段的方向。

9.根据权利要求8所述的基于衍生平行线段的大规模路网方向判定系统，其特征在于，还包括一级索引缓冲区构造模块，一级索引缓冲区构造模块用于在一级索引网格四周添加添加缓冲区域，构建一级索引缓冲区；平行线段集合构造模块在一级索引网格和一级索引缓冲区中搜索主线段的平行线段，构建衍生平行线段集合。

10.根据权利要求8所述的基于衍生平行线段的大规模路网方向判定系统，其特征在于，还包括平行路段优化模块，用于剔除平行路段在主线段上的投影距离占主线段长度的比例较小的平行线段。

说明书

一种基于衍生平行线段的大规模路网方向判定方法及系统

技术领域

[0001] 本发明涉及电子地图技术领域，特别是涉及一种基于衍生平行线段的大规模路网方向判定方法及系统。

背景技术

[0002] 矢量路网数据中，一般不会给出路网内各个路段的方向，缺乏方向属性的路段不利于解决交通领域内交通规划设计、交通信息管理等问题。少量的路段可通过人工观测或
者根据平行路段标定，而市级、省级行政区域等较大范围内矢量路网数据存在数据庞大、复
杂、偏差率高等问题，运用常规的人工观测或者根据平行路段识别，速度较慢，且错误、遗漏
问题较多，使得方向判定结果准确率降低。

[0003] 中国发明专利申请CN112348917A(公开日为2021年02月09日)公开了一种路网地图实现方法、装置和电子设备，包括：利用格网坐标系对待建图的路网进行离散化处理，得
到以被占据网格表征路网的基础路网地图；根据路网的方向信息和网格间连接关系，确定
基础路网地图中各被占据网格的可通行方向；根据各被占据网格的可通行方向确定相应被
占据网格的路网编码，从而实现路网地图。通过格网坐标系离散化处理路网，使得后续实现
的路网地图具备了可输入神经网络的基础；基于路网的方向信息和网格间连接关系确定各
被占据网格的可通行方向，进一步确定被占据网格的路网编码，从而实现了带有道路方向
信息的路网地图，能够被神经网络所提取到，提升训练效果。该专利采用格网坐标系进行处
理，根据路网的方向信息和网格间连接关系，为每个网格添加通行方向的路网编码，并未公
开如何确定路网的方向信息，仍然需要人工观测或平行路段标定等方法进行确定，效率低，
不够准确。

发明内容

[0004] 本发明的目的是提供一种效率和准确性高的基于衍生平行线段的大规模路网方向判定方法及系统。

[0005] 为了实现上述目的，本发明提供了一种基于衍生平行线段的大规模路网方向判定方法，包括如下步骤：

[0006] S1、获取矢量路网文件中的几何对象信息以及构成几何对象的要素信息，几何对象信息包括编号、类型，构成几何对象的要素信息包括点编号、点经纬度坐标；

[0007] S2、根据路网数据经纬度范围，将路网平面划分为不同的网格，将构成每一个几何对象的相邻两点所构成的线段称为索引线段，识别该索引线段所处的网格，将该索引线段
的索引存储至该网格，形成的网格称为一级索引网格；

[0008] S3、从S2中确定的索引线段中任意获取一条线段，称为主线段；构建以主线段的中点为中心对称点的矩形区域，称为二级索引矩形；

[0009] S4、依次遍历一条路段的各个主线段，识别该主线段所在一级索引网格，进行下述循环：建立空集合，将主线段存入该集合；于该主线段所在的一级索引网格中，遍历网格中
的其他索引线段，从中挑选一条线段作为待分析索引线段，首先判断该待分析索引线段是
否位于该主线段的二级索引矩形中，再判断该集合中是否存在与该待分析索引线段平行的
其他索引线段，若不存在，则重新挑选待分析索引线段继续搜索，若存在，则判断该待分析
索引线段与主线段的相对位置，将带相对位置判定的该索引输出并加入该集合，继续搜索；
循环终止后，各主线段生成的集合称为衍生平行线段集合Qi，衍生平行线段集合Qi表示第i
条主线段对应的二级索引矩形内该主线段和与其平行的索引线段集，将与主线段平行的索
引线段称为平行线段；衍生平行线段集合Qi结构为(主线段信息，平行线段1信息，平行线段
2信息……)，所有的衍生平行集合Qi构成大集合Q；

[0010] S5、从大集合Q中获取一条线段，遍历其他线段并挑选出一条，对这两条线段的角度和距离进行判断，识别这两条线段是否属于同一路段，若是，则给这两条线段添加同样的
连通属性值，直至所有属于同一路段的线段连通属性值添加结束；

[0011] S6、从第一个衍生平行线段集合Q1开始，对后面的衍生平行线段集合Q2、 Q3…Qi进行判断，如延伸方向相同则执行集合合并操作，如延伸方向不同则停止当前合并操作并开
始新的合并操作，合并后的集合称为分段集合；

[0012] S7、根据分段集合内的主线段延伸方向、主线段与平行线段的相对位置结果统计次数，判断主线段的方向。

[0013] 作为优选方案，步骤S2中，在一级索引网格四周添加缓冲区域，构建一级索引缓冲区；步骤S4中，在主线段对应的一级索引网格和一级索引缓冲区内搜索平行线段，构建衍生
平行线段集合。

[0014] 作为优选方案，步骤S3中，根据每一条主线段的斜率添加该主线段的延伸方向识别标志：一条主线段Lmn所在直线的方程为

[0015] y‑Kmnx‑Bmn＝0

[0016] 若主线段Lmn斜率为0，则添加该线段延伸方向识别标志为“vertical”；

[0017] 若主线段Lmn斜率大于0，则添加该线段延伸方向识别标志为“positive”；

[0018] 若主线段Lmn斜率小于0，则添加该线段延伸方向识别标志为“negative”；

[0019] 在步骤S6中，根据主线段的延伸方向识别标志进行判断，若两个集合的主线段延伸方向识别标志则进行合并。

[0020] 作为优选方案，步骤S4中，进行判断该待分析索引线段与主线段的相对位置时，平行线段lto1两端点Pto1(xto1，yto1)、Pto2(xto2，yto2)，主线段Lmn方程 y‑Kmnx‑Bmn＝0，计算yto1‑
Kmnxto1‑Bmn，yto2‑Kmnxto2‑Bmn，若 yto1‑Kmnxto1‑Bmn＞0，且yto2‑Kmnxto2‑Bmn＞0，判定该平行线段
位于主线段的上方，相对位置判定标记为“above”；若yto1‑Kmnxto1‑Bmn＜0，且 yto2‑Kmnxto2‑Bmn
＜0，判定该平行线段位于主线段的下方，相对位置判定标记为“below”。

[0021] 作为优选方案，步骤S5中，将大集合Q内的任一线段作为待判断线段，从同一集合内其他线段中选取一条线段，计算：

[0022] 待判断线段的第一个点与选取线段的第一个点的距离；

[0023] 待判断线段的第一个点与选取线段的第二个点的距离；

[0024] 待判断线段的第二个点与选取线段的第一个点的距离；

[0025] 待判断线段的第二个点与选取线段的第二个点的距离；

[0026] 若上述四个距离中最小值小于预设阈值dset，

[0027] 最小值为待判断线段的第一个点与选取线段的第一个点的距离：标记待判断线段的第一个点为“起点”，选取线段的第一个点为“起点”；

[0028] 最小值为待判断线段的第一个点与选取路段的第二个点的距离：标记待判断线段的第一个点为“起点”，选取线段的第一个点为“终点”；

[0029] 最小值为待判断线段的第二个点与选取路段的第一个点的距离：标记待判断线段的第一个点为“终点”，选取线段的第一个点为“起点”；

[0030] 最小值为待判断线段的第二个点与选取路段的第二个点的距离：标记待判断线段的第一个点为“终点”，选取线段的第一个点为“终点”；

[0031] 若待判断线段的第一个点为起点，以起点为计算起点，在待判断线段所在的几何对象上，顺序后推预设的计算点个数Npoint为计算终点，当相邻两点的距离大于设定阈值时，
计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值。

[0032] 若待分析路段的第一个点为终点，以终点为计算起点，在待判断线段所在的几何对象上，逆序前推预设的计算点个数Npoint为计算终点，当相邻两点的距离大于设定阈值时，
计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值。

[0033] 若选取路段的第一个点为起点，以起点为计算起点，在选取线段所在的几何对象上，顺序后推预设的计算点个数为计算终点，当相邻两点的距离大于设定阈值时，计算从计
算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

[0034] 若选取路段的第一个点为终点，以终点为计算起点，在选取线段所在的几何对象上，逆序前推预设的计算点个数为计算终点，当相邻两点的距离大于设定阈值时，计算从计
算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

[0035] 计算上述扩展后的待判断线段与扩展后的选取线段相邻两线段的夹角平均值之差并取绝对值：

[0036] 若该绝对值小于设定阈值angle_aveset，则判定待判断线段与选取线段属于同一路段，将待判断线段与选取线段的连通编号均设置为待判断线段的几何类型编号；

[0037] 若该绝对值大于设定阈值angle_aveset，则判定待判断线段与选取线段属于同一路段，将选取线段的连通编号设置为选取线段的几何类型编号。

[0038] 作为优选方案，步骤S6中，设定一个平行长度占比阈值，若平行路段在主线段上的投影距离占主线段长度的比例小于该平行长度占比阈值，则将该平行线段剔除出该分段集
合。

[0039] 作为优选方案，若主线段的延伸方向为向上，统计分段集合内相对位置位于该主线段上方和下方的平行线段的数量，若位于该主线段上方的平行线段多于位于该主线段下
方的平行线段，则该主线段的方向为“由东往西”，否则为“由北往南”；

[0040] 若主线段的延伸方向为向下，统计分段集合内相对位置位于该主线段上方和下方的平行线段的数量，若位于该主线段上方的平行线段多于位于该主线段下方的平行线段，
则该主线段方向为“由西往东”，否则为“由南往北”。

[0041] 本发明还提供一种基于衍生平行线段的大规模路网方向判定系统，包括：

[0042] 数据读取模块，用于读取矢量路网文件中的几何对象信息以及构成几何对象的要素信息，几何对象信息包括编号、类型，构成几何对象的要素信息包括点编号、点经纬度坐
标；

[0043] 一级索引网格构造模块，用于根据路网数据经纬度范围，将路网平面划分为不同的网格，将构成每一个几何对象的相邻两点所构成的线段称为索引线段，识别该索引线段
所处的网格，将该线段的索引存储至该网格，形成的网格称为构建一级索引网格；

[0044] 二级索引矩形构造模块，用于从一级索引网格构造模块存储的索引线段中任意获取一条线段，称为主线段，构建以主线段的中点为中心对称点的矩形区域，称为二级索引矩
形；

[0045] 平行线段集合构造模块，用于建立大集合Q，其中大集合Q由衍生平行线段集合Qi构成，衍生平行线段集合Qi表示第i条主线段对应的二级索引矩形内该主线段和与其平行
的索引线段集，将与主线段平行的索引线段称为平行线段；

[0046] 平行线段连通模块，用于对每一个大集合Q内的任意两条线段的角度和距离的判断，判定这两条线段是否属于同一路段，若是，则给这两条线段添加同样的连通属性值，直
至所有属于同一路段的线段连通属性值添加结束；

[0047] 分段集合构造模块，用于从第一个衍生平行线段集合Q1开始，对后面的衍生平行线段集合Q2、Q3…Qi进行判断，如延伸方向相同则执行集合合并操作，如延伸方向不同则停
止当前合并操作并开始新的合并操作，合并后的集合称为分段集合；

[0048] 平行路段方向判断模块，用于根据分段集合内的主线段延伸方向、主线段与平行线段的相对位置结果统计次数，判断主线段的方向。

[0049] 作为优选方案，还包括一级索引缓冲区构造模块，一级索引缓冲区构造模块用于在一级索引网格四周添加添加缓冲区域，构建一级索引缓冲区；平行线段集合构造模块在
一级索引网格和一级索引缓冲区中搜索主线段的平行线段，构建衍生平行线段集合。

[0050] 作为优选方案，还包括平行路段优化模块，用于剔除平行路段在主线段上的投影距离占主线段长度的比例较小的平行线段。

[0051] 与现有技术相比，本发明的有益效果在于：

[0052] 本发明根据路网数据经纬度范围，将路网平面划分为不同的网格，将路网内各几何对象相邻两点形成的索引线段存储至各网格，构建一级索引网格，根据每一条索引线段
构建二级索引矩形，对于每条索引线段，在一级索引网格中遍历查找位于二级索引矩形范
围内且满足衍生平行条件的其他索引线段，并判断其相对位置，从而构建了由索引线段以
及该线段所关联的平行线段组成的衍生平行线段集合，每条路段将生成多个衍生平行线段
集合，然后进行路段的连通关系检查，最终根据平行线段相对位置出现的次数以及索引线
段经纬度坐标确定路段方向，可提升大规模路网方向判定的效率和准确性。

附图说明

[0053] 图1是本发明实施例的大规模路网方向判定方法的流程示意图。

[0054] 图2是本发明实施例的一级索引网格和二级索引矩形示意图。

[0055] 图3是本发明实施例的衍生平行线段集合构建流程图。

[0056] 图4是现有技术挑选与主线段平行的线段的示意图。

[0057] 图5是本发明实施例的部分主线段与其平行线段的集合构建结果示意图。

[0058] 图6是本发明实施例的部分主线段与其平行线段连通后的平行集合结果。

[0059] 图7是本发明实施例的部分主线段与其平行线段优化后的平行集合结果。

[0060] 图8是本发明实施例的路网方向判断结果示意图。

具体实施方式

[0061] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0062] 如图1至图7所示，本发明优选实施例的一种基于衍生平行线段的大规模路网方向判定方法，包括如下步骤：

[0063] S1、获取矢量路网文件中的几何对象信息以及构成几何对象的要素信息，几何对象信息包括编号、类型，构成几何对象的要素信息包括点编号、点经纬度坐标。几何对象对
应现实中的路段，将现实中的各路段识别为各几何对象。首先读取需判定平行路段方向的
矢量路网文件中的几何数据，获取几何对象数据及构成几何对象的点经纬度坐标数据，并
从中挑选出最小经度longmin，最小纬度latmin，最大经度longmax，最大纬度longmax。

[0064] S2、根据路网数据经纬度范围，将路网平面划分为不同的网格，将构成每一个几何对象的相邻两点所构成的线段称为索引线段，识别该索引线段所处的网格，将该索引线段
的索引存储至该网格，形成的网格称为一级索引网格。本发明根据构成路段的点，将路段读
取为一个个索引线段进行处理。步骤S2用步骤S1获取的最大经度减去最小经度，除以指定
经度划分数Nlong，得到单个网格跨经度 longspan，用数据读取模块中获取的最大纬度减去最
小纬度，除以指定纬度划分数 Nlat，得到单个网格跨纬度latspan。

[0065] 根据经纬度划分数将路网数据划分为网格，此时任意一个网格的经度范围为 [longmin+i*longspan，longmin+(i+1)*longspan]，纬度范围为[latmin+j* latspan，latmin+(j+
1)*latspan]。其中i∈[0，Nlong‑1]，j∈[0，Nlat‑1]。

[0066] 另外，本发明在一级索引网格四周添加添加缓冲区域，构建一级索引缓冲区。设置一级索引缓冲区的目的是确保边界附近几何对象能被识别：设置缓冲系数Bnet，添加缓冲区
域之后的任意一个网格的经度范围为[longmin+(i‑Bnet)* longspan，longmin+(i+Bnet)*
longspan]，纬度范围为[latmin+(j‑Bnet)* latspan，latmin+(j+Bnet)*latspan]。

[0067] 用步骤S1获取到的所有构成几何对象的点经纬度坐标，

[0068] 从构成第一个几何对象的第一个点到构成第一个几何对象的第二个点，计算两点所连成的线段L11中点P11(x11，y11)坐标，

[0069] 从计算构成第一个几何对象的第二个点到构成第一个几何对象的第三个点，计算两点所连成的线段L12中点P12(x12，y12)坐标

[0070] ……

[0071] 从构成第二个几何对象的第一个点到构成第二个几何对象的第二个点，计算相邻两点所连成的线段L21中点P21(x21，y21)坐标

[0072] ……

[0073] 从构成第m个几何对象的第n点到构成第m个几何对象的第n+1个点，计算相邻两点所构成线段Lmn中点Pmn(xmn，ymn)坐标

[0074] ……

[0075] 将xmn与[longmin+i*longspan，longmin+(i+1)*longspan]，对比，确定i 值；ymn与[latmin+j*latspan，latmin+(j+1)*latspan]，对比，确定j值，从而可确定相邻两点所构成线段
中点位于哪一个网格，将该线段的索引存储至该网格，称索引线段。重复上述判断，直至所
有索引线段线判断完毕，将其分配至对应的网格。

[0076] S3、从S2中确定的索引线段中任意获取一条线段Lmn，称为主线段；构建以主线段的中点为中心对称点的矩形区域，称为二级索引矩形。确定主线段所在直线的方程：

[0077] y‑Kmnx‑Bmn＝0

[0078] 其中：

[0079]

[0080]

[0081] 若主线段Lmn斜率为0，则添加该线段延伸方向识别标志为“vertical”；

[0082] 若主线段Lmn斜率大于0，则添加该线段延伸方向识别标志为“positive”；

[0083] 若主线段Lmn斜率小于0，则添加该线段延伸方向识别标志为“negative”；

[0084] 直至所有主线段延伸方向识别标志添加完毕。该延伸方向识别标志为自设定，无特殊含义。

[0085] 构建以主线段Lmn中点Pmn(xmn，ymn)为中心对称点的矩形，该矩形即为二级索引矩形，其中矩形的四点坐标定义为

[0086] (xc‑SR*d，yc‑SR*d)，

[0087] (xc‑SR*d，yc+SR*d)，

[0088] (xc+SR*d，yc‑SR*d)，

[0089] (xc+SR*d，yc+SR*d)

[0090] 其中d为Pmn(xmn，ymn)，Pm(n+1)(xm(n+1)，ym(n+1))两点之间距离

[0091] 参数SR定义如下：

[0092] SR＝e‑10000d+3+C

[0093] 其中C为经验参数，

[0094] 一级索引网格与二级索引矩形的简单示意图如图2所示。设置一级索引网格的目的是在路网空间范围很大的情况下，减少搜索范围以加快搜索速度。二级索引矩形设置的
作用除了继续减少搜索范围之外，更是在较小的范围内构建平行线段的集合，从而减少平
行线段的识别错误率。

[0095] S4、依次遍历一条路段的各个主线段，识别该主线段所在一级索引网格，进行下述循环：建立空集合，将主线段存入该集合；于该主线段所在的一级索引网格中，遍历网格中
的其他索引线段，从中挑选一条线段作为待分析索引线段，首先判断该待分析索引线段是
否位于该主线段的二级索引矩形中，再判断该集合中是否存在与该待分析索引线段平行的
其他索引线段，若不存在，则重新挑选待分析索引线段继续搜索，若存在，则判断该待分析
索引线段与主线段的相对位置，将带相对位置判定的该索引输出并加入该集合，继续搜索；
循环终止后，各主线段生成的集合称为衍生平行线段集合Qi，衍生平行线段集合Qi表示第i
条主线段对应的二级索引矩形内该主线段和与其平行的索引线段集，将与主线段平行的索
引线段称为平行线段；衍生平行线段集合Qi结构为(主线段信息，平行线段1信息，平行线段
2信息……)，所有的衍生平行集合Qi构成大集合Q。本发明不仅仅挑选与主线段平行的索引
线段，而是挑选出该主线段对应集合内的所有线段平行的索引线段集，在后面的步骤中再
进行筛选。具体步骤请参见图3。

[0096] 步骤S4可挑选出二级索引矩形内所有与主线段平行的索引线段。现有的方法中，通过设置与主线段平行的索引线段和该主线段之间的距离阈值，来挑选出与主线段平行的
线段。但是，现有方法的阈值若设置过小，可能无法找到与主线段平行的线段或数量较少；
若阈值若设置过大，则会挑选到其他路段的线段，导致判断出错。如图4所示，道路1中包括
线段1、2、3、4和5；道路2中包括线段 6、7、8和9，以线段4为主线段，设置与主线段平行的索
引线段和该主线段之间的距离为d1来挑选平行线段，则只能识别到线段3和线段5，而线段
3、线段5 和主线段4位于同一道路，但分别位于主线段4的上方和下方，位于主线段4上方和
下方的平行线段数量相等，因此无法判断主线段4的方向；设置与主线段平行的索引线段和
该主线段之间的距离为d2，则只能识别到线段5，线段5属于道路2的线段，因此，用于判断道
路1的主线段4的方向同样会出错。本实施例的方法可避免上述情况，在挑选平行线段时，既
挑选到了与主线段平行的线段，也挑选到了与平行线段平行的线段，如图4所示，设置与主
线段平行的索引线段和该主线段之间的距离为d1，可挑选到与主线段4平行的线段3和5、与
线段3平行的线段2以及与线段2平行的线段1，大大提高衍生平行线段集合Qi中的线段数
量，可以极小距离的阈值衍生出所有与主线段平行的线段。

[0097] 步骤S4遍历步骤S2中的所有主线段，针对第一条主线段，根据步骤S2中所述，识别该主线段所在的一级搜索范围，建立几何对象编号、主线段起点编号、主线延伸方向、连通
编号(起始为空值)的衍生平行线段集合Q1。

[0098] ……

[0099] 针对第i条主线段，根据步骤S2中所述，识别主线段所在的一级搜索范围，建立几何对象编号、主线段起点编号、主线延伸方向、连通编号(起始为空值) 的衍生平行线段集
合Qi。

[0100] ……

[0101] 以第一条主线段L11为例，从L11所处的S2中所述一级索引缓冲区中搜索其他几何对象，从搜索结果中的第一个几何对象开始，判断构成该几何对象的第一个点Pto1(xto1，
yto1)到构成该几何对象的第二个点Pto2(xto2，yto2)是否在步骤S3中所述矩形范围内，如果在
矩形范围内，则确定该两点构成线段为待分析线段lto1。

[0102] 从衍生平行线段集合Q1中，遍历所有线段，挑选其中一条，视为参照线段lref1，同时根据形成参照线段lref1的两点坐标Pref1(xref1，yref1)，Pref2(xref2，yref2)确定线段lref1所在直
线方程：

[0103] y‑k1x‑b1＝0

[0104] 其中：

[0105]

[0106]

[0107] 计算yto1‑k1xto1‑b1，yto2‑k1xto2‑b1

[0108] 计算待分析线段lto1与参照线段lref1的夹角θ1

[0109] 计算待分析线段lto1的两个端点到参照线段lref1的距离d1，d2

[0110] 当(yto1‑k1xto1‑b1)*(yto2‑k1xto2‑b1)＞0；此规则用于确定两线段不相交。

[0111] 且θ1＜θset，此规则为挑选出与待分析线段夹角小于设定阈值θset的参照线段。

[0112] 且Bmin＜d1＜Bmax，Bmin＜d2＜Bmax，此规则为控制待分析线段lto1两端到参照线段lref1的距离处于合适范围，距离过小可能为同一直线或者错误的线，距离过大则可能会对
同一参考线重复判断。

[0113] 如满足以上三个条件，则可确定待分析线段lto1在S3所述所述矩形范围内存在平行线段，如存在，(回顾前文设定：待分析线段lto1两端点Pto1(xto1，yto1)、 Pto2(xto2，yto2)，主
线段L11方程y‑Kmnx‑Bmn＝0)

[0114] 计算yto1‑K11xto1‑B11，yto2‑K11xto2‑B11，若yto1‑K11xto1‑B11＞0，且yto2‑K11xto2‑B11＞0，判定该待分析线段相对位置判定标记为“above”；该相对位置判定标记无特殊含义，可任意
指定。

[0115] 若yto1‑K11xto1‑B11＜0，且yto2‑K11xto2‑B11＜0，判定该待分析线段相对位置判定标记为“below”；该相对位置判定标记标记无特殊含义，可任意指定。

[0116] 输出待分析线段lto1信息，包括几何类型标号，起始点编号，相对位置判定标记，连通编号(起始为空值)结果。将该信息加入衍生平行线段集合Q1中，与主线L11对应。

[0117] 不断在步骤S2构建的一级索引网格和一级索引缓冲区范围内继续搜索其他索引线段，重新挑选待分析线段，进行上述判断。直至所有一级搜索区搜索完毕，输出衍生平行
线段集合Q1。则衍生平行线段Q1为主线段与主线段的衍生平行线段的集合。重新挑选主线段
进行上述操作，直至所有主线段操作完毕。具体流程见图3.

[0118] 建立大集合Q，其中大集合Q由衍生平行线段集合Qi构成，衍生平行线段集合Qi表示每个主线段对应的二级搜索矩形内内主线段与平行线段集。

[0119] 衍生平行线段集合Qi结构：

[0120] (主线段信息，平行线段1信息，平行线段2信息……)

[0121] 主线段信息包括几何类型编号，起始点编号，主线段延伸方向，连通编号(起始为空值)

[0122] 平行线段信息几何类型编号，起始点编号，相对位置判定标记，连通编号(起始为空值)。

[0123] 某个衍生平行线段集合Qi的具体输出结果见图5。

[0124] S5、从大集合Q中获取一条线段，遍历其他线段并挑选出一条，对这两条线段的角度和距离进行判断，识别这两条线段是否属于同一路段，若是，则给这两条线段添加同样的
连通属性值，直至所有属于同一路段的线段连通属性值添加结束。

[0125] 将衍生平行线段集合Qi内的任一线段作为待判断线段，遍历同一集合内的其他线段并从中选取一条线段作为选取线段，计算：

[0126] 待判断线段的第一个点与选取线段的第一个点的距离；

[0127] 待判断线段的第一个点与选取线段的第二个点的距离；

[0128] 待判断线段的第二个点与选取线段的第一个点的距离；

[0129] 待判断线段的第二个点与选取线段的第二个点的距离；

[0130] 若上述四个距离中最小值小于预设阈值dset，

[0131] 最小值为待判断线段的第一个点与选取线段的第一个点的距离：标记待判断线段的第一个点为“起点”，选取线段的第一个点为“起点”；

[0132] 最小值为待判断线段的第一个点与选取线段的第二个点的距离：标记待判断线段的第一个点为“起点”，选取线段的第一个点为“终点”；

[0133] 最小值为待判断线段的第二个点与选取线段的第一个点的距离：标记待判断线段的第一个点为“终点”，选取线段的第一个点为“起点”；

[0134] 最小值为待判断线段的第二个点与选取线段的第二个点的距离：标记待判断线段的第一个点为“终点”，选取线段的第一个点为“终点”；

[0135] 若待判断线段的第一个点为起点，以起点为计算起点，在待判断线段所在的几何对象上，顺序后推预设的计算点个数Npoint为计算终点，当相邻两点的距离大于设定阈值时，
计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值。

[0136] 若待判断线段的第一个点为终点，以终点为计算起点，在待判断线段所在的几何对象上，逆序前推预设的计算点个数Npoint为计算终点，当相邻两点的距离大于设定阈值时，
计算从计算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值。

[0137] 若选取线段的第一个点为起点，以起点为计算起点，在选取线段所在的几何对象上，顺序后推预设的计算点个数为计算终点，当相邻两点的距离大于设定阈值时，计算从计
算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

[0138] 若选取线段的第一个点为终点，以终点为计算起点，在选取线段所在的几何对象上，逆序前推预设的计算点个数为计算终点，当相邻两点的距离大于设定阈值时，计算从计
算起点到计算终点之间相邻两线段的夹角，计算这些夹角的平均值；

[0139] 计算上述扩展后的待判断线段与扩展后的选取线段相邻两线段的夹角平均值之差并取绝对值：

[0140] 若该绝对值小于设定阈值angle_aveset，则判定待判断线段与选取线段属于同一路段，将待判断线段与选取线段的连通编号均设置为待判断线段的几何类型编号；

[0141] 若该绝对值大于设定阈值angle_aveset，则判定待判断线段与选取线段属于同一路段，将选取线段的连通编号设置为选取线段的几何类型编号。无法匹配的选取线段形成
新的对象在后面继续匹配。

[0142] 对衍生平行线段集合Q1除待判断线段外的其他线段重复上述判断，直至判断完毕。最终属于同一道路的线段连通编号均为同一值，将连通编号均为同一值的线段合并为
一条线段。继续对集合衍生平行线段Q2进行上述操作，直至所有几何操作完毕。不同的主线
段连通后就是路段。

[0143] 此时衍生平行线段集合Qi结构：

[0144] (主线段信息，平行线段1信息，平行线段2信息……)

[0145] 主线段信息包括几何类型编号，起始点编号，主线延伸方向，连通编号(非空)

[0146] 平行线段信息几何类型编号，起始点编号，相对位置判定，连通编号(非空)

[0147] 此时某个衍生平行线段集合Qi的具体输出结果见图6。

[0148] S6、从第一个衍生平行线段集合Q1开始，对后面的衍生平行线段集合Q2、 Q3…Qi进行判断，如延伸方向相同则执行集合合并操作，如延伸方向不同则停止当前合并操作并开
始新的合并操作，合并后的集合称为分段集合。

[0149] 根据步骤S3，同一个几何对象延伸方向总是分为连续的“positive”、“negative”…，因此对其进行顺序的正负段的平行线统计。

[0150] 在大集合Q中，从衍生平行线段集合Q1的主线段开始，若该主线段如步骤S3 所述延伸方向为“positive”，判断与集合Q1的主线段相连的主线段的延伸方向(实际上根据读
取规则，与衍生平行线段集合Q1中主线段相连的主线段为Q2的主线段)，若该主线段如步骤
S3中所述为“positive”，则将衍生平行线段集合Q1与Q2合并，继续对衍生平行线段集合Qi延
伸方向进行判断，如延伸方向相同则执行合并操作，如延伸方向不同则停止当前合并操作
并开始新的合并操作。

[0151] 若该主线段如步骤S3中所述为“negative”，判断与集合衍生平行线段Q1的主线段相连的主线段的延伸方向。若该主线段如S3中所述为“negative”，则将衍生平行线段集合
Q1与Q2合并，继续对集合Qi延伸方向进行判断，如延伸方向相同则执行合并操作，如延伸方
向不同则停止当前合并操作并开始新的合并操作。

[0152] 执行上述操作后，衍生平行线段集合Qi结构变为：

[0153] (主线段信息，平行线段1信息，平行线段2信息……)

[0154] 主线段不变或者增加，包括几何类型编号，连续的点编号，主线延伸方向，连通编号(非空)

[0155] 平行线段数不变或者增加，信息包括几何类型编号，起始点编号，相对位置判定，连通编号(非空)

[0156] 另外，计算衍生平行线段集合Qi主线段长度LSi，当LSi小于阈值Lset时，该几何对象长度太小，不对其进行方向分析；当LSi大于阈值Lset时，计算集合Qi中连通编号相同的平行
线段在各自对应主线上的投影距离Lpro_si，计算Lpro_si/LSi，若其小于设定的阈值Rset，则将该
连通编号的平行线段剔除出衍生平行线段集合Qi，可剔除平行路段在主线段上的投影距离
占主线段长度的比例较小的平行线段，实现平行路段优化。

[0157] 此时某个衍生平行线段集合Qi的具体输出结果见图7。

[0158] S7、根据分段集合内的主线段延伸方向、主线段与平行线段的相对位置结果统计次数，判断主线段的方向；若主线段的延伸方向为向上，统计分段集合内相对位置位于该主
线段上方和下方的平行线段的数量，若位于该主线段上方的平行线段多于位于该主线段下
方的平行线段，则该主线段的方向为“由东往西”，否则为“由北往南”；若主线段的延伸方向
为向下，统计分段集合内相对位置位于该主线段上方和下方的平行线段的数量，若位于该
主线段上方的平行线段多于位于该主线段下方的平行线段，则该主线段方向为“由西往
东”，否则为“由南往北”。

[0159] 根据步骤S3，对主线段的延伸方向添加了识别标志，因此，在本步骤中：

[0160] 若主线段为“positive”：

[0161] 统计分段集合内判定为相对位置为“below”的平行线段的连通编号，统计分段集合内判定为相对位置为“above”的平行线段的连通编号；

[0162] 若判定为相对位置判定标记为“above”的统计结果多于判定为相对位置判定标记为“below”的统计结果，主线段终点纬度坐标与起点纬度坐标的差值大于终点经度坐标与
起点经度坐标的差值，则该主线方向为“由东往西”，否则为“由北往南”；

[0163] 若主线段为“negative”：

[0164] 分段集合内判定为相对位置判定标记为“below”的结果多于判定为相对位置判定标记为“above”的结果，主线的终点纬度坐标与起点纬度坐标的差值大于终点经度坐标与
起点经度坐标的差值，则该主线方向为“由西往东”，否则为“由南往北”

[0165] 最终某个地区的矢量路网识别效果见图8。

[0166] 本发明还提供了一种基于衍生平行线段的大规模路网方向判定系统，包括：

[0167] 数据读取模块，用于读取矢量路网文件中的几何对象信息以及构成几何对象的要素信息，几何对象信息包括编号、类型，构成几何对象的要素信息包括点编号、点经纬度坐
标；

[0168] 一级索引网格构造模块，用于根据路网数据经纬度范围，将路网平面划分为不同的网格，将构成每一个几何对象的相邻两点所构成的线段称为索引线段，识别该索引线段
所处的网格，将该线段的索引存储至该网格，形成的网格称为构建一级索引网格；

[0169] 一级索引缓冲区构造模块，一级索引缓冲区构造模块用于在一级索引网格四周添加添加缓冲区域，构建一级索引缓冲区；

[0170] 二级索引矩形构造模块，用于从一级索引网格构造模块存储的索引线段中任意获取一条线段，称为主线段，构建以主线段的中点为中心对称点的矩形区域，称为二级索引矩
形；

[0171] 平行线段集合构造模块，用于建立大集合Q，其中大集合Q由衍生平行线段集合Qi构成，衍生平行线段集合Qi表示第i条主线段对应的二级索引矩形内该主线段和与其平行
的索引线段集，将与主线段平行的索引线段称为平行线段；本发明的平行线段集合构造模
块在一级索引网格和一级索引缓冲区中搜索主线段的平行线段，构建衍生平行线段集合；

[0172] 平行线段连通模块，用于对每一个大集合Q内的任意两条线段的角度和距离的判断，判定这两条线段是否属于同一路段，若是，则给这两条线段添加同样的连通属性值，直
至所有属于同一路段的线段连通属性值添加结束；

[0173] 平行路段优化模块，用于剔除平行路段在主线段上的投影距离占主线段长度的比例较小的平行线段；

[0174] 分段集合构造模块，用于从第一个衍生平行线段集合Q1开始，对后面的衍生平行线段集合Q2、Q3…Qi进行判断，如延伸方向相同则执行集合合并操作，如延伸方向不同则停
止当前合并操作并开始新的合并操作，合并后的集合称为分段集合；

[0175] 平行路段方向判断模块，用于根据分段集合内的主线段延伸方向、主线段与平行线段的相对位置结果统计次数，判断主线段的方向。

[0176] 综上，本发明实施例提供一种基于衍生平行线段的大规模路网方向判定方法，根据路网数据经纬度范围，将路网平面划分为不同的网格，将路网内各几何对象相邻两点形
成的索引线段存储至各网格，构建一级索引网格，根据每一条索引线段构建二级索引矩形，
对于每条索引线段，在一级索引网格中遍历查找位于二级索引矩形范围内且满足衍生平行
条件的其他索引线段，并判断其相对位置，从而构建了由索引线段以及该线段所关联的平
行线段组成的衍生平行集合，每条路段将生成多个衍生平行集合，然后进行路段的连通关
系检查，最终根据平行线段相对位置出现的次数以及索引线段经纬度坐标确定路段方向，
可提升大规模路网方向判定的效率和准确性。另外，本发明还提供了一种效率和准确性高
的基于衍生平行线段的大规模路网方向判定系统。

[0177] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和替换，这些改进和替换
也应视为本发明的保护范围。