基于四叉树算法的地理信息数据管理研究

张 达

(天津大学 管理与经济学部，天津300072)

地理信息数据生产管理系统是测绘行业数据生产管理的核心工具.在测绘行业中，作业员如同流水线上的工人一样，按照一定的工序和步骤，对地理影像数据进行加工、处理和编辑，这些工序和成果都在地理信息数据生产管理系统中管理.［1］但是测绘行业的生产管理具有一定的特殊性，因此生产管理一般都以图幅为单位，在地理信息数据生产管理系统中引进Web地图管理接合表是地理信息数据生产行业发展的一种趋势.Web地图的加载和显示往往受到浏览器和网络带宽的限制，因此为了提高系统的易用性，提升用户体验，地理信息数据生产管理系统中应用了瓦片式地图的加载方式加载Web地图，并应用四叉树算法对瓦片金字塔建立索引［2－6］.

1 瓦片式地图模型

图1展示了瓦片金字塔在地图数据生成、存储与调用过程中的作用.图中所示模型可分为两个部分看待:服务器端的瓦片金字塔地图库以及客户端支持 AJAX(Asynchronous JavaScript and XML，异步JavaScript与XML)技术的Web浏览器.为了构建服务器端的瓦片金字塔地图库，首先需要对采集到的原始地理信息数据实施显示符号化，并分层切割成“瓦片”.瓦片(Tile)是一种特殊的图形文件，因其大多为按行列有序排列正方形栅格图片，故形象地称其为瓦片.在一定范围内，在不同比例尺下对地理信息图片数据进行切割，即生成了不同层次的地图瓦片，形成了一个“瓦片金字塔”.金字塔的一“层”即是一个数据集，对应着一个特定缩放尺寸下的瓦片图像数据(或其一部分)，越向下则比例尺越大.对于生成的瓦片图像数据，需要采用数据库系统或文件目录方式进行存储;为方便管理、调用、对数据进行增删改等操作，还需要在数据上建立索引，由于地图数据是二维图像数据，所可以利用四叉树结构创建索引.从客户端的角度来看，瓦片式图像存储与管理可以实现仅返回用户请求层次的图像数据的功能，缩短了加载时间，提高了用户体验.为方便用户在Web浏览器上的操作，可以利用AJAX创建的客户端Web交互功能，满足其对于瓦片图像层次及其他地理信息多样性的显示需求.

图1 瓦片式地图模型

2 瓦片式地图实现的关键技术

2.1 瓦片金字塔的四叉树结构

如上文所述，瓦片金字塔模型常使用四叉树结构实现，这是由地图数据是二维图像数据这一特性决定的.四叉树是一种每个节点最多有四个子树的数据结构，可以用来在数据库中放置与定位文件.金字塔的四叉树结构简介如下:定义树的层数为n(n∈N，n=0，1，2…)，每层的节点数最多不超过bb22n个，第0层的惟一结点成为根节点.由于在二维图像中一个图元可以被重复地划分成四部分，所以利用四叉树表示的金字塔结构非常适合用来描述图像数据在不同比例尺和显示分辨率下的分割.例如，0层金字塔的图像数据显示整个区域内的地图，1层金字塔的四个节点所包含的数据分别显示整个区域内地图的1/4，即东北、西北、西南、东南四个区域.2层金字塔的每个节点包含的数据为整个区域的1/16，以此类推，如图2、3所示.

2.2 瓦片金字塔的存储结构

如第1节所述，在服务器端瓦片金字塔图像数据可用数据库或文件目录的方式存储与管理.以文件目录方式为例说明瓦片数据存储结构，在这种方式下，瓦片文件被直接存储并组织在磁盘的文件目录中.瓦片金字塔中不同层级上的数据被分配到不同的目录中存储，该目录在被命名时除了要体现对应的金字塔层数，还应将图像比例尺、对应原始地图.随着金字塔层数增长，低层次瓦片图像文件的数量也越来越多，存储大量文件于单个目录中的方式不利于瓦片文件的管理与维护.为了解决此类问题，可以引入建立子目录的思路.例如，对于每一层的瓦片文件再按照瓦片所在的行数建立二级目录——由于地图数据切割时是按照行列矩阵的方式进行的，所以二级目录可以按行数命名.二级目录中的瓦片文件名按地图切片时的列数排布.例如，二级目录m中的各瓦片文件命名为m0.jpg、m1.jpg、……、mn.jpg，如图3 所示.

图2 四叉树和瓦片金字塔的对应关系

图3 瓦片金字塔的存储结构

当用户从客户端提出数据请求时，服务器端将用户请求中包含的地图范围信息进行换算，并定位至对应目录下的瓦片文件，然后将其返回到客户端.使用文件目录组织和管理瓦片图像数据有如下优点:思路理解直观，系统设计与实现简便，系统响应速度快，系统稳定性好.但是这种管理方式有其局限性，仅适用于中小型地理信息数据生产管理系统.在实践工作中，数量庞大、来源各异的瓦片图像数据没有经过检查、清洗与重载的过程，缺乏标准化的统一管理，维护和更新的成本较高.对于大规模的Web GIS平台系统，最安全、最具可持续性的管理方式还是使用地图数据库技术.地图数据库管理系统可以快捷高效地实现瓦片图像数据的更新、维护并建立索引.当然，对各个金字塔层的瓦片图像数据建立索引，并且实现瓦片数据的清洗、入库、查询、发布等功能都需要通过编写代码、查询语句和存储过程实现，工作有一定复杂度.地图数据库管理系统提高了地理信息数据管理维护工作的自动化程度，在索引已建立的前提下，系统响应速度快，能够同时兼顾平衡后台管理和前台发布工作，在大多数应用场合中都能适用.

2.3 瓦片矩阵数据结构

瓦片图像数据是按行列矩阵方式切割的，每块瓦片包含了一定经纬度范围内的地理信息数据，所以首先可以定义二维数组用以存储瓦片索引键值，一个二维数组对应着金字塔的某一层瓦片，标记为Tile n，其中 n 表示金字塔层数(n∈N，n=0，1，2…).其数组中的每个元素对应着相应瓦片图像数据的存储路径，其下标等于其对应的瓦片图像在矩阵格栅坐标中的坐标值.然后再定义一维数组用以存储瓦片矩阵的层数索引键值，标记为Layer Tile，该一维数组中元素值等于其所对应的瓦片矩阵层数.上述索引布局如图4所示.

图4 基于四叉树算法的瓦片矩阵布局

上述数据结构可以简便地建立起瓦片图像数据的存储路径索引.例如，设第n层中，某块瓦片的行号为x，列号为y，则该瓦片的存储路径可记为Layer Tile［n］［x］［y］.其中 Layer Tile［n］即 Tile n的起始存储位置.

2.4 建立索引机制

运用四叉树数据结构构建瓦片金字塔模型和存储路径索引，每块瓦片在四叉树中用一个节点来表示，如此可以快速定位到金字塔任意一层层的任意一块瓦片图像数据，高效地管理地理信息数据.在瓦片金字塔模型基础上建立线性四叉树瓦片索引，包含逻辑分块、物理分块和瓦片节点编码等工作.

逻辑分块，对应于与前述瓦片金字塔模型构建工作，规定瓦片的划分从地理图像的左上顶点开始，按照从左至右、从上到下的顺序依次进行.同时，四叉树的层编码与瓦片金字塔的层编码应当保持一致，即四叉树的0层对应金字塔的0层，四叉树的叶节点对应金字塔的底层.

物理分块，该工作在逻辑分块的基础上对从地理信息数据生成的电子地图图像文件进行实际上的切割，生成瓦片图像数据.边界瓦片中的空白多余部分需要处理，可以使用缺省像素值填充.生成的地图瓦片的文件名可按2.1提出的规则进行命名.

3 测绘生产管理系统中的Web地图

在B/S架构的地理信息数据生产管理中，可以控制地图瓦片的外轮廓线是否显示，一般情况下，用户看到的界面是不显示地图瓦片的外轮廓线的，这样在用户眼里，地图仿佛是一个整体，但是为了调试方便，在系统开发的时候，会设置一个隐藏进口用于显示瓦片地图的外轮廓线，如图5所示.Web地图被分为了若干个正方形的小格子，每个格子都是一张图片，在浏览器中通过脚本语言将他们按照瓦片索引拼接起来.

图5 切割成瓦片的地理信息数据生产管理系统

系统实现了Web地图的平移、拉框放大、选区缩小、鼠标滚轮缩放、图幅的点选和框选，以及制作专题地图的功能，接合表中，图号、作业员、检查员、生产状态等信息都分层显示，可以自由开闭.

4 结语

在地理信息数据生产管理系统中应用瓦片金字塔模型是一项较为复杂的系统工程，瓦片金字塔的生成和瓦片的检索都依赖四叉树算法.为了分层次地显示地图场景中不同细节，支持不同缩放级别以及不同分辨率的地图，瓦片金字塔模型实现了直接提供满足对应需求图像数据的功能，而不必再进行实时电子地图绘制，极大地提高了Web地图功能响应效率.在服务器端采用瓦片金字塔地图库，并在客户端的配合以AJAX编写的查询操作，降低了来自客户端的数据请求量，提高了服务器的I/O执行效率，从而提升系统的整体性能.

［1］姚真凯.瓦片地图技术在水利WebGIS系统中的开发研究与应用［J］.浙江水利科技，2009(6):40－42.

［2］张学之，阳 俊，刘 畅.B/S架构下地理信息数据加工管理系统地图相关算法的探讨［J］.测绘与空间地理信息，2012，35(1):40－42.

［3］殷福忠，孙立民.基于瓦片金字塔技术的地图发布平台开发研究［J］.测绘与空间地理信息，2010，33(5):16－20.

［4］韦 胜.ArcEngine环境下实现瓦片地图的访问与拼接［J］.武汉大学学报:信息科学版，2012，37(6):737－740.

［5］苏旭明，谭建成.Web GIS中瓦片地图关键技术研究［J］.北京测绘，2012(2):9－12.

［6］张 宏，夏洪山.GIS空间数据查询优化技术研究［J］.哈尔滨商业大学学报:自然科学版，2010，26(5):570－572.