王 巧， 卿粼波， 張余強， 劉慧婕

(1 四川大學 電子信息學院， 成都 610065； 2 成都西圖科技有限公司， 成都 610065)

0 引 言

在探查油氣藏的過程中，為了確定油氣藏的邊界，獲取相關地質資料而進行鉆的井為探井[1]。探井信息是油田開發(fā)中的重要資源，利用探井信息分布可以進行空間油氣的預測[2]。

探井信息在地理要素上表現(xiàn)為點數(shù)據(jù)格式，在WebGIS中以圖標和文字標注的形式表現(xiàn)。地圖上的要素根據(jù)其形狀，標注可分為點要素標注、線要素標注和面要素標注[3]，因此對于探井文字標注避讓也即解決點要素標注的問題。對于點狀要素，Yoeli是最早進行點狀注記的學者之一，使用簡單的搜索方法[4]；Christensen提出一種稱為梯度下降的方法[5]；趙靜和呂德奎提出了一種基于網格的地圖標注避讓算法[6-7]。

在WebGIS中渲染探井信息時，考慮到實時交互問題，需要動態(tài)更新探井文字標注，所以探井文字標注避讓的效率和精確度是必須考慮的問題。但由于探井數(shù)量大，以上點狀要素標注方法存在時間花銷大、標注精確度受網格劃分粒度影響的問題。

為解決以上問題，本文提出了一種基于RTree建立點要素的高效空間索引，矩形碰撞檢測尋找文字標注最佳顯示位置的方法，實現(xiàn)了探井標注自動避讓，較網格法具有標注質量高、效率高、耗時短的特點。

1 地圖標注避讓的必要性以及評價因素

1.1 地圖標注避讓的必要性

地圖標注在有限屏幕顯示時，不可能表達所有的信息。標注位置和排列是否得當和美觀，對地圖的清晰度、易讀性和使用價值具有直接的影響[3]。

以谷歌地圖為底圖，渲染了4713口探井數(shù)據(jù)，在數(shù)據(jù)密集區(qū)域探井圖標、文字標注存在大量重疊現(xiàn)象，嚴重影響了地圖的清晰、易讀性以及探井信息的傳遞，如圖1所示。油田開發(fā)人員通過不同類型探井的分布可以判斷區(qū)域油氣藏的存在情況，所以在探井文字避讓中需保留探井分布，解決文字標注與探井圖標，文字標注與文字標注之間的重疊問題。

圖1 未避讓渲染效果圖

1.2 地圖標注的評價因素

地圖要素分布的不規(guī)則常導致標注沖突和壓蓋。沖突、壓蓋和位置優(yōu)先級是評價地圖標注質量的重要依據(jù)：

(1)沖突：標注與標注之間的重疊稱為沖突。是地圖標注中最嚴重的問題，它不僅影響地圖的美觀，而且妨礙信息的傳達。

(2)壓蓋：標注與要素的重疊稱為壓蓋。標注是與要素有機地結合在一起，有些壓蓋是允許的，如道路注記對道路的壓蓋。

(3)位置的優(yōu)先級：標注的備選位置在易讀性和美觀性方面存在差別，主要要素或使用者關心的要素應優(yōu)先被標注。

2 算法思想及實現(xiàn)過程

2.1 算法思想

在WebGIS中探井信息以圖標和文字標注的形式表現(xiàn)。為了解決避讓的效率與精確度，本文利用矩形碰撞檢測確定文字標注的位置，即對于待標注的探井圖標，將其文字標注、其他探井圖標、已經標注的文字三者的外接矩形做碰撞檢測，判斷是否有重疊，以確定其標注的位置。如經過矩形碰撞檢測后標注的幾口探井文字標注，如圖2所示。

圖2 碰撞檢測標注效果圖

利用矩形碰撞檢測能精確的判斷探井圖標和文字標注的沖突、壓蓋情況，解決了避讓的精確度問題。若是循環(huán)遍歷來做碰撞檢測，當探井數(shù)量較大時，所消耗的時間將會以數(shù)量的平方次增長。為了解決避讓的效率問題，本文利用RTree建立空間索引結構，主要分為以下二步：

(1)插入：將探井圖標外接矩形插入RTree中，用矩形框分割插入的矩形元素，直到每個矩形中包含的元素不超過9個停止分割。

(2)查詢：在查詢時，數(shù)據(jù)被排列在一個樹狀結構中，從根節(jié)點開始向下，當某一節(jié)點的某一分支不符合查詢條件時，該分支下的所有節(jié)點都可被跳過。

利用RTree建立空間索引結構，碰撞檢測時不用遍歷所有的外接矩形，大大地提高了避讓的效率。

2.2 算法細節(jié)討論

2.2.1 探井文字標注備選位置

點狀要素的標注備選位置通常有4、5、8、n備選位置等情況[8]。根據(jù)地圖的使用習慣，點要素的標注一般位于其右方，所以本文在考慮地圖使用習慣的基礎上建立了如圖3所示的四分位模型尋找探井文字標注的最佳位置。所謂四分位模型也即點要素標注的備選位置按照優(yōu)先級依次為右、下、上、左。

圖3 文字標注四分位模型

2.2.2 探井文字標注屬性優(yōu)先級

確定備選位置及其優(yōu)先級之后，根據(jù)用戶關心的屬性，確定屬性優(yōu)先級，高優(yōu)先級的要素先標注，低優(yōu)先級的要素后標注，后標注的要素可能會因為位置被占用而隱藏其標注。油田開發(fā)人員較為關心的探井屬性有：鉆井深度、油氣發(fā)現(xiàn)、鉆井時間等。本文選取鉆井深度屬性作為避讓的一個條件，其中鉆井深度越深優(yōu)先級越高。

2.2.3 高效點要素標注索引技術

RTree是由Guttman提出的一種可用來做空間數(shù)據(jù)存儲的樹狀數(shù)據(jù)結構[9]。RTree是BTree在高維空間的擴展，是一顆高度平衡的索引樹，它所有的索引記錄都放在葉結點中，可以有效地處理空間數(shù)據(jù)信息[10]。

本文在渲染探井信息時，將探井圖標外接矩形插入RTree中，建立一個高效的空間索引結構，并利用Map數(shù)據(jù)結構以井號為唯一標識，存儲探井與其文字標注外接矩形。在確定某一個探井文字標注時，利用Map得到其文字標注外接矩形，將此矩形結合RTree的查詢算法來決定要不要搜索某個子樹，進而可以跳過RTree上的大部分結點，從而提高查詢和避讓的效率。一顆RTree的實例圖4所示。

圖4 RTree實例

2.3 算法流程

本文利用RTree建立高效的空間索引，進行矩形碰撞檢測，尋找探井文字標注最佳位置進而進行文字標注避讓。該方法實現(xiàn)文字標注避讓分為二個步驟：數(shù)據(jù)預處理，建立RTree索引結構；矩形碰撞檢測尋找標注位置。

2.3.1 數(shù)據(jù)預處理建立RTree索引結構

在尋找探井圖標文字標注的位置前，對探井數(shù)據(jù)進行預處理，建立RTree空間索引結構，為之后尋找文字標注位置提供便利。分為以下步驟：

(1)加載探井信息時，由每一口井的坐標信息，即探井圖標的中心點坐標(c)，進而獲取其外接矩形的四個頂點坐標(A，B，C，D)，式(1)～式(4)，如圖3所示；

A=[c[0]-dis，c[1]+dis],

(1)

B=[c[0]+dis，c[1]+dis],

(2)

C=[c[0]-dis，c[1]-dis],

(3)

D=[c[0]+dis，c[1]-dis].

(4)

其中，dis=r×res，res為地圖分辨率，r為探井圖標半徑。

(2)利用探井井號的唯一性，將其作為探井圖標的標識(ID)，利用Map存儲探井及其對應的外接矩形；

(3)利用RTree建立空間索引，將探井圖標外接矩形插入RTree中；

(4)將探井信息按屬性(本文根據(jù)探井信息的鉆井深度)優(yōu)先級進行排序。

2.3.2 矩形碰撞檢測尋找標注位置

數(shù)據(jù)預處理建立RTree空間索引之后，RTree中記錄了所有探井圖標的外接矩形，針對存在的標注沖突、壓蓋問題尋找文字標注的最佳位置。尋找探井文字標注位置的流程如圖5所示，探井文字標注位置的搜索可分為以下幾個步驟：

(1)遍歷經過預處理之后的探井信息，根據(jù)探井井號，利用Map快速獲取其圖標外接矩形；

(2)獲取探井文字標注所占像素長度；

(3)根據(jù)右、下、上、左的位置優(yōu)先級尋找文字標注位置；

(4)根據(jù)位置優(yōu)先級順序建立如圖3所示的文字標注外接矩形。利用RTree進行空間查詢，也即做矩形碰撞檢測，判斷當前探井文字標注是否與其他探井文字標注沖突，或者是否壓蓋其他探井圖標。進而尋找文字標注的最佳位置。

(5)當確定一個探井文字標注的位置之后，將其文字標注所占矩形插入RTree，避免尋找剩余探井文字標注位置時與之前的文字標注發(fā)生沖突。

3 實驗結果對比及分析

3.1 地圖標注避讓效果及分析

為了更好的展示避讓的效果，圖6截取了圖1中的部分探井，對比了未進行避讓以及利用網格法和本文提出的方法進行探井文字標注避讓的效果。對圖6各圖分析如下：

(a)未經過任何方法處理的探井原圖，存在大量的沖突、壓蓋問題。

(b)利用網格法避讓，由于在尋找探井文字標注位置時，未考慮圖標所屬網格，故仍然存在沖突、壓蓋現(xiàn)象，如圖中箭頭所指區(qū)域。

(c)利用本文所提方法進行避讓，利用矩形碰撞檢測來精確判斷重疊情況，提高標注的質量，不存在沖突、壓蓋問題。

圖5 探井文字標注流程圖

(a) 未避讓效果圖 (b) 網格法效果圖 (c) 基于RTree和矩形碰撞效果圖

當用戶縮放改變比例或者改變顯示區(qū)域，或者瀏覽大于屏幕顯示區(qū)域的地圖時，探井文字標注需根據(jù)分辨率動態(tài)變化。不同分辨率下文字標注效果，如圖7所示。

(a) 分辨率：152.87

(b) 分辨率：2445.98

3.2 地圖標注自動避讓時間花銷

使用Chrome瀏覽器的Chrome DevTools Performance功能，來分析檢測利用網格法、基于RTree和矩形碰撞方法在探井文字標注自動避讓的時間開銷。

網格法由于受到網格劃分粒度的影響，想要提升自動避讓的效果，網格劃分粒度就要小，從而又增加了運算量，時間花銷大。由表1可以看出對4713口探井進行文字標注避讓，網格法花費了807 ms。

基于RTree和矩形碰撞檢測方法中，利用RTree建立空間索引，在查詢與文本標注矩形相交的矩形時，可以跳過RTree上大部分結點，從而不用循環(huán)遍歷所有的要素，大大提高了探井文字標注避讓的效率。由表1知基于RTree和矩形碰撞檢測的方法花費了462 ms，相較于網格法，其時間花銷減少了約43%。

4 結束語

本文針對在WebGIS中渲染探井信息時出現(xiàn)的沖突、壓蓋問題，提出了一種基于RTree和矩形碰撞檢測的方法。利用矩形碰撞檢測，判斷待標注文字、探井圖標、已標注文字標注外接矩形是否有重疊，精確判斷文字標注位置，提高探井文字避讓的精確度。利用RTree建立空間索引，將待標注文字外接矩形建立搜索矩形，查詢與其重疊的外接矩形，并且在查詢時跳過不符合條件的節(jié)點，提高文字避讓的效率。探井文字標注避讓的滿足油田開發(fā)工作者的要求，極大地提高了探井信息的可讀性。也可將該方法移植到其他點要素文字標注避讓的需求環(huán)境中。