基于RTree与矩形碰撞检测的探井文字标注避让

王 巧， 卿粼波， 张余强， 刘慧婕

(1 四川大学 电子信息学院， 成都 610065； 2 成都西图科技有限公司， 成都 610065)

0 引 言

在探查油气藏的过程中，为了确定油气藏的边界，获取相关地质资料而进行钻的井为探井[1]。探井信息是油田开发中的重要资源，利用探井信息分布可以进行空间油气的预测[2]。

探井信息在地理要素上表现为点数据格式，在WebGIS中以图标和文字标注的形式表现。地图上的要素根据其形状，标注可分为点要素标注、线要素标注和面要素标注[3]，因此对于探井文字标注避让也即解决点要素标注的问题。对于点状要素，Yoeli是最早进行点状注记的学者之一，使用简单的搜索方法[4]；Christensen提出一种称为梯度下降的方法[5]；赵静和吕德奎提出了一种基于网格的地图标注避让算法[6-7]。

在WebGIS中渲染探井信息时，考虑到实时交互问题，需要动态更新探井文字标注，所以探井文字标注避让的效率和精确度是必须考虑的问题。但由于探井数量大，以上点状要素标注方法存在时间花销大、标注精确度受网格划分粒度影响的问题。

为解决以上问题，本文提出了一种基于RTree建立点要素的高效空间索引，矩形碰撞检测寻找文字标注最佳显示位置的方法，实现了探井标注自动避让，较网格法具有标注质量高、效率高、耗时短的特点。

1 地图标注避让的必要性以及评价因素

1.1 地图标注避让的必要性

地图标注在有限屏幕显示时，不可能表达所有的信息。标注位置和排列是否得当和美观，对地图的清晰度、易读性和使用价值具有直接的影响[3]。

以谷歌地图为底图，渲染了4713口探井数据，在数据密集区域探井图标、文字标注存在大量重叠现象，严重影响了地图的清晰、易读性以及探井信息的传递，如图1所示。油田开发人员通过不同类型探井的分布可以判断区域油气藏的存在情况，所以在探井文字避让中需保留探井分布，解决文字标注与探井图标，文字标注与文字标注之间的重叠问题。

图1 未避让渲染效果图

1.2 地图标注的评价因素

地图要素分布的不规则常导致标注冲突和压盖。冲突、压盖和位置优先级是评价地图标注质量的重要依据：

(1)冲突：标注与标注之间的重叠称为冲突。是地图标注中最严重的问题，它不仅影响地图的美观，而且妨碍信息的传达。

(2)压盖：标注与要素的重叠称为压盖。标注是与要素有机地结合在一起，有些压盖是允许的，如道路注记对道路的压盖。

(3)位置的优先级：标注的备选位置在易读性和美观性方面存在差别，主要要素或使用者关心的要素应优先被标注。

2 算法思想及实现过程

2.1 算法思想

在WebGIS中探井信息以图标和文字标注的形式表现。为了解决避让的效率与精确度，本文利用矩形碰撞检测确定文字标注的位置，即对于待标注的探井图标，将其文字标注、其他探井图标、已经标注的文字三者的外接矩形做碰撞检测，判断是否有重叠，以确定其标注的位置。如经过矩形碰撞检测后标注的几口探井文字标注，如图2所示。

图2 碰撞检测标注效果图

利用矩形碰撞检测能精确的判断探井图标和文字标注的冲突、压盖情况，解决了避让的精确度问题。若是循环遍历来做碰撞检测，当探井数量较大时，所消耗的时间将会以数量的平方次增长。为了解决避让的效率问题，本文利用RTree建立空间索引结构，主要分为以下二步：

(1)插入：将探井图标外接矩形插入RTree中，用矩形框分割插入的矩形元素，直到每个矩形中包含的元素不超过9个停止分割。

(2)查询：在查询时，数据被排列在一个树状结构中，从根节点开始向下，当某一节点的某一分支不符合查询条件时，该分支下的所有节点都可被跳过。

利用RTree建立空间索引结构，碰撞检测时不用遍历所有的外接矩形，大大地提高了避让的效率。

2.2 算法细节讨论

2.2.1 探井文字标注备选位置

点状要素的标注备选位置通常有4、5、8、n备选位置等情况[8]。根据地图的使用习惯，点要素的标注一般位于其右方，所以本文在考虑地图使用习惯的基础上建立了如图3所示的四分位模型寻找探井文字标注的最佳位置。所谓四分位模型也即点要素标注的备选位置按照优先级依次为右、下、上、左。

图3 文字标注四分位模型

2.2.2 探井文字标注属性优先级

确定备选位置及其优先级之后，根据用户关心的属性，确定属性优先级，高优先级的要素先标注，低优先级的要素后标注，后标注的要素可能会因为位置被占用而隐藏其标注。油田开发人员较为关心的探井属性有：钻井深度、油气发现、钻井时间等。本文选取钻井深度属性作为避让的一个条件，其中钻井深度越深优先级越高。

2.2.3 高效点要素标注索引技术

RTree是由Guttman提出的一种可用来做空间数据存储的树状数据结构[9]。RTree是BTree在高维空间的扩展，是一颗高度平衡的索引树，它所有的索引记录都放在叶结点中，可以有效地处理空间数据信息[10]。

本文在渲染探井信息时，将探井图标外接矩形插入RTree中，建立一个高效的空间索引结构，并利用Map数据结构以井号为唯一标识，存储探井与其文字标注外接矩形。在确定某一个探井文字标注时，利用Map得到其文字标注外接矩形，将此矩形结合RTree的查询算法来决定要不要搜索某个子树，进而可以跳过RTree上的大部分结点，从而提高查询和避让的效率。一颗RTree的实例图4所示。

图4 RTree实例

2.3 算法流程

本文利用RTree建立高效的空间索引，进行矩形碰撞检测，寻找探井文字标注最佳位置进而进行文字标注避让。该方法实现文字标注避让分为二个步骤：数据预处理，建立RTree索引结构；矩形碰撞检测寻找标注位置。

2.3.1 数据预处理建立RTree索引结构

在寻找探井图标文字标注的位置前，对探井数据进行预处理，建立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)将探井信息按属性(本文根据探井信息的钻井深度)优先级进行排序。

2.3.2 矩形碰撞检测寻找标注位置

数据预处理建立RTree空间索引之后，RTree中记录了所有探井图标的外接矩形，针对存在的标注冲突、压盖问题寻找文字标注的最佳位置。寻找探井文字标注位置的流程如图5所示，探井文字标注位置的搜索可分为以下几个步骤：

(1)遍历经过预处理之后的探井信息，根据探井井号，利用Map快速获取其图标外接矩形；

(2)获取探井文字标注所占像素长度；

(3)根据右、下、上、左的位置优先级寻找文字标注位置；

(4)根据位置优先级顺序建立如图3所示的文字标注外接矩形。利用RTree进行空间查询，也即做矩形碰撞检测，判断当前探井文字标注是否与其他探井文字标注冲突，或者是否压盖其他探井图标。进而寻找文字标注的最佳位置。

(5)当确定一个探井文字标注的位置之后，将其文字标注所占矩形插入RTree，避免寻找剩余探井文字标注位置时与之前的文字标注发生冲突。

3 实验结果对比及分析

3.1 地图标注避让效果及分析

为了更好的展示避让的效果，图6截取了图1中的部分探井，对比了未进行避让以及利用网格法和本文提出的方法进行探井文字标注避让的效果。对图6各图分析如下：

(a)未经过任何方法处理的探井原图，存在大量的冲突、压盖问题。

(b)利用网格法避让，由于在寻找探井文字标注位置时，未考虑图标所属网格，故仍然存在冲突、压盖现象，如图中箭头所指区域。

(c)利用本文所提方法进行避让，利用矩形碰撞检测来精确判断重叠情况，提高标注的质量，不存在冲突、压盖问题。

图5 探井文字标注流程图

(a) 未避让效果图 (b) 网格法效果图 (c) 基于RTree和矩形碰撞效果图

当用户缩放改变比例或者改变显示区域，或者浏览大于屏幕显示区域的地图时，探井文字标注需根据分辨率动态变化。不同分辨率下文字标注效果，如图7所示。

(a) 分辨率：152.87

(b) 分辨率：2445.98

3.2 地图标注自动避让时间花销

使用Chrome浏览器的Chrome DevTools Performance功能，来分析检测利用网格法、基于RTree和矩形碰撞方法在探井文字标注自动避让的时间开销。

网格法由于受到网格划分粒度的影响，想要提升自动避让的效果，网格划分粒度就要小，从而又增加了运算量，时间花销大。由表1可以看出对4713口探井进行文字标注避让，网格法花费了807 ms。

基于RTree和矩形碰撞检测方法中，利用RTree建立空间索引，在查询与文本标注矩形相交的矩形时，可以跳过RTree上大部分结点，从而不用循环遍历所有的要素，大大提高了探井文字标注避让的效率。由表1知基于RTree和矩形碰撞检测的方法花费了462 ms，相较于网格法，其时间花销减少了约43%。

4 结束语

本文针对在WebGIS中渲染探井信息时出现的冲突、压盖问题，提出了一种基于RTree和矩形碰撞检测的方法。利用矩形碰撞检测，判断待标注文字、探井图标、已标注文字标注外接矩形是否有重叠，精确判断文字标注位置，提高探井文字避让的精确度。利用RTree建立空间索引，将待标注文字外接矩形建立搜索矩形，查询与其重叠的外接矩形，并且在查询时跳过不符合条件的节点，提高文字避让的效率。探井文字标注避让的满足油田开发工作者的要求，极大地提高了探井信息的可读性。也可将该方法移植到其他点要素文字标注避让的需求环境中。