基于矢量瓦片的点状要素注记处理技术

齐亚光,胡明晓,龚志红,樊竝君

(1.中国电子科技集团公司第十五研究所基础三部,北京 100083;2.温州大学数理与电子信息工程学院,浙江 温州 325035; 3.空军驻华北地区军事代表室,北京 100086)

0 引 言

瓦片数据对应一个空间参考下的一种多分辨率[1]层次模型，瓦片数据按照金字塔结构组织，每张瓦片都可通过级别、行列号唯一确定。在平移地图或不同比例尺数据缩放时，显示端根据规则，计算出所需的目标瓦片的级别与行列号，从瓦片服务器获取相应的瓦片数据进行绘制并拼接显示[2]。

一个瓦片可以由多个类型的图层组成，如矢量显示瓦片、影像瓦片、DEM瓦片等，瓦片数据显示流程如图1所示。本文研究矢量瓦片的注记处理，矢量瓦片数据记录目标属性与几何信息。矢量瓦片体积小，可高度压缩，既可以减少自身数据量，又可以减少对网络带宽的消耗[3]。

图1 瓦片数据显示流程

本文规定以CGS2000标准下，第0级为编号0/0/0和0/0/1这2片瓦片,注记字体为微软雅黑，如图2所示。

图2 第0级数据(一行2列)

1 矢量瓦片点状注记处理的必要性

地图在有限屏幕显示时，不可能表达所有的信息[4]。在地图屏幕一定的显示范围内尽可能多地显示相关信息，会带来地图空间拥挤，难以阅读。

矢量瓦片点状符号注记处理技术的基本问题是如何解决空间定位矛盾[5]，使点状注记的位置不发生重叠和保持注记完整性。矢量瓦片地图中不同比例尺的数据对应不同的瓦片级别。在注记稀疏的情况下易对注记进行处理,但小比例尺图中点状要素在图中分布最为密集，它的冲突、压盖问题最为突出，尤其是全局冲突问题最为严重[6]。

如图3所示，注记被截断、注记与注记压盖、注记压盖要素等现象的出现，干扰了地图所要表达的准确信息。

2 矢量瓦片点状注记处理原则

2.1 注记完整性原则

在以瓦片金字塔结构显示地图时，不同于桌面系统屏幕边缘截断注记[7]。由于矢量瓦片的组织结构，可能导致注记被瓦片边缘截断，进而出现瓦片不完整现象。所以应保证在本瓦片范围内注记的完整性。如图3所示，拉萨市注记被瓦片左边缘截断，只显示“市”一字。

图3 未处理矢量瓦片1/1/3局部

2.2 注记优先级原则

地图是简化地理空间信息的产物。在地图上放置要素注记位置的空间有限，不可能显示所有信息，因此，需要指定不同注记的优先级[8]，依据其重要性进行适度的取舍。

2.3 注记避让原则

注记之间不能相互压盖，否则地图将变得无法阅读。本原则要求一个要素注记要尽可能少地妨碍其他要素注记，即注记之间不能相互压盖，注记与要素符号之间不能相互压盖[9]。如图3所示，西宁市与兰州市、石家庄市与太原市的注记和要素符号互相压盖。

3 基于矢量瓦片数据的注记处理绘制流程

矢量瓦片数据的注记处理绘制流程包括遍历矢量数据，通过四叉编码过滤出目标瓦片的目标，通过注记搭配表进行注记搭配，得到点注记对象集合、仿射变换、待处理目标集合(几何、属性)，根据优先级进行目标压盖判断和位置调整、待绘制注记集合、执行绘制等过程，绘制流程如图4所示。

图4 基于矢量瓦片绘制流程

3.1 四叉编码进行目标瓦片的目标过滤

四叉树是把一幅图像递归地等分为4个子区域，即四分区。如果一个四分区的所有网格具有相同的值或完全不同的值，则这个子区就不再往下分割。如果一个四分区的所有格网值不完全和目标不同，则继续分割。在每一个四分区，其四叉编码具有继承性，即编码具有可压缩性。每个格网的四叉编码都记录着父瓦片信息[10]。

图5 四叉编码

四叉树算法将整个矢量瓦片地理范围区域看成四叉树的母结点，母结点覆盖整个瓦片区域[11]。利用四叉树数据结构，树中的每一个结点都覆盖地形中的一块相应矩形区域[12]。本文根据以上原则，利用指定父瓦片范围内的子瓦片的四叉编码过滤出指定子瓦片范围的目标。图5为矢量瓦片0～3级瓦片，从1级开始，将父瓦片分成4等份，规定从下到上，从左往右的顺序分别进行0、1、2、3编码。在保留之前编码的前提下，对每一份分别进行四叉编码递归。例如利用0_1_3矢量数据画出2/6/13瓦片，可以得出2/6/13瓦片的四叉编码为21，在遍历矢量数据目标时，以目标过滤码和显示过滤码相比较，选取短的一个过滤码为编码长度。比较目标过滤码和显示过滤码，确定此目标是否在2/6/13瓦片范围内。此示例会选出目标过滤码为2或以21开头的目标。目标过滤码为2的目标可能一部分属于2/6/13瓦片范围，目标过滤码为21开头的目标可完全属于2/6/13瓦片范围，从而实现在0_1_3范围内过滤出目标瓦片2_6_13的数据，进行正确的目标范围绘制。

3.2 根据注记搭配表得到注记对象

通过读入不同图层数据标准，得到不同图层的注记搭配表对象。注记搭配表为JSON结构，JSON结构数据格式比较简单，易于读写。注记搭配表JSON结构示例代码如下：

"labelmatch":

[{

"fields": {

"CATEGORY": 1,

"level":1,

"geoType":1

},

"matchtable":

[{

"filter": {

"CATEGORY": [0,1],

"geoType":1

},

"name": "国家",

"value": {"font":"宋体","size":14,"color":16711680,"border":false}

},{

"filter": {

"CATEGORY": 8

},

"name": "首都",

"value": {"font":"宋体","size":13,"color":255,"border":false}

}, ],

"std": "WORLD_BASE"

}]

其中，fields为注记搭配表的搭配字段，此示例有CATEGORY、level、geoType这3个搭配字段，分别为目标编码、显示级别和目标类型。搭配字段的数字为1、2、4分别代表整数、浮点、字符串类型。此示例搭配字段全为整数。matchtable为搭配规则的集合，此示例有2个规则，即国家、首都。每条规则的过滤条件为filter字段进行控制，filter字段中的过滤条件全部满足则搭配成功。例如第一条为国家的过滤条件为目标变编码范围[0,1]之间，并且目标类型为点。

搭配成功则通过value字段进行地图注记的设计。font为字体样式，size为字号大小，color为颜色(RGB十六进制转为十进制数)，border为注记是否有外接矩形框。当第一条规则匹配成功时的注记样式字体为宋体，字号为14，颜色为红色，十六进制数值FF0000(RGB)，十进制为16711680，注记没有边框。

3.3 确定图层的绘制次序

一个瓦片图层表示相同的空间参考和切分方案的数据，一个地图中只能有一个瓦片图层。一个矢量瓦片图层可由多个图层组成，一个图层可由多个目标组成，如图6所示。

图6 矢量瓦片组织结构

通过配置文件正确获取图层的绘制次序，属于显示风格。可通过如下代码添加图层进行示例：

layerOrderList.push_back(“境界与政区”);

layerOrderList.push_back(“水域陆地”);

layerOrderList.push_back(“陆地交通”);

layerOrderList.push_back(“居民地与附属设施”);

layerOrderList.push_back(“WORLD_BASE”);

3.4 从矢量数据中过滤出点要素

图7 从矢量数据过滤出点要素

根据图层的绘制次序，遍历每个图层对应的注记搭配表，根据注记搭配表中注记的次序，自顶向下，将瓦片用的绘制注记对象放到相应的绘制列表中。遍历矢量数据过程中记录注记对象及其相应的类别(见图7左)。1、2、4分别代表点注记、线注记、面注记。通过过滤操作将点注记对象放到点注记对象的绘制列表中(见图7右)。

3.5 通过仿射变换，进行视口变换

通过二维坐标到二维坐标之间的线性变换，仿射变换可以对图形进行平移、缩放、旋转[13]等操作。经过仿射变换，原来的直线仿射变换后还是直线，原来的平行线仿射变换后还是平行线且直线上点的位置顺序不变。即仿射变换保持了“平直性”和“平行性”。仿射变换可以写为如下的形式：

通过仿射变换使世界坐标与屏幕像素坐标产生对应关系[14]。即瓦片对应的世界坐标范围到瓦片显示像素大小进行视口变换。根据图层的绘制次序，将每个图层对应的点注记世界范围坐标转换为屏幕像素坐标，为后面判断注记是否压盖提供依据。

3.6 生成待处理点目标集合(几何和属性值)

当遍历矢量数据目标进行注记搭配时，当匹配成功需要注记字典结构对注记位置、内容等数据进行记录。注记对象字典结构如图8所示。

图8 点注记绘制字典结构

对第一条规则匹配成功时进行示例，注记字典结构如图9所示。注记字典中相同的注记对象的目标相关信息记录在一个字典中。目标类型为1，则为点注记对象，注记位置索引为0，对应注记数组地址为0的注记文本内容为中国。几何信息索引为0，对应几何信息数组地址为0的数值为128(绘制像素X坐标为128，Y坐标为129)，此数值为3.5节中视口变换后的像素坐标。目标段数为1，说明此目标只有一段，顶点对数为1说明此段有一对顶点，即点注记的坐标位置。

图9 点注记绘制字典示例

3.7 确定注记优先级

地图究其本质是一种集合[15]。在地图有限的显示空间上进行地图注记，可以看成是空间竞争的组合优化问题。长期以来各种对最佳注记位置的选择优化策略都是建立在如下前提下：不压盖要素图形、不压盖先前已配置注记的前提下，选择位置优先性最高者作为最佳注记位置。

本文规定在点符号的正右方为优先级1、右下方为优先级2、右上方为优先级3、正下方为优先级4、正上方为优先级5、正左方为优先级6、左上方为优先级7、左下方为优先级8。优先级从8到1，依次递增，如图10所示。

图10 设计注记优先级

3.8 高效点注记索引技术

R树是Guttman[16]于1984年提出的最早支持有序扩展的对象存取方法之一，也是目前应用最为广泛的一种空间索引结构。R树运用了空间分割的理念，采用了一种称为最小边界矩形(Minimal Bounding Rectangle，MBR)的方法，即上述3.2节中“value”属性中“border”字段所框柱注记的最小矩形。它是类似于B树的一种高度平衡的索引树，它所有的索引记录都存放在叶结点中，可以有效地处理空间数据信息。

R树叶结点结构为：

E=(I,tuple-identifier)

R树非叶结点结构为：

E=(I,child-pointer)

设一个结点的最大实体数量为M,又假设标识一个结点的最小实体量为m(m<[M/2])。一棵R树满足如下的性质：

1)除根结点外，所有叶子结点包含有m至M个记录索引(条目)。作为根结点的叶子结点所具有的记录个数可以少于m。通常为m=M/2。

2)对于所有在叶子结点(I,tuple-identifier)中存储的记录(条目)，I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形(注意：此处所说的“矩形”是可以扩展到高维空间的)。

3)对于在非叶子结点(I,child-pointer)上的每一个条目，I是可以在空间上完全覆盖这些条目所代表的最小的矩形(同性质2)。

4)除叶结点外，根结点至少包含2个结点。

5)所有叶子结点都位于同一层，因此R树为平衡树。

R树中插入新的空间索引条目记录被添加到叶子上。溢出的结点被分割，并且分裂在树上传播。分裂传播可能会导致树的高度增长。假设E=(I，tuple-identifier)是要插入的新条目。设T是R树的根。插入新的空间记录主要步骤为：

Step1找到从T开始插入E的叶L。

Step2将E加到L。如果L已满(溢出)，则将L分解为L和L′。

Step3向上传播MBR更改(放大或缩小)。

Step4如果结点拆分传播导致T分裂，则增长树高。

算法1步骤Step1的ChooseLeaf(E，N)算法

输入：条目E=(I，tuple-identifier)和有效的R树结点N

输出：应该插入E的叶子L

If N is a leaf

Return N

Else

1. Set FS be the set of current entries in the node N

2. Set F=(I, child-pointer)∈FS, so that F.I satisfies the Insertion-Notions

Return ChooseLeaf (E, F.child-pointer)

算法2步骤Step2的AdjustTree(N，N′)算法

输入：已经修改其内容的结点N以及如果不是NULL，则产生分裂结点N′，伴随N

输出：如上所述的N和N′

If N′ is Not NULL Then

If number of entries in PN

1. Create a new Entry EN′=(I_N′, child-pointer_N′)

2. Install EN′ in PN

3. Return AdjustTree(PN, NULL)

Else

4. Set {PN, PN′}=SplitNode (PN, EN′)

5. Return AdjustTree (PN, PN′)

End If

Else

Return AdjustTree(PN, NULL)

End If

步骤Step4增长树高的概念：如果递归结点分裂传播导致根分裂，则创建一个新的根，其子结点是2个最终结点。

本文使用R树的插入操作来确定注记的位置，R树的插入操作同B树的插入操作类似。当叶子结点需要添加新的数据时，若发生溢出，那么需要对叶子结点进行分裂操作。通过R树进行空间索引记录，可以在绘制点注记时判断此位置是否已被占用。

4 实验结果对比与分析

经过以上处理，从0_0_1矢量数据读出数据，经过注记搭配表，绘制出大小为1024×1024的1/1/3矢量瓦片。瓦片局部绘制如图11所示。

图11 经过处理矢量瓦片1/1/3局部

实验采用如图1所示瓦片数据显示流程，开发环境为操作系统版本：6.1.7601 Service Pack 1 Build 7601，Windows 7专业版，处理器：Inter(R) Core(TM) i7-2600 CPU@3.40 GHz，物理内存：4037 MB，虚拟内存：8071 MB，系统类型：64 bit操作系统。TileRending(TR)为绘制时间(图1中瓦片数据显示流程共计时间)，单位为ms。Consumed(CM)为消耗时间，单位为ms。Percent(P)为此流程所占总时间的比例。

基于矢量瓦片点注记处理，如高德、百度、超图等商业化的公司，并未提供基于矢量瓦片绘制处理点状要素注记性能的数据，且关于矢量瓦片点状注记处理的资料较少。所以相关对比试验在中国电子科技集团公司第十五研究所成熟的商业产品GISMAP中进行。在瓦片的基础上，将采用R树和四叉编码进行注记处理与未采用R树和四叉编码2种数据结构对注记进行处理之间的性能作对比。未采用R树和四叉编码处理点注记时为整个绘制区域建立一张二值图，设置已放置注记的像素点值为1，否则为0。此种方法缺点明显，当绘制区域较大时，需要较大的内存记录绘制范围像素的使用情况。1/1/3瓦片使用R树和四叉编码注记绘制时间如表1所示。

表1 使用2种数据结构耗时分布表

整个瓦片绘制流程耗时230 ms，其中00A16B28等6种符号绘制共耗时172 ms。点目标共67个，耗时49 ms。

表2 未使用2种数据结构耗时分布表

未使用2种数据结构耗时分布如表2所示，整个非瓦片绘制流程耗时401 ms，其中00A16B28等6种符号绘制共耗时282 ms。点目标共67个，耗时92 ms。表2中TR非图1所示流程绘制的时间，为非瓦片化绘制和1/1/3瓦片同等范围所需时间。

基于瓦片化采用R树和四叉编码2种数据结构相比于未采用以上2种数据结构来说，处理点注记性能明显提高。

5 结束语

本文针对当前矢量瓦片的注记处理问题进行了分析，并提出了利用基于R树空间索引和注记优先级队列来解决，解决了传统桌面地图显示中未遇到过的瓦片截断边缘注记的问题。

本文注记绘制注记优先级队列是按照注记搭配表从顶向下，根据点目标在矢量数据出现的次序用R树空间索引进行位置记录。相同优先级数据可能压盖，低级别数据不能压盖高级别数据。在地图有限的空间上进行地图注记，可以看成是空间竞争的组合优化问题，为了在地图中尽可能多地显示级别更高注记，本文规定每个注记位置根据注记优先级指定分数，级别越高，分数越大。如级别1分数为8，级别8分数为1。在本文基础上可以运用遗传算法、模拟退火算法等[17-18]解决最优问题算法对一屏幕数据求最大分数值，以实现在保证注记优先级的情况下，尽可能地显示更多的注记。