線狀地理要素空間距離計算與算法優化

鄧振民，田方方，楊翠媛

(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信息系統的研發與集成工作。