线状地理要素空间距离计算与算法优化

邓振民，田方方，杨翠媛

(1.山东中基地理信息科技有限公司，山东 济南 250101； 2.中国冶金地质总局山东正元地质勘查院，山东 济南 250101)

线状地理要素空间距离计算与算法优化

邓振民1，2*，田方方1，杨翠媛1

(1.山东中基地理信息科技有限公司，山东 济南 250101； 2.中国冶金地质总局山东正元地质勘查院，山东 济南 250101)

基于建立与优化线状地理要素空间最小距离计算模型的目的，采用映射线状地理要素地物到空间几何概念范畴的方法，通过分析空间范围内两要素间距离的三维关系，推导计算两要素间最小空间距离的数学模型，把模型作为基本单元向外扩展得到空间范围内地理要素间最小距离计算的数学算法，利用空间范围的划分与计算流程的优化得到性能改善的算法，以管线实例验证算法的有效性，得出算法可用于线状地理要素空间距离计算场景的结论。

线状地理要素；最小空间距离；空间范围划分；算法验证

1 引 言

线状地理要素是对客观世界中存在的线状实体、现象或关系的抽象概括，可用于空间客体的描述、分析、模拟、重现与表达等。空间距离是描述空间客体之间的相对位置、分布等情况的概念，反映空间相邻客体间的接近度和相似度等[1]。依据空间客体的形态，空间距离可表示“点/线/面/体”单地理要素的度量，还可表示“点群/线群/面群”多地理要素集的度量[2～4]，广义的空间距离还包括最近距离、最远距离、质心距离、Hausdorff距离、Fréchet距离等。线状地理要素的空间距离决定了空间客体的几何形状与位置关系，是GIS中制图表达与空间分析的目的与基石，线状地理要素间空间距离的有效计算直接影响GIS相关功能的正确性与效率。本文以空间异面直线距离计算的数学方法为基础，结合地下管线应用实例对线状地理要素间距计算算法进行研究，实现对线状空间地理要素间距计算算法的改进与优化。

2 空间距离定量描述

2.1 直线空间距离度量

直线空间距离按照不同的维度可以分为不同的类型，现实中常用的是二三维空间中的距离，如图1、图2所示：

图1 二维空间

图2 三维空间

典型的空间距离度量是Minkowski或lp-metrics(Preparata&Shamos1985)距离度量，描述如下：

设定Rm空间中的点pi(xi1，xi2，…，xim)和pj(xj1，xj2，…，xjm)，度量距离d的一般表述形式为：

(1)

其中m为点p的维度，

当p=1时，d1(pi，pj)即为曼哈顿距离：

(2)

当p=2时，d2(pi，pj)即为欧氏距离：

(3)

p→，d(pi，pj)即为Tchebycheff距离：

d(pi，pj)=max (|xi1-xj1|，|yi2-yj2|，…，|yim-yjm|)

(4)

以上是lp-metrics类中最为常见的三种距离，其中第三种d(pi，pj)可以看作栅格中一般计算距离的方法。

2.2 线状地理要素空间距离度量

假设空间中存在两条线段ab和cd，线段ab端点的坐标分别为a：(x1，y1，z1)，b：(x2，y2，z2)，线段cd端点的坐标分别为c：(x3，y3，z3)，d：(x4，y4，z4)。

(1)空间直线(线段)位置关系

①共面直线(线段)的几种位置关系(如图3所示)

②异面直线(线段)位置关系(如图4所示)

图3共面直线(线段)位置关系

图4 异面直线(线段)位置关系

(2)空间距离计算分析

①基本参数方程

设p是直线ab上的一点，p点的坐标(X，Y，Z)的参数方程可以表示为：

(5)

当参数0≤s≤1时，p是线段ab上的点；当参数s<0时，p是ba延长线上的点；当参数s>1时，p是ab延长线上的点。

②线上参数方程

设q是直线cd上的一点，q点的坐标(U，V，W)的参数方程可以表示为：

(6)

当参数0≤t≤1时，q是线段cd上的点；当参数t<0时，q是dc延长线上的点；当参数t>1时，q是cd延长线上的点。

③两点间的距离

p，q两点之间的距离为：

(7)

即为两点间的欧氏距离。

2.3 最小空间距离分析

线状要素间的距离有无数多个，工程中应用较多的是最小距离，由两点间欧氏距离公式推演最小距离的过程：

①距离公式

距离平方的展开式为

f(s，t)=pq2=(X-U)2+(Y-V)2+(Z-W)2=[(x1-x3)+s(x2-x1)-t(x4-x3)]2+[(y1-y3)+s(y2-y1)-t(y4-y3)]2+[(z1-z3)+s(z2-z1)-t(z4-z3)]2

(8)

要求直线ab，cd之间的最短距离，需要求f(s，t)的最小值。

②推导计算

对f(s，t)分别求s，t的偏导数，并令偏导数为0：

(9)

展开并整理后，得到下列方程组：

(10)

③求解方程

根据坐标点求解方程式

(11)

(12)

(13)

(14)

如果从这个方程组求出的参数s，t的值满足0≤s≤1，0≤t≤1，说明p点落在线段ab上，q点落在线段cd上，这时pq的长度为：

(15)

就是线段ab与cd的最短距离。

④计算结论

如果从方程组求出的参数s，t的值不满足0≤s≤1，0≤t≤1，说明不可能在线段ab内部找到一点p，在线段cd内部找到一点q，使得pq的长度就是线段ab与cd的最短距离。

这时，可以分别求a点到线段cd的最短距离、b点到线段cd的最短距离、c点到线段ab的最短距离、d点到线段ab的最短距离。

dis=Min(dis1，dis2，dis3，dis4)

(16)

disi|i∈(1，2，3，4)——线段端点a、b、c、d到非其所在线段的最短距离

dis即为线段ab到cd的最短距离[7～9]。

3 空间距离算法分析

3.1 算法描述

步骤描述：①获取空间两条线状要素的4个端点及其坐标值；②判断输入要素是否共面，如果共面进入步骤③，否则进入步骤④；③判断两要素是否平行，如果平行直接计算垂线距离dis，如果不平行则分别计算两条线状要素到彼此的最短距离，然后取最小值；④分别计算s与t的值，如果同时满足0≤s≤1，0≤t≤1，则计算距离pq，否则分别计算两条线状要素端点到另一条线状要素的最小值并获取最小值dis=Min(dis1，dis2，dis3，dis4)。⑤返回最小距离。

图5 算法流程图

3.2 算法伪代码实现

三维点的伪代码表示：

publicdouble point3d(){

private double _x，_y，_z；

point3d(double x，double y，double z){this._x=x；this._y=y；this._z=z；}

public x{return this._x；}

public y{returnthis._y；}

public z{return this._z；}

}

三维线段的伪代码表示：

public point3d line3d(){

private point3d _poi[2]；

line3d(point3d a，point3d b){this._poi[0]=a；this._poi[1]=b；}

public poi_s{return this._poi[0]；}

public poi_e{return this.poi[1]；}

}

计算过程基于传统的空间几何计算模型，可以准确地计算给定的两条线状要素间的空间距离，算法对于中等数量的线状要素的空间距离计算适应性较好。通过对输入线段进行判别，合理组织程序流程，简化计算过程，避免冗余计算，提高运行效率。

运算过程的伪代码表示：

public double calculate(){

private line3d la，lb；

public calculate(line3d a，line3d b){this.la=a；this.lb=b；}

privatebool coplane(){}//判断是否共面

privatebool parallel(){}//判断是否平行

private double calculateparalleldis(){}//计算平行线距离

private double calculatecoplanedis(){}//计算共面非平行线距离

private bool inrange(){}//判断s、t是否位于区间内

private double calculateinrangedis(){} //计算位于区间内的最短距离

private double calculateoutrangedis(){}//计算超出区间的最短距离

public double mindis(){if(coplane()){

if(parallel()){return calculateparalleldis()；}else{return calculatecoplanedis()；}

}else{

If(inrange()){return calculateinrangedis()；}else{return calculateoutrangedis()；}}

}

}

3.3 实例验证

通过c#语言对算法进行编程实现，加载已有的地下管线数据，对地下管线之间的空间最小距离进行计算，并与国家规定的管线间距标准进行对比，可以快速发现不符合规范要求的管线，为管线施工与整改提供数据基础。

图6 空间最小距离算法实例

4 结 论

通过对空间线状要素的抽象，建立空间直线的距离模型，经过模型推导得出空间线段最短距离的表达式。在数学模型计算机化的过程中对算法进行了调整与优化，通过实例的运行验证了算法的有效性。随着智能算法的发展，遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等算法在现实中的应用逐渐增多[10，11]，遗传算法也被应用到线状地理要素的碰撞检测分析中，传统算法与智能算法各有所长，适用于不同的应用场景，两者结合可以提升运算效率。

[1] Frank A U. Qualitative spatial reasoning about distances and directions in geographic space[J]. Journal of Visual Languagesand Computing，1992，3(4)：343～371.

[2] 郭仁忠. 空间分析[M]. 北京：北京高等教育出版社，2001.

[3] 邓敏，赵彬彬，徐震等. GIS空间目标间距离表达方法及分析[J]. 计算机工程与应用，2011(1)：35～39.

[4] 薛露露. 方向与距离关系集成的空间定性推理[D]. 北京：北京大学，2008.

[5] 马广韬，徐厚生，王莹君. 求解空间两异面直线公垂距离的计算方法[J]. 山东理工大学学报·自然科学版，2007(4)：103～105.

[6] 崔朋志，刘宝锋. 空间管线间最短距离研究[J]. 测绘科学，2012(5)：121～140.

[7] 黄雁，李黎. 多源空间信息服务集成方法研究[J]. 城市勘测，2011(4)：50～53.

[8] 李平，卢立. ArcGIS中几种坐标系转换方法的应用研究[J]. 城市勘测，2012(1)：87～90.

[9] 余剑. 土地勘测定界系统的设计与实现[J]. 城市勘测，2012(5)：60～62.

[10] 刘洪江，曹玉香. 基于ArcGIS实现地类图斑净面积的计算[J]. 城市勘测，2012(5)：114～116.

[11] 郑建敏. 城市基础地理信息平台的构建与应用[J]. 城市勘测，2013(3)：38～42.

SpatialDistanceCalculationandOptimizationAlgorithmofLinearGeographicFeatures

Deng Zhenmin1，2，Tian Fangfang1，Yang Cuiyuan1
(1.Geological Exploration Institute of Shandong Zhengyuan，Jinan 250101，China；2.Shandong Zhongji Geographic Information Supervision Co.，Ltd，Jinan 250101，China)

For the purpose of establishingand optimizing spatial distance calculation model，the mathematical model of the minimum spatial distance between two elements is deducedby analyzing the three-dimensional relationship between two elements in the spatial rangeusing the method of mapping linear geometric elements’ relationship to spatial geometric concept category. The model is expanded as the basic unit to obtain the mathematical algorithm of the minimum distance calculation between the geographic elements in the space rangeusing the spatial scope of the division and optimization of the calculation process to improve the performance of the algorithm. The validity of the algorithm is verified by the pipeline example andthe algorithm can be widely used to calculate the spatial distance of linear geography elements.

linear geographic features；minimum spatial distance；spatial division；algorithm validation

1672-8262(2017)06-63-05

P208.1

A

2017—02—21

邓振民(1984—)，男，硕士，助理工程师，主要从事GIS信息系统的研发与集成工作。