朱 荔，鄭 昊

國(guó)產(chǎn)平臺(tái)上GIS矢量繪制的多線程改造

朱 荔1，鄭 昊2

(1. 中國(guó)電子科技集團(tuán)第十五研究所，北京市 100083；2. 中國(guó)電子科技集團(tuán)第十五研究所，北京市 100083)

為解決目前國(guó)產(chǎn)基礎(chǔ)軟硬件平臺(tái)上GIS矢量地圖繪制性能問(wèn)題，本文嘗試基于矢量瓦片技術(shù)，對(duì)MGIS的矢量繪制進(jìn)行多線程改造，其中包括對(duì)矢量數(shù)據(jù)模型的瓦片化改造以支持并行計(jì)算。實(shí)驗(yàn)結(jié)果表明，本文提出的多線程改造技術(shù)能夠大幅提升矢量地圖可視化性能。

地理信息系統(tǒng)；矢量地圖可視化；矢量瓦片；多線程

0 引言

描述人類活動(dòng)的信息有60%左右與位置相關(guān)[1]，在信息化的時(shí)代，國(guó)防、政府、企業(yè)和大眾都離不開地理信息系統(tǒng)（Geographic Information System，縮寫為GIS）[2]。

MGIS是一個(gè)專業(yè)面向國(guó)防領(lǐng)域的系列化地理信息系統(tǒng)平臺(tái)，其基于商業(yè)化軟硬件平臺(tái)的版本目前已在國(guó)防領(lǐng)域得到了廣泛的應(yīng)用。為確保關(guān)鍵領(lǐng)域信息系統(tǒng)安全，提供支持國(guó)產(chǎn)基礎(chǔ)軟硬件平臺(tái)的MGIS系列產(chǎn)品是十分必要的。

矢量地圖是地理信息系統(tǒng)中最復(fù)雜、處理難度最大的數(shù)據(jù)，相對(duì)于柵格地圖，它具有精確度更高、數(shù)據(jù)顯示不受分辨率影響、包含的關(guān)系數(shù)據(jù)可以使得一些空間分析更有效率（例如網(wǎng)絡(luò)分析）、數(shù)據(jù)所占據(jù)的存儲(chǔ)空間相對(duì)較小、便于編輯修改等優(yōu)點(diǎn)[3][4]。

由于商用軟硬件平臺(tái)的成熟性和高性能，MGIS只需采用串行計(jì)算的體系結(jié)構(gòu)，在矢量地圖顯示、漫游、尺度切換等各方面就能滿足用戶使用要求。但是，目前的國(guó)產(chǎn)基礎(chǔ)軟硬件（包括CPU/GPU的計(jì)算能力、操作系統(tǒng)對(duì)顯卡等外設(shè)的驅(qū)動(dòng)能力、二三維圖形支撐環(huán)境的圖形繪制性能、國(guó)產(chǎn)整機(jī)的綜合性能等）與主流商用軟硬件相比還存在不小差距[5]，如果只是將基于商用基礎(chǔ)軟硬件平臺(tái)的MGIS簡(jiǎn)單移植到國(guó)產(chǎn)基礎(chǔ)軟硬件平臺(tái)上，矢量地圖顯示、漫游、尺度切換等方面指標(biāo)將達(dá)不到用戶使用要求，我們的實(shí)踐已經(jīng)證明了這點(diǎn)。

考慮到現(xiàn)有國(guó)產(chǎn)CPU一般都是多核，這為我們解決國(guó)產(chǎn)平臺(tái)上MGIS矢量繪制性能問(wèn)題提供了一種可能——將最耗時(shí)的矢量繪制進(jìn)行多線程改造，以充分利用現(xiàn)有國(guó)產(chǎn)多核CPU的并行計(jì)算能力。

本文主要針對(duì)國(guó)產(chǎn)基礎(chǔ)軟硬件平臺(tái)上MGIS的矢量地圖繪制展開多線程改造，以期對(duì)解決國(guó)產(chǎn)平臺(tái)上MGIS矢量繪制性能問(wèn)題有所突破。

1 多線程改造與矢量瓦片

1.1地理信息系統(tǒng)體系結(jié)構(gòu)分析

一個(gè)通常的地理信息系統(tǒng)體系結(jié)構(gòu)如圖一所示[6,7]

圖1 一個(gè)典型的地理信息系統(tǒng)體系結(jié)構(gòu)Fig.1 a typical architecture of GIS

圖中各模塊具體介紹如下：

（1）基礎(chǔ)軟件層：包括操作系統(tǒng)、數(shù)據(jù)管理系統(tǒng)（文件系統(tǒng)、關(guān)系數(shù)據(jù)庫(kù)等）、圖形支撐環(huán)境（比如GD1/GDI+、GTK、QT、OpenGL等）；

（2）數(shù)據(jù)訪問(wèn)對(duì)象：是中間件層，它屏蔽底層數(shù)據(jù)存儲(chǔ)層軟件（比如不同關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)之間及同一數(shù)據(jù)庫(kù)管理系統(tǒng)不同版本之間）之間的差異，對(duì)上層提供統(tǒng)一的數(shù)據(jù)對(duì)象訪問(wèn)接口；

（3）數(shù)據(jù)層：地理信息庫(kù)負(fù)責(zé)地理信息的組織與管理；

（4）空間數(shù)據(jù)引擎層：包括負(fù)責(zé)讀寫地理信息庫(kù)的空間數(shù)據(jù)庫(kù)訪問(wèn)引擎、元數(shù)據(jù)及空間數(shù)據(jù)在內(nèi)存與本地緩存一體化存儲(chǔ)管理與調(diào)度的數(shù)據(jù)緩存共享區(qū)、以及對(duì)緩存共享區(qū)數(shù)據(jù)進(jìn)行讀寫的緩存共享數(shù)據(jù)訪問(wèn)引擎；

（5）功能處理層：提供地理信息系統(tǒng)常用功能，主要包括數(shù)據(jù)裝載、數(shù)據(jù)處理（編輯、拓?fù)潢P(guān)系處理、空間索引與矢量金字塔生成、拼接裁剪等）、可視化、屬性與空間查詢（含屬性查詢、空間查詢、基于地名的查詢等）、空間分析計(jì)算（路徑規(guī)劃、地形分析計(jì)算、緩沖區(qū)分析、疊置分析、空間計(jì)算等）、綜合查詢分析、制圖輸出（含可視化顯示、打印等）。各功能一般以組件方式實(shí)現(xiàn)，便于功能模塊間的集成與協(xié)同工作；

（6）主控：為功能處理層各功能模塊的集成提供統(tǒng)一的集成框架，負(fù)責(zé)統(tǒng)一獲取用戶的交互操作、各功能組件自身的狀態(tài)、各功能組件的處理結(jié)果的狀態(tài)，并將對(duì)應(yīng)的處理通過(guò)消息交給相應(yīng)的功能組件去處理，各功能組件將處理結(jié)果以消息的方式返回給主控，通過(guò)這樣實(shí)現(xiàn)功能組件間的集成與協(xié)同工作；

（7）交互界面:提供人機(jī)交互接口，如鼠標(biāo)操作、菜單選取、在對(duì)話框中輸入信息等。

矢量地圖顯示、漫游、尺度切換的性能主要與矢量繪制密切相關(guān)。典型的矢量繪制的流程是：

（1）交互界面向主控發(fā)布任務(wù)；（2）主控向繪制模塊分派任務(wù)；

（3）繪制模塊向空間數(shù)據(jù)引擎請(qǐng)求數(shù)據(jù)；

（4）空間數(shù)據(jù)引擎從數(shù)據(jù)層得到數(shù)據(jù)；

（5）繪制模塊進(jìn)行圖形繪制，并將繪制結(jié)果顯示在交互界面中。

在上述流程中，空間數(shù)據(jù)引擎從數(shù)據(jù)層得到數(shù)據(jù)、繪制模塊進(jìn)行圖形繪制兩個(gè)步驟是最具有多線程改造的潛力，而對(duì)它們進(jìn)行多線程改造必將伴隨著對(duì)數(shù)據(jù)模型的改造[2]。

1.2地理數(shù)據(jù)模型改造與矢量瓦片

Richard Healey等在進(jìn)行支持并行計(jì)算的地理信息系統(tǒng)設(shè)計(jì)時(shí)，提出過(guò)一種稱之為“多區(qū)塊”的矢量數(shù)據(jù)結(jié)構(gòu)。所謂“多區(qū)塊”是用指一系列彼此獨(dú)立的規(guī)則網(wǎng)格來(lái)覆蓋一個(gè)區(qū)域[2]。這與當(dāng)今在許多在線上商用地理信息系統(tǒng)中使用的“地圖瓦片”概念有相似的部分，盡管“地圖瓦片”的本質(zhì)是柵格地圖，是將矢量地圖在服務(wù)器端柵格化形成圖片并在各個(gè)比例尺上進(jìn)行切分所形成的，為的是解決初期線上地理信息系統(tǒng)的客戶端瀏覽器常常不支持繪圖功能以及網(wǎng)絡(luò)帶寬不支持快速的全圖傳輸?shù)膯?wèn)題。隨著客戶端瀏覽器的繪圖能力由于一些繪圖插件（如WebGL）的出現(xiàn)得到提高，以及用戶對(duì)線上地圖的編輯性要求的提高，“矢量瓦片”的概念被提了出來(lái)。應(yīng)該說(shuō)，“矢量瓦片”雖然并不是為了解決并行計(jì)算問(wèn)題而誕生，卻是最接近Richard Healey等人提出的“多區(qū)塊”數(shù)據(jù)結(jié)構(gòu)的概念。

“矢量瓦片”的思想與“地圖瓦片”類似，是將矢量數(shù)據(jù)組織成類似的、按照地理位置組織地理要素的小片，并統(tǒng)合各比例尺數(shù)據(jù)進(jìn)一步形成矢量瓦片金字塔，以應(yīng)對(duì)多比例尺的切換問(wèn)題。不過(guò)矢量瓦片比起地圖瓦片更為復(fù)雜，需要考慮格式標(biāo)準(zhǔn)、瓦片劃分體系、細(xì)節(jié)概括程度、基本幾何要素、圖層組織、屬性信息組織等等因素[4]。當(dāng)前一個(gè)比較成熟的矢量瓦片體系是來(lái)自Mapbox的矢量瓦片服務(wù)。

Mapbox的一個(gè)矢量瓦片內(nèi)部包含一個(gè)或幾個(gè)圖層，每個(gè)圖層都有一個(gè)版本號(hào)和名字，并記錄了其覆蓋的地理范圍。圖層內(nèi)部有多個(gè)地理要素并存有這些地理要素所擁有的全部非幾何屬性的名稱和這些非幾何屬性的值。每個(gè)地理要素除了需要指向這些非幾何屬性的鍵和值外，還需要標(biāo)明id、要素類型以及幾何信息。其中，幾何信息是以指令信息和參數(shù)信息所組成的。指令信息共有三種：MoveTo、LineTo、和ClosePath。最初的起點(diǎn)設(shè)為（0,0），MoveTo有兩個(gè)參數(shù)（dx，dy），它表示從當(dāng)前點(diǎn)（x，y）直接移動(dòng)到（x+dx, y+dy）畫點(diǎn)，并將新起點(diǎn)設(shè)為（x+dx, y+dy）；LineTo也有兩個(gè)參數(shù)（dx，dy），它表示從當(dāng)前點(diǎn)（x，y）移動(dòng)到（x+dx, y+dy）畫點(diǎn)，并將（x，y）與（x+dx,y+dy）連線，起點(diǎn)不變；ClosePath沒(méi)有參數(shù)，它表示從當(dāng)前點(diǎn)（x，y）回到起點(diǎn)并連線。這三條指令相互配合，能夠表示地理要素中可能出現(xiàn)的所有幾何類型，并且能夠被機(jī)器解讀，再與符號(hào)搭配表對(duì)照，從而繪制出相應(yīng)的幾何圖形[8]。如果可以將這項(xiàng)技術(shù)應(yīng)用于改造現(xiàn)有的關(guān)系數(shù)據(jù)庫(kù)，不但可以降低多線程改造的難度，而且可以大大減少在讀取數(shù)據(jù)時(shí)的I/O次數(shù)，從而提升繪制性能。

根據(jù)上述思路，我們擬以矢量瓦片技術(shù)為基礎(chǔ)，并對(duì)繪制模塊進(jìn)行多線程改造的方法來(lái)對(duì)基于國(guó)產(chǎn)軟硬件基礎(chǔ)平臺(tái)的MGIS進(jìn)行優(yōu)化。

2 MGIS矢量繪制的多線程改造實(shí)驗(yàn)

2.1實(shí)驗(yàn)環(huán)境

本文所采用的實(shí)驗(yàn)環(huán)境如表1所示。

2.2設(shè)計(jì)方案

MGIS矢量繪制多線程改造方案如圖2所示。

表1 實(shí)驗(yàn)環(huán)境Tab.1 experiment context

圖2 MGIS矢量繪制多線程改造方案Fig.2 the design of the multithreading modification of MGIS vector drawing

其中：

（1）界面線程為主線程，負(fù)責(zé)接收用戶的交互輸入、將內(nèi)存中的圖像進(jìn)行貼圖和保存在本地緩存中；

（2）共有四個(gè)繪制線程，負(fù)責(zé)按矢量瓦片塊數(shù)據(jù)繪制成圖像，并寫入內(nèi)存的圖像緩沖區(qū)中；

（3）一個(gè)后臺(tái)運(yùn)行的注記線程，負(fù)責(zé)地圖注記的繪制與壓蓋處理；

（4）一個(gè)空間數(shù)據(jù)讀取線程，負(fù)責(zé)從本地緩存中按順序依次讀取地圖瓦片、矢量瓦片和從地理信息庫(kù)中讀取矢量瓦片數(shù)據(jù)；

（5）建立0-22級(jí)基于矢量瓦片的多尺度矢量數(shù)據(jù)庫(kù)。

2.3關(guān)鍵算法

原型系統(tǒng)主要涉及到的算法是矢量瓦片的生成算法。對(duì)于提取出的原始地理數(shù)據(jù)，首先將其處理成各比例尺所對(duì)應(yīng)的地圖的矢量數(shù)據(jù)，在該過(guò)程中須經(jīng)歷過(guò)濾和簡(jiǎn)化，即預(yù)處理；再切分空間區(qū)域；然后對(duì)每一個(gè)比例尺的每一個(gè)圖層的每一個(gè)地理要素進(jìn)行計(jì)算，判斷他們與該比例尺的哪些瓦片相關(guān)聯(lián)（穿過(guò)哪些瓦片或在瓦片內(nèi)部），對(duì)橫跨兩個(gè)或以上的地理要素按照瓦片的邊緣進(jìn)行切分，再放入記錄中重新進(jìn)行判斷，直到取出的要素只在一瓦片內(nèi)部，則將其放入所屬的瓦片空間中。其過(guò)程如圖3所示：

圖3 矢量瓦片生成流程Fig.3 the process of tiling vector data

該過(guò)程中的要點(diǎn)在于1.計(jì)算某個(gè)地理要素與哪些瓦片關(guān)聯(lián)（穿過(guò)哪些瓦片或在瓦片內(nèi)部）；2.將橫跨多個(gè)瓦片的地理要素按瓦片邊緣進(jìn)行切分。

2.3.1 計(jì)算某個(gè)地理要素與哪些瓦片關(guān)聯(lián)的算法

對(duì)于某個(gè)比例尺下的點(diǎn)要素來(lái)說(shuō)，用點(diǎn)的橫坐標(biāo)除以該比例尺下瓦片的寬度，得到的數(shù)值取整加一，得到所屬瓦片的列數(shù)；用點(diǎn)的縱坐標(biāo)除以該比例尺下瓦片的寬度，得到的數(shù)值取整加一，得到所屬瓦片的行數(shù)。

對(duì)于某個(gè)比例尺下的線要素來(lái)說(shuō)，對(duì)非閉合弧段首先按照點(diǎn)要素的方法得出除終點(diǎn)、前后兩點(diǎn)的x值均小于自身x值及前后兩點(diǎn)的y值均小于自身這三類特殊點(diǎn)以外的其他節(jié)點(diǎn)相關(guān)的瓦片行列號(hào)；對(duì)于這三類特殊點(diǎn)，則需考察其前一個(gè)節(jié)點(diǎn)的坐標(biāo)值情況，若其x值小于該特殊點(diǎn)的x值，則計(jì)算該特殊點(diǎn)所關(guān)聯(lián)的瓦片時(shí)，如果用點(diǎn)的橫坐標(biāo)除以該比例尺下瓦片的寬度得到的數(shù)值為整數(shù)，則按照普通的點(diǎn)要素得到的相關(guān)瓦片的列數(shù)要減一才是該特殊點(diǎn)的所在瓦片的列數(shù)，如不為整數(shù)，則按照非特殊點(diǎn)處理，如果前一節(jié)點(diǎn)的y值小于特殊點(diǎn)y值，則對(duì)行數(shù)也需要做類似的處理；對(duì)閉合弧段，則要用同樣方式處理前后兩點(diǎn)的x值均小于自身x值及前后兩點(diǎn)的y值均小于自身的兩類特殊點(diǎn)。其次，找出兩端點(diǎn)相關(guān)聯(lián)的瓦片不相鄰的線段，計(jì)算以兩端點(diǎn)相關(guān)瓦片作為兩對(duì)角方格的網(wǎng)格中所有邊界所在的直線與線段的交點(diǎn)，按照將x值從小到大的方式排列，依次得出線段穿過(guò)了哪些瓦片的邊界，如果交點(diǎn)并不是瓦片的角點(diǎn)，則線段與所穿過(guò)的邊界兩邊的瓦片都相關(guān)；如果恰好是角點(diǎn)，則取中心點(diǎn)離上一個(gè)計(jì)算出的交點(diǎn)（若該點(diǎn)為線段的第一個(gè)交點(diǎn)，則考察線段的起點(diǎn)）最近的那個(gè)瓦片為關(guān)聯(lián)瓦片。

對(duì)于面要素來(lái)說(shuō)，首先計(jì)算其邊界節(jié)點(diǎn)相關(guān)的瓦片行列號(hào)，得到x的最大值和最小值、y的最大值和最小值，并計(jì)算在x=xmin，y=ymin，x=xmax，y=ymax所圍成的瓦片網(wǎng)格中，有哪些瓦片的角點(diǎn)在圖形之中，如果這些在圖形內(nèi)部的角點(diǎn)既不在圖形的邊上也不在圖形的角點(diǎn)上，則這些角點(diǎn)四周的瓦片都與該圖形相關(guān)；若這樣的角點(diǎn)在圖形的邊上，則用線要素的方法計(jì)算與這條邊相關(guān)聯(lián)的瓦片，這些瓦片與該圖形關(guān)聯(lián)；若這樣的角點(diǎn)恰好在圖形的角點(diǎn)上，則用線要素的方法計(jì)算與該角點(diǎn)相連的兩邊的關(guān)聯(lián)瓦片，這些瓦片與該圖形關(guān)聯(lián)。

2.3.2 將橫跨多個(gè)瓦片的地理要素按瓦片邊緣進(jìn)行切分的算法

對(duì)于某個(gè)比例尺下的線要素，當(dāng)它與多個(gè)瓦片相關(guān)聯(lián)時(shí)，隨意找這條弧段中與兩個(gè)以上瓦片相關(guān)聯(lián)的一條線段，計(jì)算它與其中存在公共邊界的兩個(gè)瓦片的公共邊界的交點(diǎn)，根據(jù)交點(diǎn)將弧段分成起點(diǎn)-交點(diǎn)、交點(diǎn)-終點(diǎn)兩條弧段。

對(duì)于某個(gè)比例尺下的面要素，首先尋找與兩個(gè)瓦片相關(guān)聯(lián)的邊，計(jì)算這條邊與這兩個(gè)瓦片公共邊界的交點(diǎn)，然后找出另一條與這條公共邊界所在直線相交的邊，計(jì)算出交點(diǎn)，根據(jù)交點(diǎn)將圖形劃分為起點(diǎn)-交點(diǎn)1-交點(diǎn)2-起點(diǎn)、起點(diǎn)-交點(diǎn)2-交點(diǎn)1-起點(diǎn)兩個(gè)圖形。

3 實(shí)驗(yàn)結(jié)果

優(yōu)化前后二維地圖可視化實(shí)驗(yàn)結(jié)果對(duì)比如表2所示。

可以看出，國(guó)產(chǎn)平臺(tái)上的MGIS優(yōu)化后所達(dá)到的性能指標(biāo)與優(yōu)化前相比，整體性能提升一倍左右。

表2 優(yōu)化前后二維地圖可視化實(shí)驗(yàn)結(jié)果對(duì)比Tab.2 performance comparison: before optimization vs after optimization

4 結(jié)果與討論

綜上所述，國(guó)產(chǎn)平臺(tái)上的MGIS經(jīng)過(guò)優(yōu)化后所達(dá)到的性能指標(biāo)與優(yōu)化前相比，整體性能有大幅提升，但與用戶要求仍然存在一些差距。我們認(rèn)為可能的改進(jìn)工作將圍繞以下兩點(diǎn)：

（1）空間數(shù)據(jù)引擎的多線程改造；

（2）對(duì)矢量數(shù)據(jù)模型的改造以支持基于CPU/ GPU的異構(gòu)計(jì)算，以充分發(fā)揮GPU在二維可視化特別是符號(hào)化時(shí)的硬件加速能力。

相信在未來(lái)通過(guò)以上兩點(diǎn)的優(yōu)化，基于國(guó)產(chǎn)基礎(chǔ)軟硬件的GIS的矢量地圖顯示、漫游、尺度切換的性能還將得到進(jìn)一步的提升。

[1] Hahmann S, Burghardt D. How much information is geospatially referenced? Networks and cognition[J]. International Journal of Geographical Information Science, 2013, 27(6): 1171-1189.

[2] Healey, R., Dowers, S., Gittings, B., & Mineter, M. J. Parallel processing algorithms for GIS[M]. CRC Press, 1997.

[3] Chen F, Ren H. Comparison of vector data compression algorithms in mobile GIS[C]. Computer Science and Information Technology (ICCSIT), 2010 3rd IEEE International Conference on. IEEE, 2010, 1: 613-617.

[4] Ingensand J, Nappez M, Moullet C, et al. Implementation of tiled vector services: a case study[OL]. [2016-5-27].

張曉清, 龔波, 田麗韞, 等. 國(guó)產(chǎn)自主可控應(yīng)用性能優(yōu)化研究[J]. 軟件, 2015, 36(2): 5-9.

[5] ZHANG X Q, GONG B, TIAN L Y, et al. Study on the performance optimization of application running on the platform built with Chinese owned technology[J]. Software, 2015, 36(2): 5-9.

[6] 賈鵬, 王雅楠. 地理信息系統(tǒng)數(shù)據(jù)庫(kù)設(shè)計(jì)的研究[J]. 計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展2004, 2004.

JIA P, WANG Y N. The research on the design of GIS database[J]. Progress of Computer Technology and Application in 2004, 2004

[7] 譚少輝. 一種跨平臺(tái)三維GIS系統(tǒng)的分析與實(shí)現(xiàn)[J]. 軟件, 2014, 35(12): 94-97

TAN S H. The analysis and implementation of a cross- platform 3D GIS system[J]. Software, 2014, 35(12): 94-97

[8] Mapbox. Vector Tile Specification ver2.1[OL]. [2016-4-29]. https://github.com/mapbox/vector-tile-spec/tree/master/2.1..

Multithreading Modification of GIS Vector Drawing on Domestic Platform

ZHU Li1, ZHENG Hao2
(1. No.15 Institute of China Electronics Technology Corporation, Beijing, 100083, China; 2. No.15 Institute of China Electronics Technology Corporation, Beijing, 100083, China)

In order to solve the usability problem of vector map drawing in GIS on domestic platform, this article tries to modify vector drawing module in a multithreading way based on the idea of vector tiles, including the tiling of vector data. The result shows that this method of the multithreading modification can improve the performance of vector map drawing performance largely.

GIS; The optimization of vector map visualization; Vector tiles; Multithreading

P208

: A

10.3969/j.issn.1003-6970.2017.02.024

朱荔(1992-），女，碩士研究生，主要研究方向：計(jì)算機(jī)軟件與理論；鄭昊(1978-），男，研究員級(jí)高級(jí)工程師，主要研究方向：地理信息系統(tǒng)平臺(tái)技術(shù)與數(shù)據(jù)共享。

本文著錄格式：朱荔，鄭昊. 國(guó)產(chǎn)平臺(tái)上GIS矢量繪制的多線程改造[J]. 軟件，2017，38（2）：116-120