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

俞 信,郭 毓,王 洋

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

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

俞 信1,郭 毓1,王 洋2

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

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

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

0 引 言

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

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

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

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

1.1 坐標轉化

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

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

(1)

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

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

L=tan-1(Y/X)

(2)

(3)

(4)

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

1.2 拾取交互流程設計

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

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

對圖1有以下幾點說明：

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

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

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

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

2 問題描述

2.1 射線求交法存在的問題

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

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

2.2 內角和算法的不足

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

3 改進的點在多邊形內的判斷算法

3.1 改進的射線求交法

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

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

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

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

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

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

3.2 基于半平面連續鏈的新型內角和算法

(1)基本概念。

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

圖2 半平面連續鏈

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

(2)算法改進。

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

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

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

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

(7)

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

4 實 驗

4.1 實驗環境

實驗環境：Intel? Core(TM) i5 CPU、1.9 GHz、內存8 GB，操作系統為Windows 7，開發環境為Visual Studio 2013，利用C++實現。實驗數據采用格式為shapefile的矢量數據。

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

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

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

4.3 矢量要素拾取效率對比

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

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

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

4.4 內角和算法改進前后復雜度分析

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

對于不同數目頂點的多邊形，使用傳統的內角和算法和改進的內角和算法，程序響應時間如圖5所示。

圖5 內角和算法改進前后響應時間對比

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

5 結束語

文中設計了一種柵格化矢量地圖的交互方法，基于實際面型矢量頂點數目多、多邊形分離、空洞多邊形等特性，改進了傳統的射線求交判斷點是否在多邊形內的算法；同時，提出了一種基于半平面連續鏈的新型內角和算法，實現了柵格化矢量地圖的拾取交互。通過對三種復雜度不同的矢量進行拾取實驗后，驗證了所提算法的有效性。實驗結果表明，該算法拾取效率良好，且拾取響應時間只取決于矢量數據本身的復雜度，與三維地形復雜度無關，可以供三維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矢量數據三維可視化的地形匹配技術研究[J].計算機科學,2009,36(11):262-265.

[4] 孫文彬,單士剛,白建軍,等.實時柵格化的全球矢量數據可視化及交互操作[J].中國礦業大學學報,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] 陳 鴻,湯曉安,謝耀華,等.基于視點相關透視紋理的矢量數據在三維地形上的疊加繪制[J].計算機輔助設計與圖形學學報,2010,22(5):753-761.

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

[14] 丁 健.基于GIS的野戰給水保障輔助決策關鍵算法研究[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)；南京理工大學研究生創新實踐計劃項目

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

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