基于向量法距離計算的快速圓形區域查詢方法

張國賓 王勇 倪凱歌 陳晨

摘要 隨著移動網絡技術與全球定位技術的發展，GIS信息在軍事應用中使用愈來愈頻繁，在任務數據保障中，對目標周邊區域情報數據的快速查詢是一項基本功能。在推進國產化的進程中，部分國產數據庫還未集成空間分析功能。本文提供了一種已知兩點經緯度，基于向量點乘公式，求出兩點對應地心角，計算距離，實現圓形區域查詢的方法，同時通過對數據初篩過濾、建立索引等方法進行查詢優化，達到快速查詢效果。

【關鍵詞】向量點乘距離計算 圓形區域查詢初篩過濾 查詢優化

隨著移動網絡技術與全球定位技術的發展，GIS信息在生活、軍事應用中使用愈來愈頻繁，在任務數據保障中，對目標周邊區域情報數據的快速查詢是一項基本功能。在推進國產化的進程中，部分國產數據庫還未集成空間分析功能。本文提供了一種基于向量法距離計算的快速圓形區域查詢方法。

圓形區域查詢是常用的一種區域查詢方式，通過計算數據庫中各POI（商家）或相關方信息與目的目標位置（中心點）的距離，而進行的一種篩選查詢。所以圓形區域的查詢重點在于與中心點間的距離計算。

1 計算方法

1.1 常用計算方法

對己知兩點經緯度的進行距離計算由多種方法，下邊是常用的幾種。

（1）己知兩點的大地坐標計算距離，設兩點大地坐標值為（xl，yl），（x2，y2）則：

式中L是兩點之間距離，單位是km。用此公式計算時，要注意兩點是否在同一個坐標系內。如果兩點不在同一個坐標系內，就須將其中的一點經坐標平移變換到另一點所在的坐標系內。平移公式為：x =x+a、y=y+b，式中a，b是原坐標的原點在新坐標系中的坐標值。

（2）己知兩點的空間三維坐標計算距離，設兩點空間三維坐標值為（xl，yl，zl），（x2，y2，z2）則：

式（2）中L是兩點之間距離，單位是km。用此公式計算時，是將地球近似成球體，地表點都為空間直角坐標系球體表面一點，將經緯度坐標轉換為空間直角坐標系坐標，公式（3）如下。

在直角坐標系中，X軸為地心與初始子午線與赤道的交點的連接方向為正向，Y軸為地心向西經90°子午線與赤道交點的方向為正向，Z軸為地心與北極點連接方向為正向，R為地球半徑，lat、lon分別為緯度、經度值，x、y、z分別是該點轉換后的空間坐標值。

（3）己知兩點的經緯度計算兩點距離的近似公式，設定A點（latl，lonl）和B點（ lat2，lon2）則：

式（4）中L是兩點之間距離，單位是度，111.199km是赤道附近10經緯度差對應的距離值。

比較以上三種方法：

第一種方法比較簡單，但大地坐標非常用地理信息表示方法，不易獲取該值;

第二種方法，采用三維直角坐標系，計算空間兩點直線距離，即球面兩點間弦的長度，在短距離計算中近似等于地表距離，但在大跨度遠距離時，誤差較大;

第三種方法，分別計算兩點在經緯度方向的弧長值，近似利用勾股定理，獲得兩點間的弧長。同樣，與第二種方法類似，所使用的勾股定理是平面直角坐標系內的計算公式，在近距離內，兩點可認為是在同一地平面，但在大跨度遠距離時，誤差依然較大。

1.2 向量法距離計算

對于球面體，球面弧長，等于球體半徑與對應球心角（弧度）的乘積，同理，地球表面兩點間距離，可以從兩點與地心組成空間角度來計算獲得。暫時稱該兩點與地心組成的角度稱為地心角，如圖1中所示地表A點（ LonA，LatA）與B點（LonB，LatB）與地心O組成的夾角0。

求θ角的方法有多種，可以通過AB弦長度與OA、OB地球半徑的長度，根據三角形余弦公式獲得，也可以通過三面角余弦公式獲的。但其計算過程步驟復雜。本方案采用向量法獲取θ角值。OA、OB可認為是兩個三維空間向量，θ為向量間夾角，根據向量點乘公式（5）（6）可知，0的余弦等于兩向量點乘除以兩向量模的乘積。

A、B兩點的弧長AB則等于R.θ，θ的單位是弧度。由于地球是橢球型，在WGS-84地球橢球體中，赤道半徑為長軸半徑R，長6378127km，第一偏心率e2=0.006694379013，

2 設計實現與優化

2.1 設計實現

數據庫將采用向量法計算距離方法做成數據庫函數，代碼實現如下所示：

---Cul JW Distance：通過兩點經緯度，計算距離，返回值為兩點間距離，單位為km，小數點后4位（分米）

create or replace Function”PUBLIC””CulJW Distance”

（

lonl

double，

latl double，

lon2

double，

lat2 double

）

retum number

1S

pi double：=3.1415926;

EARTH_R number：=6378137; 一地球長軸半徑

EART H

E 2double：=0.006694379013;--地球第一偏心率

EARTH B double：=EARTHR*SQRT（l-EARTH_E2）;

一地球短軸半徑

lathl double;

一緯度1弧度表示

lonhl double;

一經度1弧度表示

lath2 double;

一緯度2弧度表示

lonh2 double;

一經度2弧度表示

DN double;

一兩點中間緯度位置地球半徑

TranMatrix00 double;

TranMatrix01 double;

TranMatrix02 double;

TranMatrixlo double;

TranMatrixll double;

TranMatrix12 double;

cosangle double;

一夾角余弦值

angle double;

一夾角

begin

lathl：=latl*PIo，/180;

lonhl：=lonl*PI（）/180;

lath2：=lat2*PIo，/180;

lonh2：=lon2*PI（）/180;

DN：=EARTH_R*SQRT（1-EARTHE2* SIN《lathl+lath2）/2） *SIN《lathl+lath2）/2》;

TranMatrixOO：=COS（lathl）*COS（lonhl）;

TranMatrix0 1：=COS（lathl）*SIN（lonhl）;

TranMatrix02：= SIN（larhl）;

TranMatrixlO：=COS（lath2）*COS（Ionh2）;

TranMatrixll：=CO S（larh2）*SIN（lonh2）;

TranMarrix12：=SIN（lath2）;

Cosangle：=TranMatrixOO*TranMatrixlO+TranMatrixOl*TranMatrixll+TranMatrix02*TranMatrix12;

angle：=ACOS（cosangle）;

retum ROUND（DN*angle/1000，4）;

end;

在己知某點經緯度（lon，lat），查詢L公里內目標數據信息的查詢方法可以寫為：selectid，culj w_distanee （longitude，latitude，lon，lat）distance from table where distance <=L;

2.2 性能優化

上述查詢只是功能實現，但實際在使用中，數據量達到100W時，查詢過程中將對整表數據遍歷計算比較，耗時達到數秒（105W時，11.63秒），這對于使用過程中時無法容忍的，如何提高效率，可以從減少查詢范圍、增加查詢索引等方面著手。

縮小查詢區域范圍，對待查詢數據進行初篩過濾，將待查詢范圍縮減為該圓形區域的外切正方形，根據圓形區域半徑可計算出該半徑對應的圓心角度值，分別在經度方向與緯度方向找到邊界最大值，如圖2所示，A（ Lon，Lat）點周圍L公里范圍查詢時，首先求得在同緯度方向上，L公里對應的經度角么AO'B（0），同經度線上對應的緯度角∠BOC（φ），計算過程中0' B=O' A=OB.Cos（ Lat）.OB可根據上文中公式（9）進行計算。至此，則可在查詢時增加查詢限制條件，在一定范圍內的進行初步篩選。查詢語句變為：select id，culjw_distance（longirude，latitude，Ion，lat） distance from table where distance <=Land longitude between lon-θandlon+θ and latitudebetween lat-φandlat+φ;當然，當0蘭1800或Lat-θ<-90°或Lat+θ>90°時，應做相應修訂，此處不具體討論。如此做來，100W級數據查詢時間將至百毫秒級（105W是0.28s）。

建立索引是另一種提高檢索速度的方法，可以將數據庫表中經緯度建立空間索引，但實際測試效果，速度并未明顯提升，經查證發現，當查詢語句where后的條件中有函數計算時，索引將不被使用，即查詢仍然使用的是全表數據的遍歷模式。為了能夠使索引起到作用，查詢語句需要如下更改，先根據初篩條件，將初篩結果集放置一個臨時集合中，再對該臨時集合內數據進行距離計算。查詢語句變換為：select id，culjw_distance（longitude，latitude，lon，lat） distance from （select id，longitude，latitude fromtable where Iongitude between lon-θ and lon+θand latitude between lat-φand lat+φ）tempwhere distance <=L;

在SQL語句執行過程中為了減少數據庫對SQL語句硬解析次數，提高使用高速緩存空間軟解析的命中率，使用綁定變量法，在此語句中，每次查詢變化的只是中心點的經緯度和圓形區域半徑，將該三位參數使用綁定變量替換，則查詢語句變為：select id，culjw_disrance（longitude，latitude，：lon，：lat） distance from（select id，longitude，latitude from table wherelongitude between lon-θ and lon+θ and latitudebetween lat-φand lat+φ） tempwhere distance<=：L;如此調優之后，百萬級數據查詢將至毫秒級（105W時4.8ms）

3 結束語

在任務保障中，經常需要快速查詢目標周邊信息情報數據，在己知目標經緯度和區域范圍的情況下，使用本文的方法進行計算簡單方便，通過初篩過濾、使用索引等方法優化查詢過程，達到快速查詢目的，為任務執行提供情報支援保障。

參考文獻

[1]胡偉凡，楊恢先，于洪等，基于高斯投影的經緯度距離參數修正方法[J].計算機工程，2010，36 （02）：244-246.

[2]韓忠民，知經緯度計算兩點精確距離[J].科技傳播，2011（06）：196-194.

[3]王瓊麗，數據庫應用系統性能優化研究與實踐[D].北京郵電大學，2009： 34-39.

[4]汪照東.Oracle llg數據庫管理與優化寶典[M].電子工業出版社，2008： 720-724.