適用于道路沿線信息查詢的矢量壓縮算法

張 丹，胡 泊

(1. 黃河水利職業(yè)技術(shù)學(xué)院，河南 開封 475004； 2. 河南理工大學(xué)礦山空間信息技術(shù)國家測繪地理信息局重點實驗室，河南 焦作 454003)

適用于道路沿線信息查詢的矢量壓縮算法

張 丹1,2，胡 泊1

(1. 黃河水利職業(yè)技術(shù)學(xué)院，河南 開封 475004； 2. 河南理工大學(xué)礦山空間信息技術(shù)國家測繪地理信息局重點實驗室，河南 焦作 454003)

針對矢量數(shù)字地圖中道路布局錯綜復(fù)雜的問題，提出了一種用于查詢道路沿線信息的矢量壓縮算法。該方法首先基于夾角和歐氏距離對道路端點與拐角凸側(cè)地物點進行判斷，然后利用矢量壓縮算法對道路折線進行簡化、分析地物點是否在道路沿線的緩沖區(qū)內(nèi)，從而實現(xiàn)地物信息與道路沿線的鄰近度判斷。試驗結(jié)果表明該方法的高效性和有效性，具有復(fù)雜道路情況下沿線地物點的查詢分析功能。

GIS；緩沖區(qū)分析；疊加分析；矢量壓縮

Abstract： Aiming at the intricate layout of roads on vector digital maps,the paper comes up with an algorithm for searching features information within road polyline buffer field based on vector compression.Judging the features information in endpoints and corner convex field with included angle and Euclidean distance,then simplify the road polyline by method of vector compression,analyze the proximity between point features and road polyline.And realize the searching function based on this method on Google Map.Experimental results show that the algorithm is efficient,fast and accurate for searching along the road polyline.

Keywords： GIS；buffer analysis；overlay analysis；vector compression

GIS查詢是從眾多的時空實體中選擇滿足用戶要求的空間實體[1]，空間分析是GIS的核心內(nèi)容之一[2]。矢量數(shù)字地圖中道路信息主要以折線(由一系列的道路節(jié)點組成)形式表示，而道路緩沖區(qū)則主要是以折線對象為中心線形成的多邊形區(qū)域[3]。判斷點與多邊形關(guān)系的疊加分析是查詢道路沿線地物信息的重要方法[4-5]，常用的疊加分析多是基于多邊形裁剪算法，文獻[6]介紹了基于拓撲模型和簡單數(shù)據(jù)模型的兩類算法，在比較兩者優(yōu)劣性基礎(chǔ)上提出基于交點搜索的多邊形疊加分析算法?，F(xiàn)有的多邊形裁剪算法多針對具體類型的多邊形，使得算法復(fù)雜、時間消耗大，如Sutherl-Hodgeman、梁-Barsky、NLN算法要求裁剪多邊形是凸多邊形[7-9]。Weiler算法，以及近幾年出現(xiàn)的Vatti算法及Greiner-Hormann算法[10-12]，則可以處理一般常見的多邊形。文獻[12]提出用單線性鏈表數(shù)據(jù)結(jié)構(gòu)的一般多邊形裁剪算法，并與Vatti算法及Greiner-Hormann算法進行了對比分析。

上述算法需要遍歷求出判斷點與每一條折線段之間的最短距離，然后與緩沖區(qū)閾值進行比較，若小于閾值，則判定點在緩沖區(qū)內(nèi)，否則不在緩沖區(qū)內(nèi)。由此可見，這些算法計算過程煩瑣、效率較低，不適用于節(jié)點較多且形狀錯綜復(fù)雜的折線。針對上述問題，本文提出一種判斷點是否在折線緩沖區(qū)內(nèi)的矢量壓縮算法，該方法通過對折線的逐步壓縮和簡化，確定與地物點相距最近的道路折線段，從而進行點與線的鄰近度判斷，實現(xiàn)空間查詢功能。實例驗證結(jié)果表明該算法快速、有效，具有一定的實際應(yīng)用價值。

1 常用緩沖區(qū)分析方法

1.1 道路沿線緩沖區(qū)建立

傳統(tǒng)的緩沖區(qū)分析是在地理實體周圍建立一定寬度的緩沖區(qū)多邊形[13]。角分線法是建立折線緩沖區(qū)的最簡單方法；凸角圓弧法則是為減小由于凸側(cè)角點進一步變銳時，拐角凸側(cè)處緩沖區(qū)遠離折線節(jié)點所引起的偏差而用圓弧進行彌合，其中圓弧的兩端點為過節(jié)點作其相鄰兩折線段的垂線并與凸側(cè)緩沖區(qū)邊界形成的交點[14-15]。本文采用凸角圓弧法建立折線緩沖區(qū)，并將點在道路折線緩沖區(qū)的情況分為3種：區(qū)域1表示端點處緩沖區(qū)、區(qū)域2表示拐角凸側(cè)處緩沖區(qū)、區(qū)域3表示一般區(qū)域緩沖區(qū)，如圖1所示。

圖1 凸角圓弧法生成的折線緩沖區(qū)

1.2 端點與拐角凸側(cè)緩沖區(qū)分析

1.2.1 端點緩沖區(qū)分析

端點緩沖區(qū)的判定步驟為(如圖2所示，以端點P0為例)：

(1) 連接AP0、A1P0，在折線A、A1一側(cè)分別與折線形成夾角∠AP0P1和∠A1P0P1。

(2) 若夾角≤90°，將此點直接過濾；反之，則將AP0與閾值d進行比較，此時如果AP0≤d，判斷點A在端點P0的緩沖區(qū)內(nèi)；若AP0>d，則不在該緩沖區(qū)內(nèi)。

同理，對Pn進行分析，若點被過濾，則需進行后續(xù)算法。

圖2 端點處緩沖區(qū)判斷

1.2.2 拐角凸側(cè)緩沖區(qū)分析

用圓弧對折線在拐角凸側(cè)區(qū)域進行擬合，形成凸角圓弧緩沖區(qū)。對經(jīng)過由上節(jié)端點處過濾所剩余的點，可按下列步驟進行判定(如圖3所示)：

(1) 連接APi并與折線在靠A點一側(cè)形成夾角∠APiPi-1和∠APiPi+1。

(2) 若∠APiPi-1和∠APiPi+1均大于90°，則點在發(fā)散的扇形陰影區(qū)域PiMN內(nèi)(若同時滿足在多個節(jié)點凸側(cè)的發(fā)散扇形陰影區(qū)域內(nèi)，則將A與距離最近的節(jié)點Pi進行判斷)，予以保留，否則將該點過濾。

(3) 若APi≤d，則點A位于緩沖區(qū)內(nèi)。

圖3 凸角圓弧緩沖區(qū)判斷

2 本文算法

折線可以分為理想型折線和一般型折線兩類。

理想型折線：折線每個拐彎處的夾角≥90°(如圖4所示)，折線軌跡大幅度逐步遠離起始點。

圖4 理想型折線

一般型折線：折線拐角處夾角有銳角有鈍角，如“發(fā)夾彎”“十字路口自相交”等，使得折線呈各式各樣且錯綜復(fù)雜(如圖5所示)，在實際情況下此類折線更具有普遍性。

圖5 一般型折線

對于理想型折線可用較小夾角法對道路一般區(qū)域的點進行緩沖區(qū)分析，具體為：若使點A與某節(jié)點Pi的距離離最短，則設(shè)A僅可能與Pi相關(guān)的折線段形成緩沖區(qū)關(guān)系，通過比較APi與折線形成的臨近A側(cè)的兩夾角大小，并過A對形成較小角的折線段作垂線，垂距L即為點到此折線的最短距離。

對于一般型折線，如圖5中點A與節(jié)點P3的距離最短，而實際上最短的折線是P4P5，與節(jié)點P3無關(guān)，因此較小夾角法無法適用一般型折線。

2.1 矢量壓縮算法

為適應(yīng)一般型折線，本文提出基于矢量壓縮的算法，即對被過濾的點采用基于矢量壓縮算法進行判斷。首先計算待判定點與某節(jié)點取得的最短距離，利用較小夾角法在局部進行初步緩沖區(qū)判斷：

(1) 若判定點不在局部折線段的緩沖區(qū)內(nèi)，可將其全部消去，并對折線進行壓縮簡化。

(2) 在折線斷開處用虛擬線段連接，這樣可以保證折線的連續(xù)性，并不參與后續(xù)計算。

(3) 判斷點是否在緩沖區(qū)內(nèi)，當(dāng)點同時在多條折線段的閾值內(nèi)，滿足其中之一即可停止計算，或當(dāng)折線無法再壓縮時停止計算。

2.2 算法原理與實現(xiàn)

2.2.1 算法原理

設(shè)P0、Pn分別為折線的起、始端點，Pi為中間節(jié)點(i=0,1,2，…，n)，折線由節(jié)點及節(jié)點間的折線段組成，P_C、L_C表示組成折線的節(jié)點集合、線段集合，即

P_C={P0,P1,P2,…,Pi-1,Pi,Pi+1,…，Pn-1,Pn

(1)

L_C={P0P1,P1P2,P2P3,…，Pi-1Pi,PiPi+1,…，Pn-1Pn}

(2)

S_C為遍歷判定點與各節(jié)點間的距離集合

S_C={s_AP0,s_AP1,…，s_APi,…，s_APn}

(3)

上述3個集合，可對折線本身及待判斷點與折線關(guān)系進行描述：

(1) 點A為待判定的地物要素點，d為緩沖區(qū)閾值，L為計算得到的點與折線段的距離。

(2) 地圖上各點的經(jīng)緯度坐標(biāo)已知，用(lat，lng)表示。

(3) 在壓縮過程中，若出現(xiàn)兩條虛擬線段相鄰的情況，由于其均不參與計算，可自動將它們壓縮合并，用新的虛擬線段取代。

2.2.2 算法實現(xiàn)

圖6為一般型折線，壓縮算法的實現(xiàn)過程為：

(1) 對點A到折線點集P_C中各節(jié)點遍歷計算距離，得到距離集S_C。

圖6 一般型折線

(2) 從距離集S_C中取出A與某節(jié)點Pi間的最短距離Smin，令Smin=AP2。

(3) 連接APi，在折線靠A一側(cè)形成兩夾角∠APiPi-1和∠APiPi+1，通過比較可知：∠AP2P3=min(∠AP2P1，∠AP2P3)。根據(jù)較小夾角法，A點初步找到折線段P2P3，過A作垂直于P2P3的垂線AM，則A到線段P2P3的距離為

L=AM=AP2×sin∠AP2P3

(4)

(4) 若L≤閾值d，則點A在折線緩沖區(qū)內(nèi)，計算結(jié)束；否則，去掉節(jié)點P2和線段P2P1、P2P3，形成虛擬線段P1P3，折線被第一次簡化。折線每壓縮一次，與折線相關(guān)的集合P_C、L_C、S_C均會發(fā)生改變，形成新的折線和新的點集合P_C、線段集合L_C及距離集合S_C。

(5) 對形成的新折線，重復(fù)步驟(1)—步驟(4)，當(dāng)判斷出點A在折線緩沖區(qū)內(nèi)，則立即停止計算；否則，繼續(xù)簡化壓縮。

(6) 若折線再無法繼續(xù)壓縮(如圖7所示)，且仍未判斷出點在緩沖區(qū)內(nèi)，則計算終止，說明點A不在折線緩沖區(qū)內(nèi)。

3 實例驗證與結(jié)果分析

為驗證本文方法有效性，選擇普通道路與復(fù)雜道路形狀兩種情況，對道路沿線地物信息進行查詢試驗。

(1) 普通道路情況。在桂林市疊彩區(qū)標(biāo)注米粉店若干(如圖8所示)，然后沿“疊彩路—芙蓉路—鳳北路—中山路—三皇路—四會路”軌跡在地圖上畫出道路沿線，設(shè)置緩沖區(qū)閾值為30 m。點擊查詢按鈕，系統(tǒng)解析出此道路沿線周邊的米粉店，并在圖中顯示(如圖9所示)。部分標(biāo)記點的具體查詢結(jié)果見表1。

圖7 判定點在折線緩沖區(qū)內(nèi)的矢量壓縮過程

圖8 米粉店標(biāo)記點位置

地物點ID地物點坐標(biāo)與道路實際最短距離/m判斷結(jié)果準(zhǔn)確與否1(25.28673,110.30118) 14.788是是2(25.28684,110.30288)21.713是是4(25.28428,110.30046)21.250是是5(25.28472,110.29797)32.028否是6(25.28355,110.29677)13.243是是9(25.28638,110.29854)144.574否是10(25.28743,110.29668)228.421否是

(2) 復(fù)雜道路情況。與上述試驗區(qū)相同，藥店標(biāo)記點位置如圖10所示，試驗結(jié)果如圖11所示，試驗具體數(shù)據(jù)見表2。

圖10 藥店標(biāo)記點位置

圖11 道路沿線緩沖區(qū)查詢結(jié)果

地物點ID地物點坐標(biāo)與道路實際最短距離/m判斷結(jié)果準(zhǔn)確與否1(25.27021,110.28420)22.098是是2(25.26985,110.28531)11.0是是3(25.26864,110.28285)10.036是是4(25.27002,110.28371)11.879是是7(25.26964,110.28183)15.962是是8(25.26921,110.28453)42.396否是9(25.27051,110.28308)60.942否是

通過上述試驗，可得出如下結(jié)論：

(1) 本文算法查詢準(zhǔn)確率高，適用于各種類型的折線形式。

(2) 計算效率高，冗余小。當(dāng)判斷出地物信息在道路沿線緩沖區(qū)內(nèi)，即停止計算。

(3) 僅利用道路節(jié)點和地物標(biāo)記點的經(jīng)緯度數(shù)據(jù)，通過夾角和歐氏距離即可進行計算。

4 結(jié) 語

本文提出了一種用于查詢道路沿線地物信息的矢量壓縮算法。試驗結(jié)果表明，該算法對折線節(jié)點多、折線錯綜復(fù)雜等情況，具有較好的適應(yīng)性，且在滿足高精度的同時，降低了計算量，顯著提高了計算效率。

[1] 沙薇,盛業(yè)華,楊林.基于GIS的高速公路沿線設(shè)施管理信息查詢系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機應(yīng)用與軟件,2009,26(1):112-114.

[2] 王滿,孫海燕.基于地圖代數(shù)的緩沖區(qū)分析算法的研究[J].測繪信息與工程,2009,34(3):33-34.

[3] 賴云波,孫棣華,廖孝勇，等.基于道路緩沖區(qū)分析的地圖匹配算法[J].計算機應(yīng)用研究,2011,28(9):3312-3314.

[4] 王少華,鐘耳順,盧浩，等.基于非均勻多級網(wǎng)格索引的矢量地圖疊加分析算法[J].地理與地理信息科學(xué),2013,29(3):17-20.

[5] 朱效民,趙紅超,劉焱，等.矢量地圖疊加分析算法研究[J].中國圖象圖形學(xué)報,2010,15(11):1696-1706.

[6] 薛勝,潘懋,王勇.多邊形疊置分析算法研究[J].計算機工程與應(yīng)用,2003(2):57-59.

[7] SUTHERLAND I E,HODGEMAN G W.Reentrant Polygon Clipping[J].Communications of the ACM,1974,17(1):32-42.

[8] LIANG Y,BARSKY B A.An Analysis and Algorithm for Polygon Clipping[J].Communications of the ACM,1983,26(11):868-877.

[9] FOLEYJ D,DAM A,FEINER S K,et al.Computer Graphics,Principles and Practice[M].Boston:Addison-Wesley,1990.

[10] 陳占龍,吳信才,吳亮，等.基于單調(diào)鏈和STR樹的簡單要素模型多邊形疊置分析算法[J].測繪學(xué)報,2010,39(1):102-108.

[11] 陳占龍,張丁文,吳亮，等.基于圖模型的多邊形自動并行構(gòu)建算法[J].計算機應(yīng)用研究,2012,29(5):1634-1636.

[12] 劉勇奎,高云,黃有群，等.一個有效的多邊形裁剪算法[J].軟件學(xué)報,2003,14(4):845-856.

[13] 崔爽,蘇鴻,葉良松,等.一種基于空間對象的緩沖區(qū)分析算法[J].地理與地理信息科學(xué),2011,27(1):38-41.

[14] 王家耀.空間信息系統(tǒng)原理[M].北京:科學(xué)出版社，2001:291-309.

[15] 鄔倫,劉瑜,張晶，等.地理信息系統(tǒng)——原理、方法和應(yīng)用[M].北京:科學(xué)出版社，2001:168-171.

AVectorCompressionAlgorithmforInformationSearchingonRoadPolyline

ZHANG Dan1,2，HU Bo1

(1. Yellow River Conservancy Technical Institute,Kaifeng 475004，China； 2. Key Laboratory of Mine Spatial Information Technologies,NASG,Henan Polytechnic University,Jiaozuo 454003，China)

P208

A

0494-0911(2017)09-0060-05

2017-06-21

2016年度國家重點研發(fā)計劃重點專項(2016YFC0803103)

張 丹(1980—)，男，碩士，講師，研究方向為測繪科學(xué)與技術(shù)。E-mail：40663113@qq.com

張丹，胡泊.適用于道路沿線信息查詢的矢量壓縮算法[J].測繪通報，2017(9)：60-64.

10.13474/j.cnki.11-2246.2017.0288.