基于GPS数据的露天矿山道路网自动构建方法及系统

摘要

本发明提供了一种基于GPS数据的露天矿山道路网自动构建方法及系统，所述方法包括S1.根据预先采集的露天矿山道路网的GPS点数据，使用散点Delaunay三角化算法，构建GPS点数据的初始三角网；S2.对初始三角网进行过滤，得到道路三角网；S3.提取道路三角网的开口线，构建道路双线网，形成道路多连通域；S4.使用多连通域三角化算法，构建道路多连通域三角网；S5.遍历道路多连通域三角网中的三角形，提取出各三角形的特征点；S6.根据道路多连通域三角网中各三角形与相邻的三角形的关系连接特征点，形成露天矿山道路拓扑网络。本发明能够实现露天矿山道路网的自动构建。

说明书

技术领域

本发明涉及露天矿山道路构建领域，具体涉及一种基于GPS数据 的露天矿山道路网自动构建方法及系统。

背景技术

露天矿山道路网是一种真实反映露天矿山道路地理位置信息及道 路间拓扑关系的路网，是露天矿山卡车调度系统及矿山设备运营监控 管理的基础。随着信息化智能化在矿山中的应用和发展，对露天矿山 道路网自动构建和快速更新的需求日益迫切，现有露天矿山道路网构 建技术存在诸如自动化程度低、周期长、成本高和精度差等问题，从 而导致露天道路网构建跟不上实际发展变化的窘境。

现有的道路网构建方法主要分为两类：一类是传统的测绘方法， 存在着自动化程度低、周期长、成本高等缺陷，同时由于矿山开采的 不断推进，矿山道路网变动频繁且无规律可循，导致该类方法无法有 效用于露天矿山实际生产应用；另一类是基于GPS数据采集的路网构 建方法，许多研究学者在GPS数据的基础上研究了城市道路网的自动 构建方法，且取得了一定的成果，但尚且无人研究针对露天矿山道路 网的自动构建。

史文欢提出一种基于GPS定位的道路网络栅格数字地图自动生成 方法，该方法生成的是一种栅格数字地图，缺乏道路网拓扑关系信息， 无法满足露天矿山卡车调度的需求；张健钦提出的一种基于公交GPS 轨迹数据的路况信息生成方法及孙棣华提出的一种利用城市浮动车辆 GPS数据生成道路路网矢量地图方法，此类方法均只适用于城市道路 网的自动构建，方法中或者以公交站点作为参考，或者以城市道路线 路较为固定作为前提，无法应用于露天矿山道路网的复杂情况；史文 中提出一种基于机载LIDAR和GIS协同的三维道路生成方法，该方法 主要研究道路点云裁切、高架桥道路自动分层和高程内插等，露天矿 山道路均不存在上述问题，故该方法也无法适用。

针对上述现象，亟需一种快速准确的自动构网方法，解决基于GPS 数据的露天矿山道路网自动构建问题。

发明内容

针对现有技术中的缺陷，本发明提供一种基于GPS数据的露天矿山 道路网自动构建方法及系统，能够实现露天矿山道路网的自动和准确 构建。

为解决上述技术问题，本发明提供以下技术方案：

第一方面，本发明提供一种基于GPS数据的露天矿山道路网自动 构建方法，包括：

S1.根据预先采集的露天矿山道路网的GPS点数据，使用散点 Delaunay三角化算法，构建GPS点数据的初始三角网；

S2.对初始三角网进行过滤，得到道路三角网；

S3.提取道路三角网的开口线，构建道路双线网，形成一个道路多 连通域；

S4.使用多连通域三角化算法，构建道路多连通域三角网；

S5.遍历道路多连通域三角网中的三角形，提取出各三角形的特征 点；

S6.根据道路多连通域三角网中各三角形与相邻的三角形的关系 连接特征点，形成露天矿山道路拓扑网络，完成露天矿山道路网的自 动构建。

进一步地，所述步骤S2对初始三角网进行过滤，得到道路三角网， 包括：

遍历初始三角网中的所有三角形，去除面积大于阈值S_max的三角 形；

遍历剩余的三角形，去除周长大于阈值L_max且最小内角小于阈值 A_min的三角形，得到道路三角网。

进一步地，所述步骤S3提取道路三角网的开口线包括：

遍历道路三角网的所有三角形，将各三角形的三条边中不与其它 任何三角形相邻的边提取出来，实现道路三角网开口线的提取。

进一步地，所述步骤S4使用多连通域三角化算法，构建道路多连 通域三角网，包括：

利用多连通域中的多边形的顶点和边的拓扑关系构建三角形，形 成多连通域的三角网。

进一步地，所述步骤S5遍历道路多连通域三角网中的三角形，分 别提取出各三角形的特征点，包括：

根据Pt(x,y)＝(x1+x2+x3*2,y1+y2+y3*2)/4提取出各三角形的特征 点；

其中，Pt(x,y)是三角形的特征点，(x3,y3)是三角形最小内角对应的 点，(x1,y1)和(x2,y2)是三角形的另外两点。

进一步地，所述步骤S6根据道路多连通域三角网中各三角形与相 邻的三角形的关系连接特征点，形成露天矿山道路拓扑网络，完成露 天矿山道路网的自动构建，包括：

判断多连通域三角网中的各三角形与其相邻的其他三角形之间的 关系；

若三角形的三条边均与其它三个三角形相邻，则该三角形为种子 三角形，根据种子三角形及其相邻的三个三角形的关系连接特征点形 成岔路；其中，道路在种子三角形处出现分叉；

若三角形有且仅有两条边与其它两个三角形相邻，则该三角形为 常规三角形，根据常规三角形及其相邻的两个三角形的关系连接特征 点形成道路直线段；其中，道路在常规三角形处为直线段；

若三角形有且仅有一条边与其它一个三角形相邻，则该三角形为 边界三角形，根据边界三角形及其相邻的一个三角形的关系连接特征 点形成道路的终点；其中，道路在边界三角形处出现终止。

第二方面，本发明还提供了一种基于GPS数据的露天矿山道路网 自动构建系统，包括：

第一构建单元，用于根据预先采集的露天矿山道路网的GPS点数 据，使用散点Delaunay三角化算法，构建GPS点数据的初始三角网；

过滤单元，用于对初始三角网进行过滤，得到道路三角网；

第二构建单元，用于提取道路三角网的开口线，构建道路双线网， 形成一个道路多连通域；

第三构建单元，用于使用多连通域三角化算法，构建道路多连通 域三角网；

特征点提取单元，用于遍历道路多连通域三角网中的三角形，提 取出各三角形的特征点；

第四构建单元，用于根据道路多连通域三角网中各三角形与相邻 的三角形的关系连接特征点，形成露天矿山道路拓扑网络，完成露天 矿山道路网的自动构建。

进一步地，所述过滤单元用于遍历初始三角网中的所有三角形， 去除面积大于阈值S_max的三角形；所述过滤单元还用于遍历剩余的三 角形，去除周长大于阈值L_max且最小内角小于阈值A_min的三角形，得 到道路三角网。

进一步地，所述第二构建单元用于遍历道路三角网的所有三角形， 将各三角形的三条边中不与其它任何三角形相邻的边提取出来，实现 道路三角网开口线的提取。

进一步地，所述第四构建单元，包括判断模块、标记模块和执行 模块；

所述判断模块，用于判断多连通域三角网中的各三角形与其相邻 的其他三角形之间的关系；

所述标记模块，用于在所述判断模块确定某三角形的三条边均与 其它三个三角形相邻时，标记该三角形为种子三角形；

所述标记模块，用于在所述判断模块确定某三角形有且仅有两条 边与其它两个三角形相邻时，标记该三角形为常规三角形；

所述标记模块，用于在所述判断模块确定某三角形有且仅有一条 边与其它一个三角形相邻时，标记该三角形为边界三角形；

所述执行模块，用于根据种子三角形及其相邻的三个三角形的关 系连接特征点形成岔路；其中，道路在种子三角形处出现分叉；

所述执行模块，用于根据常规三角形及其相邻的两个三角形的关 系连接特征点形成道路直线段；其中，道路在常规三角形处为直线段；

所述执行模块，用于根据边界三角形及其相邻的一个三角形的关 系连接特征点形成道路的终点；其中，道路在边界三角形处出现终止。

由上述技术方案可知，本发明所述的基于GPS数据的露天矿山道 路网自动构建方法，解决了露天矿山道路网无法准确构建的技术难题， 实现了露天矿山道路网的自动和准确构建。露天矿山作业人员在进入 露天矿山开采时，可以参考构建好的露天矿山道路网，从而有效保证 了作用人员的安全。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面 将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而 易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通 技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图 获得其他的附图。

图1示出了本发明实施例一提供的基于GPS数据的露天矿山道路 网自动构建方法的流程图；

图2示出了一个露天矿山中使用车载GPS系统采集的矿山道路上 GPS点数据的示意图；

图3示出了使用散点Delaunay三角化算法得到的由GPS点数据构 建的初始三角网示意图；

图4示出了对初始三角网进行过滤，去除道路外三角形后得到的 道路三角网示意图；

图5示出了提取道路三角网的开口线，构建道路双线网，即形成 的一个多连通域的示意图；

图6示出了使用多连通域三角化算法得到的道路多连通域三角网 的示意图；

图7示出了遍历道路多连通域三角网中的三角形，提取三角网中 各三角形的特征点的示意图；

图8及图8a-图8c分别示出了在道路分叉处、在道路直线处、在 道路复杂路段处的处理示意图；

其中，图8a、图8b和图8c分别示出了图8中a、b、c处的细节 放大图；图8a表示在道路分叉处，根据种子三角形及其相邻的三个三 角形的关系连接特征点形成的岔路示意图；图8b表示在道路直线处， 根据三角形及其相邻的两个三角形的关系连接特征点形成的直线道路 示意图；图8c表示在道路复杂路段，将其分解为若干个分岔路口处理 的示意图；

图9示出了根据道路多连通域三角网相邻关系连接特征点，形成 的露天道路网示意图；

图10示出了本发明实施例二提供的基于GPS数据的露天矿山道 路网自动构建系统的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结 合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、 完整的描述，显然，所描述的实施例是本发明一部分实施例，而不是 全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有 作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护 的范围。

图1示出了本发明实施例一提供的基于GPS数据的露天矿山道路 网自动构建方法的流程图，参见图1，本发明实施例提供的基于GPS 数据的露天矿山道路网自动构建方法包括：

步骤101：根据预先采集的露天矿山道路网的GPS点数据，使用 散点Delaunay三角化算法，构建GPS点数据的初始三角网。

在本步骤中，所述GPS点数据是指通过车载GPS系统采集的卡车 位置坐标信息，如图2所示，若干安装GPS系统的卡车在露天矿山道 路上运行，实时的采集各卡车当前的坐标位置信息，从而构成了本实 施例的数据基础GPS点数据。

所述散点Delaunay三角化算法是一种对散点进行三角剖分形成三 角网的方法，使用Delaunay三角化算法形成的三角网具有以下两个重 要特性：

a.空圆特性：任一三角形的外接圆范围内不会存在有其它点；

b.最小内角最大化特性：任意两个相邻的三角形构成凸四边形的 对角线，在相互交换后，六个内角的最小角不再增大，如图3所示。

步骤102：对初始三角网进行过滤，得到道路三角网。

在本步骤中，对初始三角网进行过滤，去除道路外的三角形，得 到道路三角网，如图4所示。

根据GPS点数据在露天道路上较为密集、在道路外较为稀疏这一 空间分布特点，其生成的初始三角网也具有一定的特点，即道路上的 三角形大多是边长较短、面积较小且最小内角较大的近正三角形，而 道路外的三角形边长较长、面积较大且容易产生最小内角较小的奇异 三角形。因此，根据初始三角网的特点，通过以下步骤可去除掉道路 外的三角形，得到道路三角网：

A1：遍历初始三角网中的所有三角形，去除掉面积大于阈值S_max的三角形，主要作用是空旷区域三角形的初次过滤，本实施例中阈值 S_max取值为120m²；

A2：遍历剩余的三角形，去除掉周长大于阈值L_max，且最小内角 小于阈值A_min的三角形，主要作用是道路交叉处干扰三角形的精细过 滤，本实施例中阈值L_max和A_min分别取值为15m和15°；

A3：判断遍历是否结束，若是，则完成初始三角网的过滤，得到 道路三角网；若否，则继续执行步骤A1和步骤A2。

步骤103：提取道路三角网的开口线，构建道路双线网，形成一个 道路多连通域。

在本步骤中，如图5所示，所述提取道路三角网的开口线，是指 遍历道路三角网的所有三角形，将各三角形的三条边中不与其它任何 三角形相邻的边提取出来，从而实现道路三角网开口线的提取。

在本步骤中，所述道路多连通域是指多边形区域内存在洞、岛等 情形，从而体现了露天道路网存在分叉和附和等情形。

步骤104：使用多连通域三角化算法，构建道路多连通域三角网。

在本步骤中，如图6所示，所述多连通域三角化算法是指充分利 用多连通域中的多边形的顶点和边的拓扑关系构建三角形，形成多连 通域的三角网。

步骤105：遍历道路多连通域三角网中的三角形，提取出各三角形 的特征点。

在本步骤中，如图7所示，根据GPS点及多连通域的特点，其生 成的多连通域三角网上的三角形均为奇异三角形，即三角形的最小内 角较小，且最小内角所对应的边均落在道路双线网上，故本实施例中 三角形的特征点求解方法为：

根据Pt(x,y)＝(x1+x2+x3*2,y1+y2+y3*2)/4提取出各三角形的特征 点；

其中，Pt(x,y)是三角形的特征点，(x3,y3)是三角形最小内角对应的 点，(x1,y1)和(x2,y2)是三角形的另外两点。

步骤106：根据道路多连通域三角网中各三角形与相邻的三角形的 关系连接特征点，形成露天矿山道路拓扑网络，完成露天矿山道路网 的自动构建。

在本步骤中，判断多连通域三角网中的各三角形与其相邻的其他 三角形之间的关系；

若三角形的三条边均与其它三个三角形相邻，则该三角形为种子 三角形，根据种子三角形及其相邻的三个三角形的关系连接特征点形 成岔路；其中，道路在种子三角形处出现分叉。如图8及图8a、图8c。 所示其中，图8a表示在道路分叉处，根据种子三角形及其相邻的三个 三角形的关系连接特征点形成的岔路示意图；图8c表示在道路复杂路 段，将其分解为若干个分岔路口处理的示意图。

若三角形有且仅有两条边与其它两个三角形相邻，则该三角形为 常规三角形，根据常规三角形及其相邻的两个三角形的关系连接特征 点形成道路直线段；其中，道路在常规三角形处为直线段如图8及图 8b所示。图8b表示在道路直线处，根据三角形及其相邻的两个三角形 的关系连接特征点形成的直线道路示意图；

若三角形有且仅有一条边与其它一个三角形相邻，则该三角形为 边界三角形，根据边界三角形及其相邻的一个三角形的关系连接特征 点形成道路的终点；其中，道路在边界三角形处出现终止。

本步骤106执行完后形成了露天矿山道路拓扑网络，完成了露天 矿山道路网的自动构建，最终结果如图9所示。

本发明实施例提供的基于GPS数据的露天矿山道路网自动构建方 法，解决了露天矿山道路网无法准确构建的技术难题，实现了露天矿 山道路网的自动和准确构建。露天矿山作业人员在进入露天矿山开采 时，可以参考构建好的露天矿山道路网，从而有效保证了作用人员的 安全。

图10示出了本发明实施例二提供的基于GPS数据的露天矿山道路 网自动构建系统的结构示意图，参见图10，本发明实施例二提供的基 于GPS数据的露天矿山道路网自动构建系统包括：

第一构建单元100，用于根据预先采集的露天矿山道路网的GPS 点数据，使用散点Delaunay三角化算法，构建GPS点数据的初始三角 网；

过滤单元200，用于对初始三角网进行过滤，得到道路三角网；

第二构建单元300，用于提取道路三角网的开口线，构建道路双线 网，形成一个道路多连通域；

第三构建单元400，用于使用多连通域三角化算法，构建道路多连 通域三角网；

特征点提取单元500，用于遍历道路多连通域三角网中的三角形， 提取出各三角形的特征点；

第四构建单元600，用于根据道路多连通域三角网中各三角形与相 邻的三角形的关系连接特征点，形成露天矿山道路拓扑网络，完成露 天矿山道路网的自动构建。

优选地，所述过滤单元200用于遍历初始三角网中的所有三角形， 去除面积大于阈值S_max的三角形；所述过滤单元还用于遍历剩余的三 角形，去除周长大于阈值L_max且最小内角小于阈值A_min的三角形，得 到道路三角网。

优选地，所述第二构建单元300用于遍历道路三角网的所有三角 形，将各三角形的三条边中不与其它任何三角形相邻的边提取出来， 实现道路三角网开口线的提取。

优选地，所述第四构建单元600，包括判断模块601、标记模块602 和执行模块603；

所述判断模块601，用于判断多连通域三角网中的各三角形与其相 邻的其他三角形之间的关系；

所述标记模块602，用于在所述判断模块确定某三角形的三条边均 与其它三个三角形相邻时，标记该三角形为种子三角形；

所述标记模块602，用于在所述判断模块确定某三角形有且仅有两 条边与其它两个三角形相邻时，标记该三角形为常规三角形；

所述标记模块602，用于在所述判断模块确定某三角形有且仅有一 条边与其它一个三角形相邻时，标记该三角形为边界三角形；

所述执行模块603，用于根据种子三角形及其相邻的三个三角形的 关系连接特征点形成岔路；其中，道路在种子三角形处出现分叉；

所述执行模块603，用于根据常规三角形及其相邻的两个三角形的 关系连接特征点形成道路直线段；其中，道路在常规三角形处为直线 段；

所述执行模块603，用于根据边界三角形及其相邻的一个三角形的 关系连接特征点形成道路的终点；其中，道路在边界三角形处出现终 止

本实施例所提供的基于GPS数据的露天矿山道路网自动构建系 统，可以用于执行上述实施例一所述的方法，其工作原理和有益效果 和上述实施例一类似，此处不再赘述。

以上实施例仅用于说明本发明的技术方案，而非对其限制；尽管 参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员 应当理解：其依然可以对前述各实施例所记载的技术方案进行修改， 或者对其中部分技术特征进行等同替换；而这些修改或替换，并不使 相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。