巷道中线的计算机自动求解算法

摘 要 本文将巷道中线的确定看作是由点至线的求解问题，以矿井巷道的左帮距、右帮距等测量数据为依据，利用导线点与巷道壁之间的特殊位置关系，提出了一种新的基于坐标公式法易于在计算机上实现的巷中线求解算法，将人们从繁琐的绘图工作中解放了出来，具有很好的实用价值。

关键字：巷道中线；坐标公式法；左帮距；右帮距；比对

中图分类号 TP391.72 文献标识码 A

The automatic computer algorithm of the laneway center line

Bo Tang

(Computer Science of Technology,China University of Mining and Technology,Xxuzhou 221002，China)

【Abstract 】 This specification regarded the determination of the laneway center line as a problem of line-to-point, based on the data of distance to the left,taken advance of the special relationship between the location of tunnel wall and traverse points,proposing a new method based on the formula easy to confine the roadway center line algorithm on a computer, drawing people from the tedious work out of the liberation, having a better actual value.

【Key words】laneway centerline; coordinate formula method;distance to the left; distance to the right;compare

0 引 言

当前，尽管已经有人提出了多种巷道中线求解算法，如直接加减法、解三角形法、坐标公式法[1]等,但是这些方法大都仅考虑到了“直线型”巷道条件下的巷道中线求解问题。然而，实际生产中，我们遇到的往往是“折线型”巷道，因此并不具有实际应用价值。于是，当前的巷道中线的绘图基本上是手工完成的，虽然在绘图过程中可以借助于AutoCAD等计算机辅助绘图软件，但由于AutoCAD这类的辅助设计软件主要用于图形的二次开发，并不能实现人们巷道中线计算机自动生成的初衷。本文正是在这种现实背景下，提出了一种巷道中线计算机自动求解算法。本算法对通常的坐标公式法进行了改进，融入了数据结构化，功能模块化等思想，一方面有利于计算机的数据处理，提升求解效率，另一方面使得求解思路更加简洁明快，便于程序设计以至于在计算机上的实现。

*基金项目：中国矿业大学大学生实践创新训练计划项目

*Foundation Items: The Practice Inovation Trainng Program Projects of China University of Mining and Technology

1 算法用到的数据结构

有实际生产经验可知，通常在进行巷道中线绘制时，我们手中的第一手数据往往是一些和导线点有关的测量数据，这些数据通常会对导线点的地理位置坐标、左帮距、右帮距、环境状况、实际地貌等属性进行描述[2]。基于这些测量数据，为其建立相应的数据结构，对于每一个导线点，在它的数据结构中应包含节点的ID(ID)、节点的位置坐标x(worldx)、节点的位置坐标y(worldy)、指向下一边结点的指针(nextaRc)、环境信息描述(EnvirDes)、实际地貌描述(ActualFlag)，另外为了方便对折线型巷道折点出现的位置进行标识，还需要设置一个属性――折点标识(FoldPoint），节点数据结构如表1所示：

2 巷道中线求解算法描述

本算法基于坐标公式法，根据导线点与巷道壁之间的特殊位置关系，给出了一种新的求解巷道中线的算法。具体求解时，首先根据巷道靠近端点的两个导线点的坐标及其左、右帮距，算出巷道壁的直线方程，然后依据导线点编号顺次计算其至此求出的直线方程的距离，接着将此距离值与测量所得的左帮距进行比对，如果相等则说明巷道在此处尚未发生偏折，否则说明巷道在此处发生偏折，应重新计算巷道壁方程。这样重复前述各个步骤，巷道壁的直线方程便全部确定了，最后根据左、右帮距可以计算出各导线点所对应的巷道中点的坐标，顺次连接这些中点后，巷道中线就形成了。

下面我们以图1为例说明巷道中线的生成算法，假设图中A、B、C、D、E是属于同一巷道的导线点，且A、B、C、D、E的编号分别为XXXXXXX001、XXXXXXX002、XXXXXXX003、XXXXXXX004、XXXXXXX005，相应的导线点对为（A，B）、（B、C）、（C、D）、（D、E）。

步骤一：依据A、B确定巷道壁所在直线方程

导线点的左、右帮距给出了导线点到巷道两边的距离，由相邻导线点的坐标可以计算出相邻导线点间的距离，可以证明巷道壁其实就在分别以两相邻导线点为圆心，以左（右）帮据为半径的圆的公切线上。利用相关几何知识可以解出公切线的直线方程，即巷道壁所在直线方程。

因为导线点的坐标均可依据测量值转化得到，为简便起见，在下述计算过程中，均作为已知值。图2中，设A、B为导线点，C、D、E为做作辅助线时产生的辅助点；导线点A的坐标为（Ax, Ay）；导线点B的坐标为（Bx, By）；导线点A、B的左帮距离分别为lefta、leftb，导线点A、B的右帮距离分别为righta、rightb；

根据对称性原理可知，根据左帮距或右帮距计算所得的巷道中线是一致的。在接下来的阐述中，本文从左帮距出发，演示求解过程。如图2所示，以导线点A为圆心，以左帮距为半径作圆A,则在圆A的切线中必然有且仅有一条经过圆周B，即图中的直线L，直线L就是左侧巷道壁所在位置。

该直线L为巷道壁的具体证明过程如下：

如图2所示，点P为某一导线点，而直线L为巷道壁的左侧，过点P作一直线段垂直于L于点M，根据左帮距的定义知，线段PM即为左帮距，根据几何公理[4]：

公理1 经过直线外一点有且仅有一条直线与已知直线垂直。

公理2 直线外的一点到直线的距离垂线段最短。

可得：交点M有且仅有1个，于是左侧巷道壁上有且仅有一点在圆B上。

过圆周上任意一点做圆的切线得到L1，L2，….，Li，…，Ln，则这些切线中必然有一条代表着左侧巷道壁，该直线L应满足如下条件：过导线点B作垂线段垂直于L于点N，则NM的长度恰为导线点B的左帮距。

延长直线L、AB，相交于点C，下面我们将 单独拿出来求解 ，如图3所示，其中 ，AB=lefta，EB=leftb。

理论上，若此巷道壁至此导线点处仍是符合实际地貌的，即没有发生转弯，则delt=0。然而，考虑到实际测量肯定会有一些误差，因此我们给定一个误差允许范围 ，如果Delt

当枚举至E点时，E点到直线的距离与实际的左帮据差值超出了误差允许范围，即 ，则说明此巷道壁至此导线点处是不符合实际地貌的，也就是此处发生了转弯。这时发生转弯的第一个点即为我们需要标记的折线点，标记时只需将中点的折线点标识修改为True即可。

为方便说明，接下来将转弯处单独拿出来分析，如图5所示：

以点C为圆心，以左帮距为半径作圆。过点M作圆C的切线，这条切线即为左巷道壁转弯后的位置。

根据前述步骤一、二的计算过程，可以解得切线MN的直线方程，进而求得各导线点所对应的巷道中点。

将确定的中点的坐标存入中点数据结构中与之相对应的属性域中，并将导线点对按照逐一替换的方法修改为中点对，顺次连接便可以得到巷道中线了

3 算法关键函数的伪码实现

以下伪码主要实现巷道中线求解功能[5]

void CalMidNode(vector ¬evector, note &nt)

{

for(vector::size_type i=0;i!=notevector.size();i++)

{//以巷道为单位依次求解其内导线点对应的中点

CalLaneEquation(nt[i].current);

note *before=hd.first,*current=hd.first; //设两个指向导线点的指针，以方便找到这个集合的合适位置来加入新的点

for(int j=0;nt[i].ID!='NUll';j++)

{

Dis=CalDistinction(nt[i].ID);

if(abs(dis-nt.ID.left>misstatement)

{

CalLaneEquation(nt[i].current);

nt[i]. arcsign=1;

}

else cintinue;//修改相关指针

before.next=&nt;cu

nt.next=current;

before=current;

current=current.next;

}

}

}

4 结 论

本文在总结前人巷道中线求解算法的基础上，提出了一种基于坐标公式法以矿井巷道的左帮距、右帮距等测量数据为依据，利用导线点与巷道壁之间的特殊位置关系进行求解的的新的巷道中线求解算法。为了使该算法更具有使用价值，本文还给出了所用到的数据结构和伪码实现，为该算法在计算机中实现奠定了基础。相信本算法的应用将会为广大矿井巷道的绘图工作者减轻许多负担，并且对矿井巷道图的自动生成也打下了坚实的基础。

参考文献[参考资料]

[1] 刘焕星,庞尔雷,刘其虎,等.几种巷道中线执行的解算方法[J].山东煤炭科技, 2011(02):38-40.

[2] 汪云甲,郭达志,邓喀中,等.我国矿山测量学科的发展与创新[J].测绘通报,2005(02):1-6.

[3] 严蔚敏, 吴伟民.数据结构（c语言版）[M].北京: 清华大学出版社,1997:30-60

[4] 南开大学数学系.空间解析几何引论 [M] 北京:人民教育出版社,1979:40-50

[5] Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein. Introduction to Algorithms [M] The MIT Press, 2001:305-320.

5 作者简介与联系方式

作者简介: 唐波(1991－),男本科,学生,主要研究领域为无线传感网络