基于向量法距離計(jì)算的快速圓形區(qū)域查詢方法

張國(guó)賓 王勇 倪凱歌 陳晨

摘要 隨著移動(dòng)網(wǎng)絡(luò)技術(shù)與全球定位技術(shù)的發(fā)展，GIS信息在軍事應(yīng)用中使用愈來(lái)愈頻繁，在任務(wù)數(shù)據(jù)保障中，對(duì)目標(biāo)周邊區(qū)域情報(bào)數(shù)據(jù)的快速查詢是一項(xiàng)基本功能。在推進(jìn)國(guó)產(chǎn)化的進(jìn)程中，部分國(guó)產(chǎn)數(shù)據(jù)庫(kù)還未集成空間分析功能。本文提供了一種已知兩點(diǎn)經(jīng)緯度，基于向量點(diǎn)乘公式，求出兩點(diǎn)對(duì)應(yīng)地心角，計(jì)算距離，實(shí)現(xiàn)圓形區(qū)域查詢的方法，同時(shí)通過(guò)對(duì)數(shù)據(jù)初篩過(guò)濾、建立索引等方法進(jìn)行查詢優(yōu)化，達(dá)到快速查詢效果。

【關(guān)鍵詞】向量點(diǎn)乘距離計(jì)算 圓形區(qū)域查詢初篩過(guò)濾 查詢優(yōu)化

隨著移動(dòng)網(wǎng)絡(luò)技術(shù)與全球定位技術(shù)的發(fā)展，GIS信息在生活、軍事應(yīng)用中使用愈來(lái)愈頻繁，在任務(wù)數(shù)據(jù)保障中，對(duì)目標(biāo)周邊區(qū)域情報(bào)數(shù)據(jù)的快速查詢是一項(xiàng)基本功能。在推進(jìn)國(guó)產(chǎn)化的進(jìn)程中，部分國(guó)產(chǎn)數(shù)據(jù)庫(kù)還未集成空間分析功能。本文提供了一種基于向量法距離計(jì)算的快速圓形區(qū)域查詢方法。

圓形區(qū)域查詢是常用的一種區(qū)域查詢方式，通過(guò)計(jì)算數(shù)據(jù)庫(kù)中各POI（商家）或相關(guān)方信息與目的目標(biāo)位置（中心點(diǎn)）的距離，而進(jìn)行的一種篩選查詢。所以圓形區(qū)域的查詢重點(diǎn)在于與中心點(diǎn)間的距離計(jì)算。

1 計(jì)算方法

1.1 常用計(jì)算方法

對(duì)己知兩點(diǎn)經(jīng)緯度的進(jìn)行距離計(jì)算由多種方法，下邊是常用的幾種。

（1）己知兩點(diǎn)的大地坐標(biāo)計(jì)算距離，設(shè)兩點(diǎn)大地坐標(biāo)值為（xl，yl），（x2，y2）則：

式中L是兩點(diǎn)之間距離，單位是km。用此公式計(jì)算時(shí)，要注意兩點(diǎn)是否在同一個(gè)坐標(biāo)系內(nèi)。如果兩點(diǎn)不在同一個(gè)坐標(biāo)系內(nèi)，就須將其中的一點(diǎn)經(jīng)坐標(biāo)平移變換到另一點(diǎn)所在的坐標(biāo)系內(nèi)。平移公式為：x =x+a、y=y+b，式中a，b是原坐標(biāo)的原點(diǎn)在新坐標(biāo)系中的坐標(biāo)值。

（2）己知兩點(diǎn)的空間三維坐標(biāo)計(jì)算距離，設(shè)兩點(diǎn)空間三維坐標(biāo)值為（xl，yl，zl），（x2，y2，z2）則：

式（2）中L是兩點(diǎn)之間距離，單位是km。用此公式計(jì)算時(shí)，是將地球近似成球體，地表點(diǎn)都為空間直角坐標(biāo)系球體表面一點(diǎn)，將經(jīng)緯度坐標(biāo)轉(zhuǎn)換為空間直角坐標(biāo)系坐標(biāo)，公式（3）如下。

在直角坐標(biāo)系中，X軸為地心與初始子午線與赤道的交點(diǎn)的連接方向?yàn)檎?，Y軸為地心向西經(jīng)90°子午線與赤道交點(diǎn)的方向?yàn)檎颍琙軸為地心與北極點(diǎn)連接方向?yàn)檎?，R為地球半徑，lat、lon分別為緯度、經(jīng)度值，x、y、z分別是該點(diǎn)轉(zhuǎn)換后的空間坐標(biāo)值。

（3）己知兩點(diǎn)的經(jīng)緯度計(jì)算兩點(diǎn)距離的近似公式，設(shè)定A點(diǎn)（latl，lonl）和B點(diǎn)（ lat2，lon2）則：

式（4）中L是兩點(diǎn)之間距離，單位是度，111.199km是赤道附近10經(jīng)緯度差對(duì)應(yīng)的距離值。

比較以上三種方法：

第一種方法比較簡(jiǎn)單，但大地坐標(biāo)非常用地理信息表示方法，不易獲取該值;

第二種方法，采用三維直角坐標(biāo)系，計(jì)算空間兩點(diǎn)直線距離，即球面兩點(diǎn)間弦的長(zhǎng)度，在短距離計(jì)算中近似等于地表距離，但在大跨度遠(yuǎn)距離時(shí)，誤差較大;

第三種方法，分別計(jì)算兩點(diǎn)在經(jīng)緯度方向的弧長(zhǎng)值，近似利用勾股定理，獲得兩點(diǎn)間的弧長(zhǎng)。同樣，與第二種方法類似，所使用的勾股定理是平面直角坐標(biāo)系內(nèi)的計(jì)算公式，在近距離內(nèi)，兩點(diǎn)可認(rèn)為是在同一地平面，但在大跨度遠(yuǎn)距離時(shí)，誤差依然較大。

1.2 向量法距離計(jì)算

對(duì)于球面體，球面弧長(zhǎng)，等于球體半徑與對(duì)應(yīng)球心角（弧度）的乘積，同理，地球表面兩點(diǎn)間距離，可以從兩點(diǎn)與地心組成空間角度來(lái)計(jì)算獲得。暫時(shí)稱該兩點(diǎn)與地心組成的角度稱為地心角，如圖1中所示地表A點(diǎn)（ LonA，LatA）與B點(diǎn)（LonB，LatB）與地心O組成的夾角0。

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

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

2 設(shè)計(jì)實(shí)現(xiàn)與優(yōu)化

2.1 設(shè)計(jì)實(shí)現(xiàn)

數(shù)據(jù)庫(kù)將采用向量法計(jì)算距離方法做成數(shù)據(jù)庫(kù)函數(shù)，代碼實(shí)現(xiàn)如下所示：

---Cul JW Distance：通過(guò)兩點(diǎn)經(jīng)緯度，計(jì)算距離，返回值為兩點(diǎn)間距離，單位為km，小數(shù)點(diǎn)后4位（分米）

create or replace Function”P(pán)UBLIC””CulJW Distance”

（

lonl

double，

latl double，

lon2

double，

lat2 double

）

retum number

1S

pi double：=3.1415926;

EARTH_R number：=6378137; 一地球長(zhǎng)軸半徑

EART H

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

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

一地球短軸半徑

lathl double;

一緯度1弧度表示

lonhl double;

一經(jīng)度1弧度表示

lath2 double;

一緯度2弧度表示

lonh2 double;

一經(jīng)度2弧度表示

DN double;

一兩點(diǎn)中間緯度位置地球半徑

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;

在己知某點(diǎn)經(jīng)緯度（lon，lat），查詢L公里內(nèi)目標(biāo)數(shù)據(jù)信息的查詢方法可以寫(xiě)為：selectid，culj w_distanee （longitude，latitude，lon，lat）distance from table where distance <=L;

2.2 性能優(yōu)化

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

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

建立索引是另一種提高檢索速度的方法，可以將數(shù)據(jù)庫(kù)表中經(jīng)緯度建立空間索引，但實(shí)際測(cè)試效果，速度并未明顯提升，經(jīng)查證發(fā)現(xiàn)，當(dāng)查詢語(yǔ)句where后的條件中有函數(shù)計(jì)算時(shí)，索引將不被使用，即查詢?nèi)匀皇褂玫氖侨頂?shù)據(jù)的遍歷模式。為了能夠使索引起到作用，查詢語(yǔ)句需要如下更改，先根據(jù)初篩條件，將初篩結(jié)果集放置一個(gè)臨時(shí)集合中，再對(duì)該臨時(shí)集合內(nèi)數(shù)據(jù)進(jìn)行距離計(jì)算。查詢語(yǔ)句變換為：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語(yǔ)句執(zhí)行過(guò)程中為了減少數(shù)據(jù)庫(kù)對(duì)SQL語(yǔ)句硬解析次數(shù)，提高使用高速緩存空間軟解析的命中率，使用綁定變量法，在此語(yǔ)句中，每次查詢變化的只是中心點(diǎn)的經(jīng)緯度和圓形區(qū)域半徑，將該三位參數(shù)使用綁定變量替換，則查詢語(yǔ)句變?yōu)椋簊elect 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;如此調(diào)優(yōu)之后，百萬(wàn)級(jí)數(shù)據(jù)查詢將至毫秒級(jí)（105W時(shí)4.8ms）

3 結(jié)束語(yǔ)

在任務(wù)保障中，經(jīng)常需要快速查詢目標(biāo)周邊信息情報(bào)數(shù)據(jù)，在己知目標(biāo)經(jīng)緯度和區(qū)域范圍的情況下，使用本文的方法進(jìn)行計(jì)算簡(jiǎn)單方便，通過(guò)初篩過(guò)濾、使用索引等方法優(yōu)化查詢過(guò)程，達(dá)到快速查詢目的，為任務(wù)執(zhí)行提供情報(bào)支援保障。

參考文獻(xiàn)

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

[2]韓忠民，知經(jīng)緯度計(jì)算兩點(diǎn)精確距離[J].科技傳播，2011（06）：196-194.

[3]王瓊麗，數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)性能優(yōu)化研究與實(shí)踐[D].北京郵電大學(xué)，2009： 34-39.

[4]汪照東.Oracle llg數(shù)據(jù)庫(kù)管理與優(yōu)化寶典[M].電子工業(yè)出版社，2008： 720-724.