基于RTree與矩形碰撞檢測的探井文字標(biāo)注避讓

王 巧， 卿粼波， 張余強(qiáng)， 劉慧婕

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

0 引 言

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

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

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

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

1 地圖標(biāo)注避讓的必要性以及評價因素

1.1 地圖標(biāo)注避讓的必要性

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

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

圖1 未避讓渲染效果圖

1.2 地圖標(biāo)注的評價因素

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

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

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

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

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

2.1 算法思想

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

圖2 碰撞檢測標(biāo)注效果圖

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

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

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

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

2.2 算法細(xì)節(jié)討論

2.2.1 探井文字標(biāo)注備選位置

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

圖3 文字標(biāo)注四分位模型

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

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

2.2.3 高效點(diǎn)要素標(biāo)注索引技術(shù)

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

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

圖4 RTree實(shí)例

2.3 算法流程

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

2.3.1 數(shù)據(jù)預(yù)處理建立RTree索引結(jié)構(gòu)

在尋找探井圖標(biāo)文字標(biāo)注的位置前，對探井?dāng)?shù)據(jù)進(jìn)行預(yù)處理，建立RTree空間索引結(jié)構(gòu)，為之后尋找文字標(biāo)注位置提供便利。分為以下步驟：

(1)加載探井信息時，由每一口井的坐標(biāo)信息，即探井圖標(biāo)的中心點(diǎn)坐標(biāo)(c)，進(jìn)而獲取其外接矩形的四個頂點(diǎn)坐標(biāo)(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為探井圖標(biāo)半徑。

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

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

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

2.3.2 矩形碰撞檢測尋找標(biāo)注位置

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果對比及分析

3.1 地圖標(biāo)注避讓效果及分析

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

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

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

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

圖5 探井文字標(biāo)注流程圖

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

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

(a) 分辨率：152.87

(b) 分辨率：2445.98

3.2 地圖標(biāo)注自動避讓時間花銷

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

網(wǎng)格法由于受到網(wǎng)格劃分粒度的影響，想要提升自動避讓的效果，網(wǎng)格劃分粒度就要小，從而又增加了運(yùn)算量，時間花銷大。由表1可以看出對4713口探井進(jìn)行文字標(biāo)注避讓，網(wǎng)格法花費(fèi)了807 ms。

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

4 結(jié)束語

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