俞 信,郭 毓,王 洋

(1.南京理工大學 自動化系，江蘇 南京 210094；2.中國科學院電子學研究所蘇州研究院，江蘇 蘇州 215000)

一種柵格化矢量地圖的拾取交互方法

俞 信1,郭 毓1,王 洋2

(1.南京理工大學 自動化系，江蘇 南京 210094；2.中國科學院電子學研究所蘇州研究院，江蘇 蘇州 215000)

針對紋理法渲染的柵格化矢量地圖難以直接進行交互的問題，設計了一種柵格化矢量地圖的拾取交互方法?；趯嶋H面型矢量頂點數(shù)目多、多邊形分離、空洞多邊形等特性，改進了傳統(tǒng)的射線求交判斷點是否在多邊形內(nèi)的算法，使其可適用于實際面型矢量拾??；同時，提出了一種基于半平面連續(xù)鏈的新型內(nèi)角和算法，可大幅降低傳統(tǒng)內(nèi)角和算法的計算量，實現(xiàn)了柵格化矢量地圖的拾取交互。應用不同復雜程度的矢量數(shù)據(jù)進行相關實驗，結果表明，在明顯提高矢量渲染效率的同時，避免了在三維場景下矢量渲染不貼地的情況下，可以實現(xiàn)矢量興趣要素拾取，且所提矢量拾取方法實時性良好，拾取響應時間只取決于矢量數(shù)據(jù)本身復雜度，與三維地形復雜度無關，可以滿足GIS的需求。

矢量地圖交互；要素拾取；柵格化；射線求交；內(nèi)角和

0 引 言

空間查詢和交互是地理信息系統(tǒng)(GIS)的必備功能，無論是二維還是三維GIS，現(xiàn)有的實現(xiàn)方法都是通過鼠標的點選方式獲取矢量要素的空間坐標，執(zhí)行矢量高亮顯示和屬性查詢操作[1-2]，這種方法的前提是場景中的矢量地圖是基于幾何法渲染的。文獻[3]從屏幕發(fā)出射線與地形節(jié)點進行相交運算獲取地理坐標，計算得到地理包圍矩形，繼而得到該地理包圍矩形內(nèi)的矢量要素數(shù)據(jù)。文獻[4]采用視點相關的數(shù)據(jù)動態(tài)調用策略，實現(xiàn)了視景體內(nèi)矢量線、面對象的動態(tài)查詢和檢索，此方法取決于三維地形數(shù)據(jù)的復雜度。文獻[5]提出了只考慮當前屏幕中可見矢量要素的方法，提高了拾取效率。

目前，三維場景下的矢量地圖渲染方法主要分為兩種：幾何法[6-8]和紋理法[9-10]。幾何法中，二維矢量與三維地形融合過程復雜，需要不斷計算頂點位置，在頂點之間進行插值，效率較低，不合理的插值會出現(xiàn)矢量數(shù)據(jù)的“懸空”或“入地”現(xiàn)象，難以確保矢量數(shù)據(jù)貼合地面[11]。紋理法將矢量數(shù)據(jù)柵格化為紋理后，通過紋理映射投影到三維地形上，無需考慮矢量數(shù)據(jù)貼地的問題，且效率較高，但較之幾何法，紋理法可能會導致在相機視距較小時出現(xiàn)邊緣走樣[12]。另外，針對矢量地圖交互問題，幾何法可以直接利用射線法與矢量模型節(jié)點作相交測試得到興趣要素，進行后續(xù)的高亮和屬性查詢等操作；而紋理法無法直接進行矢量地圖交互，其本質是利用柵格化后的地圖加載效率而舍棄了矢量的實時可交互性。相較于幾何法，紋理法的優(yōu)勢是其較高的渲染效率使矢量數(shù)據(jù)與三維地形完美的融合。

為此，設計了一種柵格化矢量地圖的交互方法，基于實際面型矢量頂點數(shù)目多、多邊形分離、“空洞”多邊形等特性，對普通的射線求交判斷點是否在多邊形中的算法進行了改進，提出了一種基于半平面連續(xù)鏈的新型內(nèi)角和算法，提高了拾取效率。此交互方法既保留了柵格化矢量地圖渲染快、貼合地面的優(yōu)點，又能進行拾取交互，解決了柵格化矢量地圖難以直接進行交互的問題。利用不同復雜度的矢量數(shù)據(jù)進行交互實驗后，在矢量地圖渲染效率明顯提高的前提下，拾取效率良好，證明所提方法可用于實際GIS系統(tǒng)。

1 柵格化矢量地圖拾取交互設計

1.1 坐標轉化

空間坐標的相互轉化是矢量地圖交互的基礎。矢量地圖拾取交互操作的第一步是鼠標點擊，點擊處獲取的是屏幕坐標，而大多數(shù)矢量數(shù)據(jù)存儲的坐標信息都是基于WGS84經(jīng)緯度坐標系的。因此，需將屏幕坐標轉換為常用的經(jīng)緯度坐標。

首先，從屏幕坐標系轉換到世界坐標系，轉換表達式為：

(1)

其中，Mmodel-view、Mprojection和Mscreen分別代表參與坐標變換的模型視點矩陣、投影矩陣和窗口矩陣。

接著，從世界坐標系轉換到經(jīng)緯度坐標系。經(jīng)度、高度和緯度的計算表達式如下：

L=tan-1(Y/X)

(2)

(3)

(4)

其中，X,Y,Z為世界坐標系的三個坐標；L,N,H為經(jīng)緯高三個分量。

1.2 拾取交互流程設計

與柵格數(shù)據(jù)相比，矢量數(shù)據(jù)最大的優(yōu)勢是支持空間分析以及屬性查詢。當采用紋理法渲染矢量數(shù)據(jù)時，矢量數(shù)據(jù)轉化為柵格數(shù)據(jù)，按照柵格的方式渲染至三維場景中，此時不能按照傳統(tǒng)的幾何法渲染的矢量地圖的交互方式實現(xiàn)拾取。文中設計的柵格化矢量地圖拾取交互方法流程如圖1所示。

圖1 柵格化矢量地圖拾取流程

對圖1有以下幾點說明：

(1)執(zhí)行包圍盒與點位置的包含關系判斷的原因是：當點不在矢量要素的包圍盒內(nèi)時，一定不在矢量要素中的多邊形中，當點位于包圍盒里時再執(zhí)行判斷算法，提高了計算效率。

(2)經(jīng)包圍盒的位置判斷得到矢量要素，若矢量要素的幾何類型為單一的多邊形時，無需分離其幾何體，只需執(zhí)行點是否在多邊形內(nèi)的判斷即可；若一個矢量要素包含多個幾何體時，則需分解要素，繼而執(zhí)行改進后的點在多邊形內(nèi)的判斷算法。

(3)由于矢量地圖拾取的唯一性，只需滿足點在多邊形內(nèi)即可獲得包含輸入點的幾何要素編號，即可跳出循環(huán)，提高檢索效率。

由圖1可知，柵格化矢量地圖的拾取交互問題轉化成為點是否在多邊形內(nèi)的判斷問題，拾取效率將取決于點在多邊形內(nèi)判斷算法的執(zhí)行效率。

2 問題描述

2.1 射線求交法存在的問題

傳統(tǒng)射線求交法[13]的基本原理為：對于普通凸多邊形而言，只要從所選點向左延伸一條射線，得到與多邊形的交點個數(shù)，若交點個數(shù)為奇，則該點在多邊形內(nèi)，否則該點不在多邊形內(nèi)。

傳統(tǒng)射線求交法適用于單一的多邊形，由于面型矢量數(shù)據(jù)的特殊結構，它不適用于實際面型矢量。如中國海南島，在地圖上與其他省份屬于分離的多邊形；南非內(nèi)的萊索托國，一個多邊形內(nèi)有一個或多個“空洞”。當在此類矢量地圖上進行拾取操作時，用戶需要將該矢量要素全部顯示為高亮，而不是點擊中國時，不顯示海南島。

2.2 內(nèi)角和算法的不足

內(nèi)角和的基本原理為：點Q與多邊形P的每條邊界構成的夾角之和若為±2π，則Q在P內(nèi)，否則，Q在P外。對于單一的，頂點數(shù)目較少的多邊形而言，內(nèi)角和算法簡單快捷，但是對于實際的矢量數(shù)據(jù)而言，多邊形頂點繁多，且無規(guī)則可言。計算每一個邊界內(nèi)角時需進行大量的反三角函數(shù)計算，既耗時又消耗計算機內(nèi)存，不利于實時交互。

3 改進的點在多邊形內(nèi)的判斷算法

3.1 改進的射線求交法

結合矢量數(shù)據(jù)特點，對點在多邊形內(nèi)的判斷算法進行改進，使得當點位于一個多邊形時可以檢索到其關聯(lián)多邊形，或者當點位于空洞多邊形時，判斷點不在多邊形中，改進算法主要步驟如下：

Step1：當一個矢量要素包含多個多邊形時，分離一個矢量要素中的所有幾何體，并遍歷所有幾何體；

五是建立了社會監(jiān)督制度。制定下發(fā)了 《天津市河道水生態(tài)環(huán)境社會監(jiān)督員聘請與管理辦法》《實行 “河長制”管理的河道“河長”公示牌設立工作要求》，全市共聘請社會監(jiān)督員290名，設立河長公示牌400個。向社會公布監(jiān)督電話，共受理河道水環(huán)境社會監(jiān)督投訴事項34件，辦結率100%。

Step2：設包含鼠標點擊處的多邊形數(shù)目為n，對于每個分離出來的多邊形都利用射線求交法進行判斷，當點位于該多邊形內(nèi)時，n加1；

Step3：只有當n=1時才認為該矢量要素被選中，返回其要素編號。

該改進方法將矢量要素解耦，得到多個無關聯(lián)的多邊形，繼而分別判斷多邊形與點的幾何關系。對于分離多邊形，鼠標點擊位置只可能在一個多邊形中，而對于有空洞的多邊形，點擊處可能落在空洞多邊形中，導致n大于1，只有當n為1時才代表點落在外圍的多邊形中且不在空洞多邊形中。

3.2 基于半平面連續(xù)鏈的新型內(nèi)角和算法

(1)基本概念。

引入半平面連續(xù)鏈[14]的概念，以檢測點Q為參考坐標系原點，在多邊形P中，位于點Q右邊的頂點組成的多邊形鏈稱為相對于Q點的右半平面連續(xù)鏈；位于點Q左邊的頂點組成的多邊形鏈稱為相對于Q點的左半平面連續(xù)鏈；位于點Q上邊的頂點組成的多邊形鏈稱為相對于Q點的上半平面連續(xù)鏈；位于點Q下邊的頂點組成的多邊形鏈稱為相對于Q點的下半平面連續(xù)鏈，如圖2所示。

圖2 半平面連續(xù)鏈

文獻[14]已證明引理：對于簡單多邊形的半平面連續(xù)鏈Lk～k+m，點Q與Lk～k+m上的每個邊界的夾角之和等于點Q與Lk～k+m上的兩個端點夾角，即Δθ(Lk～k+m)=∠PkQPk+m=Δθ(PkPk+m)。

(2)算法改進。

有了上述引理的理論基礎，可對多邊形內(nèi)角和算法進行改進，不需要針對多邊形的每條邊界都計算邊界內(nèi)角，而只需將多邊形P分割成n條半平面連續(xù)鏈。如圖2中，豎直的虛線將多邊形P分成了左右半平面連續(xù)鏈，橫向的虛線將多邊形P分成了上下半平面連續(xù)鏈。

相鄰多邊形鏈的相鄰頂點與Q的夾角的計算方法為：

多邊形內(nèi)角即為所有多邊形鏈內(nèi)角與相鄰多邊形鏈的相鄰頂點與點Q的夾角之和，以圖2中多邊形為例，則多邊形內(nèi)角為：

∑Δθ(P)=Δθ(L2～5)+Δθ(L6～9)+Δθ(L10～11)+Δθ(L12～1)+∠P1QP2+∠P5QP6+ ∠P9QP10+∠P11QP12

(7)

若∑Δθ(P)=0，則點Q位于多邊形P外，否則，點Q位于多邊形P內(nèi)。

4 實 驗

4.1 實驗環(huán)境

實驗環(huán)境：Intel? Core(TM) i5 CPU、1.9 GHz、內(nèi)存8 GB，操作系統(tǒng)為Windows 7，開發(fā)環(huán)境為Visual Studio 2013，利用C++實現(xiàn)。實驗數(shù)據(jù)采用格式為shapefile的矢量數(shù)據(jù)。

4.2 三維場景下柵格化矢量地圖拾取可視化效果

圖3為幾何法和紋理法渲染某地區(qū)矢量時矢量要素的拾取可視化效果。可見，在二維矢量與三維地形的融合過程中，幾何法的渲染結果出現(xiàn)了斷線情況，而紋理法未出現(xiàn)。圖3為文中算法在拾取彼此分離或有空洞的矢量要素時的可視化效果，驗證了算法同樣適用于特殊矢量要素。

圖3 矢量要素的拾取可視化效果

4.3 矢量要素拾取效率對比

以三種不同復雜度的面型矢量為實驗數(shù)據(jù)，進行拾取響應時間測試實驗，拾取響應時間定義為在屏幕上點擊后到相應矢量要素高亮顯示的時間。圖4為三種不同復雜度的矢量數(shù)據(jù)分別使用文中改進的射線求交法、新型內(nèi)角和算法的拾取響應時間。

圖4(a)為復雜度最低的矢量的拾取響應時間，可見射線求交法的拾取效率遠比新型內(nèi)角和算法高，這是因為當要素數(shù)目較少時，內(nèi)角和算法需要計算反正切函數(shù)，消耗時間較長，而射線求交法的計算次數(shù)較少；當矢量復雜度上升時，由圖4(b)與(c)可知，新型內(nèi)角和算法的拾取響應時間基本維持不變，在0.2～0.3 s之間，而射線求交法的拾取響應時間逐漸提升，當矢量數(shù)據(jù)較復雜時，拾取響應時間在1.2 s左右。實驗結果表明：對于常用的矢量數(shù)據(jù)而言，改進的射線求交法的拾取響應時間在幾十毫秒左右，可以供用戶使用，而當矢量數(shù)據(jù)復雜度提升時，新型內(nèi)角和算法拾取效率更高，滿足用戶實時性需求。

圖4 三種不同復雜度的矢量數(shù)據(jù)拾取響應時間

4.4 內(nèi)角和算法改進前后復雜度分析

對于一個頂點數(shù)為N的多邊形P而言，普通的內(nèi)角和算法需要計算N次反正切函數(shù)、N次二維向量叉乘、N次二維向量點乘以及N次二維向量求模函數(shù)。當使用改進的內(nèi)角和算法時，假設將多邊形P分成n條半平面連續(xù)鏈，則由式(5)、(6)可知，此時需要計算2n次反正切函數(shù)、2n次二維向量叉乘、2n次二維向量點乘以及2n次二維向量求模函數(shù)。對于實際矢量要素中的多邊形而言，N遠大于2n。因此，在對普通內(nèi)角和算法改進后，判斷點在多邊形內(nèi)的效率得到大幅提升。

對于不同數(shù)目頂點的多邊形，使用傳統(tǒng)的內(nèi)角和算法和改進的內(nèi)角和算法，程序響應時間如圖5所示。

圖5 內(nèi)角和算法改進前后響應時間對比

可見，當多邊形頂點數(shù)目較小時，改進的內(nèi)角和算法效率提升得不明顯，當頂點數(shù)目較大時，改進的內(nèi)角和算法的計算效率明顯比傳統(tǒng)的內(nèi)角和算法高，而且當頂點數(shù)目在5 000以上時，傳統(tǒng)的內(nèi)角和算法所需的時間過長，不適合實時拾取，而改進的內(nèi)角和算法能滿足實時拾取的要求。

5 結束語

文中設計了一種柵格化矢量地圖的交互方法，基于實際面型矢量頂點數(shù)目多、多邊形分離、空洞多邊形等特性，改進了傳統(tǒng)的射線求交判斷點是否在多邊形內(nèi)的算法；同時，提出了一種基于半平面連續(xù)鏈的新型內(nèi)角和算法，實現(xiàn)了柵格化矢量地圖的拾取交互。通過對三種復雜度不同的矢量進行拾取實驗后，驗證了所提算法的有效性。實驗結果表明，該算法拾取效率良好，且拾取響應時間只取決于矢量數(shù)據(jù)本身的復雜度，與三維地形復雜度無關，可以供三維GIS使用。

[1]YangL,ZhangLQ,KangZZ,etal.Anefficientrenderingmethodforlargevectordataonlargeterrainmodels[J].ScienceChinaInformationSciences,2010,53(6):1122-1129.

[2]KerstingO,D?llnerJ.Interactive3DvisualizationofvectordatainGIS[C]//ProceedingsoftheACMworkshoponadvancesingeographicinformationsystems.NewYork,NY,USA:AssociationforComputingMachinery,2002:107-112.

[3] 康 來,趙 健,宋漢辰,等.面向二維GIS矢量數(shù)據(jù)三維可視化的地形匹配技術研究[J].計算機科學,2009,36(11):262-265.

[4] 孫文彬,單士剛,白建軍,等.實時柵格化的全球矢量數(shù)據(jù)可視化及交互操作[J].中國礦業(yè)大學學報,2013,42(5):845-850.

[5]ZhiY,GaoY,WuL.Animprovedalgorithmforvectordatarenderinginvirtualterrainvisualization[C]//Procof2013 21stinternationalconferenceonIEEE.[s.l.]:IEEE,2013.

[6]WangX,LiuJ,BiJ.Renderingofvectordataon3Dvirtuallandscapes[C]//Procof2009 1stinternationalconferenceoninformationscienceandengineering.Piscataway,NJ,USA:IEEEComputerSociety,2009:2125-2128.

[7]SunW,ShanS,FengC.Geometry-basedmappingofvectordataandDEMbasedonhierarchicallongitude/latitudegrids[C]//Procof2010 2ndinternationalconferenceongeoscienceandremotesensing.Piscataway,NJ,USA:IEEEComputerSociety,2010:215-218.

[8]WangS,ZhongE,LuH.Aneffectivealgorithmforlinesandpolygonsoverlayanalysisusinguniformspatialgridindexing[C]//Procof2015 2ndIEEEinternationalconferenceonspatialdataminingandgeographicalknowledgeservices.Piscataway,NJ,USA:IEEEComputerSociety,2015:175-179.

[9]ZhangX,SuiZ,WuL.Aprocessingandschedulingmethodforvectorrenderinginglobal3DGIS[C]//Procof2011 19thinternationalconferenceongeoinformatics.[s.l.]:IEEE,2011.

[10] 李 融,鄭文庭.三維地形高質量實時矢量疊加繪制[J].計算機輔助設計與圖形學學報,2011,23(7):1106-1114.

[11]XuY,SuiZ,WengJ.Visualizationmethodsofvectordataonadigitalearthsystem[C]//Procof2010 18thinternationalconferenceongeoinformatics.Piscataway,NJ,USA:IEEEComputerSociety,2010:1-5.

[12] 陳 鴻,湯曉安,謝耀華,等.基于視點相關透視紋理的矢量數(shù)據(jù)在三維地形上的疊加繪制[J].計算機輔助設計與圖形學學報,2010,22(5):753-761.

[13]DingJ,WangQ,WuK,etal.ThestudyofrobustalgorithmfororientationandpointinclusionqueryforpolygoninGIS[C]//Procof2011internationalconferenceonremotesensing,environmentandtransportationengineering.Piscataway,NJ,USA:IEEEComputerSociety,2011:2756-2760.

[14] 丁 健.基于GIS的野戰(zhàn)給水保障輔助決策關鍵算法研究[D].北京:中國科學院研究生院,2005.

A Picking Interaction Method of Rasterized Vector Map

YU Xin1,GUO Yu1,WANG Yang2

(1.Department of Automation,Nanjing University of Science and Technology,Nanjing 210094,China; 2.Institute of Electronics of Chinese Academy of Sciences,Suzhou 215000,China)

Aiming at the problem that the vector map rendered based on texture is difficult to realize the interaction,an interactive method of the rasterized vector map is designed.Based on the characteristic of polygonal vector which has a great quantity of vertices,separate polygon and holey polygon,the traditional ray intersection method determining whether a point is in a polygon is improved to apply to polygonal vector.Meanwhile,an interior angle summation based on half-plane continuous chain which could reduce the computation of the traditional interior algorithm is proposed.The experiment is done by using vector data with different degrees of complexity.The result shows that the efficiency of rendering based on rasterization is significantly increased and the bad overlaying performance of vector rendering in 3D scene is improved.Vector map interaction could be realized in this case.The proposed interaction method which is only according to the degrees of complexity of vector data and has nothing to do with the degrees of complexity of terrain,guarantees favorable performance of real-time to meet the need of GIS.

vector map interaction;feature picking;rasterization;ray-intersection;interior angle summation

2015-12-27

2016-04-21

時間：2016-09-19

國家自然科學基金資助項目(61473152)；南京理工大學研究生創(chuàng)新實踐計劃項目

俞 信(1991-)，男，碩士研究生，研究方向為時空大數(shù)據(jù)可視化技術；郭 毓，教授，博士，研究方向為智能控制、圖像處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0839.020.html

TP301

A

1673-629X(2016)10-0118-05

10.3969/j.issn.1673-629X.2016.10.026