无人机激光点云矿区土方量计算系统的设计与开发

柳克松

（中煤科工集团沈阳设计研究院有限公司，辽宁 沈阳 110000）

使用无人机获取激光点云数据，利用开发的软件处理点云数据同时需要应用数据库技术，以VS 2019为开发平台，通过C++语言，根据软件开发设计流程做出了一个基于DTM（Digital Terrain Model）的土方量计算系统，为生产管理提供了一种有效的技术手段。在研究传统逐点插入法的基础上，提出了一种基于红黑二叉树索引的改进算法，主要包括点和线的快速定位查找等功能并将其应用于DTM 的建立。分析了传统工程土方量计算方法的优缺点，获得了一种能够快速计算土方量的设计方案，这种方案的基础是建立DTM。研究结果表明，相较于传统的断面法与方格网法，此方法具有刻画地形图整体面貌与局部细节特征更加准确、作业方法效率高、计算结果精度高等优点。其技术路线如图1 所示。

图1 技术路线

1 系统设计与土方量计算

1.1 系统设计

在当前的系统中，创建了格网模型和不规则三角网模型并根据设计网格、特征点展点图以及测区边界等，运行土方量计算程序，将某个区域中的挖方及填方量算出来，同时还可根据土方量填挖平衡的相关原则计算区域内设计的平整高程，同时生成土方计算数据文件、指定范围总面积及挖方面积的土方量和填方面积土方量。

为了实现既定的系统功能，本软件设计了DTM 生成边界模块和土方量计算模块，而且基于2 个主模块将一些更加具体的算法集中应用到系统中，由此达到了设计目标。系统从数据输入、计算处理到结果输出，结构清晰、功能完善。

遍历顺序是将三角形的数据读取后，对三角形的每个顶点进行遍历，目的是确定目前的顶点是否在红黑二叉树中，如果不在树中，那么就将此顶点按照红黑二叉树的规则加入到二叉树中，并按照自然数的顺序为遍历的每个顶点排序，选择红黑二叉树的原因为红黑二叉树在存储数据时不会出现重复。例如存入第一个三角形后，再存入第二个三角形时，第二个三角形中有2 个点是第一个三角形中的，这时二叉树会放弃这2 个点，因此，原本需要存入6 个点，这时只需要存入4 个点就可以将三角形的数据结构存储下来，大大减少了内存空间，加快了计算速度。

为了把边界提取出来，需要DTM 三角网中每个点的坐标，每个三角形和其周边三角形的序号，将三角形中每条边序号、三角形序号及与这条边相邻的三角形序号作为一组数据进行临时保存。因此根据这个要求，首先建立指针类型数据结构Pointlist 用来存平面坐标（x，y），指针类型数据结构Pointattributrlist 用来存高程（z），指针类型数据结构Trianglelist 用来存三角形的3 个顶点（由点在红黑二叉树中的序号组成），最后指针类型数据结构neighborlist 用来存三角形每条边的信息（由三角形顶点构成，序号小的在前）。接下来再次对DTM 模型中所有三角形进行遍历，将每个三角形的顶点在红黑二叉树中进行遍历，将遍历得到的结果作为将要存入数据结构中的位置，分别将平面坐标、高程、顶点信息存储到不同的数据结构中。

将三角形顶点两两组成一条边，对每条边进行遍历，查找所在边的左右三角形序号，并将边及左右三角形序号存放在之前创建的map 数据结构中。这步是将每2 个点之间组成一条边，遍历每条边是否在map中，其中map 中前一个要素edge 由边构成，后一要素是把这条边的左右邻居存入进去，如果这条边的左边没有邻居就用﹣1 来表示。这条边的右边代表当前三角形序号。将当前三角形的序号存放进去，这一步骤目的是将这条边的信息及它的左右邻居进行存储。

对存入的边进行遍历，寻找除对应边所在顶点外另一顶点的序号，并将边及顶点序号存放在最开始定义的数据结构中。

1.2 土方量计算

在构造不规则三角形格网时需要结合实际地形地貌，此外，TIN（不规则三角形格网）的每个基本单元都是不规则三角形的一个顶点坐标[1-3]。由于采样时选取的观测点是由地形决定的，一般为地形坡度的变换点或平面地形的转折点，从而使得离散点在区域中呈非规则非均匀分布。正因此，使用这种方法所构建出的三角形格网肯定是不规则的，只有通过准确计算才能够最终确定内部不规则三角形的格网数目。依据几何学，假设一个区域内有n个离散点，那么它们可构成的互不交叉的三角形的数目最多不超过2n－5 个。在生成TIN 的过程中，还要考虑地性线、地物等的影响。为了保证格网最大限度符合实际地形，在应用中通常把地形特征线作为TIN 中三角形的边，并在扩展TIN 时，先从地形特征线开始。因此大比例尺数字测图的建模中大都采用三角形格网法，它避免了为内插方格网而牺牲原始测点精度的问题，从而保证了整个模型的精度[4]。

在利用不规则三角形模型进行土地均衡平整及土方量计算时，要依据圈定边界区域内的离散点建立出带约束的不规则的三角网（TIN），这样能够对地形进行更好的反映；另一方面当地形出现变化时也可以第一时间进行描述，以此提高所测土方量的精度。

以下是常见的不规则三角形构建方法：约束图法、分割-合并算法、加密算法、Shell 三角化算法、两步法及某些算法的合成算法。此次研究所使用的方法为两步法，首先用凸包算法快速计算出无约束条件的不规则三角形的各个顶点坐标，然后逐渐向DTM 中添加约束线，构建起约束三角网。使用该方法时必须保证所有的约束线的节点都在离散数据的初始三角网部分，然后根据约束线与离散点之间的拓扑关系将约束线逐条嵌入初始三角网中。

本系统以VS 2019 为平台，并利用C++语言来进行开发，这样就可以在离散点数据的基础上，利用内插法获得相关的不规则三角网数据，从而建立不规则三角网（ TIN ）模型。最终利用设计标高来确定挖方量、填方量及平整区域的土方量，完成给定区域的土地均衡平整和土方量计算。

输入模型为设计地面的DTM 模型和原地面的DTM 模型步骤如下：①对原地面的DTM 模型中每个三角形进行搜索，寻找与三角形相交的设计地面DTM模型中所有三角形外接矩形，计算相交面积。②当2个DTM 模型相交图形为三角形时，将设计地面DTM模型中相交三角形投影到原地面DTM 模型中；当2个DTM 模型相交图形为多边形时，将其分割为多个三角形，再进行投影。③投影后的三角形平面坐标不变，高程由原来的设计地面高程改为原地面高程，2 个模型可以形成平面坐标相同、高程不同的立方体，达到计算填挖方体积的目的。

设计地面的DTM 模型和参考高程土方量计算与输入模型为设计地面的DTM 模型和原地面的DTM 模型相比，步骤①和步骤②相同，步骤③中投影后的三角形平面坐标不变，高程由原来的设计地面高程改为输入的参考高程，最后进行计算。

2 工程案例

工程区地形以剥蚀低山丘陵地貌为主，穿插丘间沟谷地、丘间谷盆地，地形总体起伏较大，山势陡峻，主山脉走向呈北东东向，但其山麓山坡中山脊走向呈南北向或北北西向，波状起伏较大，地面标高在160～385 m 之间：而丘间沟谷地、丘间谷盆地地形多呈“U”字形，狭长条带状，沟谷走向与主体山脊直垂直，呈近南北向，地表发育浅表性软土，地面高程随相应的低丘山麓山坡标高变化相差较大。

将数据导入本文研发系统中按照步骤进行计算，该系统操作结果如图2—图5 所示。

图2 导入数据

图5 最终生成DTM

图3 打开文件

图4 计算窗口

3 总结

在本软件开发过程中，主要应用数字建模技术、数据库技术、系统工程理论及计算机图形学等新技术进行研究。为了克服传统逐点插入法所存在的问题，基于原有成果，依据红黑二叉树法给出了一种基于网格索引的可快速定位插入点并确定影响域的改进算法设计。对于地测系统来说，验收是其主要功能，其中包括填挖方的验收，此外还有露天采场的验收及掘进工程的验收等，这些都需进行土方工程量的计算。在总结传统工程土方量计算方法的基础上，给出了基于DTM 的工程土方量计算方法设计，该方法主要包括生成边界与计算土方量。由于三角网的点的检索比矩形格网的检索具有更高的复杂性，为了使效率得到进一步提升，提出了以网格作为其基础的点的快速搜索算法，同时给出了相应的计算算法；在研究已有生成边界的基础上，给出了一种新算法，它使交点计算法得到显著的简化，进而使效率得到显著提高，而且，它无需对一些特殊情况进行专门处理。其开发平台为Visual Studio 2019，并嵌套C++编程语言，严格按照软件工程技术进行了开发，最终开发出此系统用于计算工程土方量。