网格化河湖管理中的地理实体编码与匹配

蔡赟 吕景旭

摘要 网格化管理由于其可以保证地理实体的完整性、管理的便捷性等优势，在河湖数据管理中得到广泛的应用。传统编码方案基于矩形或经纬网的分幅方法，对地理实体位置信息的表达不适用于网格化管理。本文针对河湖数据网格化管理，在研究相关编码方案的基础上，基于四进制Morton码的编码思想，对常规线性四叉树存在的一些弊端进行改进，设计了一种基于地理实体位置信息的编码方案，所设计方案提高了空间利用率与查询效率，便于河湖数据的维护与更新。

关键词网格化;地理实体编码;四叉树;Morton码

1引言

在地学领域中，网格化是一种依照道路、水系、行政区划边界等要素对地理空间进行划分的方法[1]。划分形成的多边形称为网格单元，各个网格单元相互邻接且不发生交叉，其间的空间关系是隐含表达的[2]。与传统分幅方式相比，网格化可以最大限度地保证地理要素的完整性与连续性。在数据处理中，可减少接边的工作量，提高工作效率，在实际应用中方便日常管理，因此在河湖数据管理中得到了广泛应用。

2编码方法

2.1四叉树与Morton码地址编码

四叉树是一种应用十分广泛的数据结构[5]，它的建立是将地理空间划分为四个相等的子空间，然后通过递归的方式对子空间重复划分直至满足一定要求后停止，划分后对应的格网信息存储在叶结点中，位置信息则隐含于结点编号（即地址编码）中。Morton码通过将二进制的行号和列号交叉组合为格网赋予地址编码。相比于其他编码方案中直接记录四叉树行列号的方式[3]，四进制Morton码将二维数据转为一维数据，同时将空间层次包含在编码中，更有利于数据结构的设计以及存储。

当地理实体位置分布较为均匀时，四叉树各个分支之间较为平衡，数据插入和查询都有较高的效率;而当数据量较大且分布不均时，随着数据的逐渐插入，不均衡的数据分布将导致四叉树各分支之间失去平衡。由于存储实体的结点均为叶结点，中间结点与根结点均不参与存储，检索时必须遍历至叶结点才能结束，这样就会增加检索深度，降低检索的效率，同时造成存储空间的浪费。

因此，本文在建立四叉树时，将地理实体信息存储在完全包含该实体的最低层次结点中，而不是完全存储在叶结点中。这样改变存储位置之后，根结点、中间结点就与叶结点一样，需要使用四进制Morton码来获取地址编码。改进前后的四叉树以及Morton码的应用如图1、表1所示（根结点代表第0层）：

以实体C为例，该实体涉及第2层的结点00与结点02，但由于结点00、01、02、03为第一层的同一结点的子结点，故检索区域包含2*2个结点，在使用单层Morton码时，对应的区域边长值为2，在四叉树中检索至树的第2层获取到相关实体，需要用2个结点来存储实体信息。而在使用分层Morton码时，包含实体C的最小格网为以上四个结点的父结点，处于四叉树中第1层，对应的分层Morton码为00，仅需1个结点存储，检索时遍历至树的第1层即可结束。由以上对比易知，改进后的分层Morton码以及四叉树充分利用了现有结点，节约了存储空间，同时降低了涉及范围较广的实体的检索深度，提高了检索效率。

2.2 格网划分与编码

格网的划分与编码设计基于2.1中分层Morton编码的基本思想进行。由于四进制分层Morton码的长度与所在层次相关，为保证码段长度恒定，当码段长度空缺时使用“9”进行补位。如图2，编码由四部分组成，前三部分为不同层次的位置码段，分别为行政区划位置码（5位）、网格单元位置码（4位）、实体位置码（7位），最后一部分为扩展码（2位）。

第一部分为行政区划位置码，通过对根结点存储的地理空间划分2次，最终划分为3层，第2层的结点共16个，政区实体存储在四叉树中0、1、2层，码段长度为5位，其中Morton码3位，顺序码2位（表示市级行政编号）。

第二部分为网格单元位置码，在第一次划分的基础上对地理空间再划分2次，空间总共被划分为5层，网格单元主要存储在四叉树中3、4层，第4层的结点共256个，码段长度为6位，其中Morton码4位，顺序码2位（表示网格单元编号）。

第三部分为实体位置码，在第二次划分的基础上再划分4次，至此，空间总共被划分为9层，地理实体主要存储在四叉树中5、6、7、8层，叶结点共65536个，码段长度为11位，其中Morton码8位，顺序码3位（地理实体编号，保证地理实体的唯一性）。

第四部分的扩展码默认为“00”，方便数据的存储与管理。

同时，为避免编码长度过长，数据表中将前两个码段与后两个码段分别存储在两个字段中。这样，基于分层思想的编码方式，将地理实体位置信息通过四进制Morton码将空间索引记录在编码中，为地理实体的快速检索提供了依据。

3地理实体检索与匹配

在网格化河湖管理系统中，根据编码可实现未知地理实体与数据库中地理实体的初步匹配。日常管理中，网格单元由专门的巡查人员进行巡查，发现异常时将信息进行上报。服务器端可根据巡查人员位置以及上报的实体信息自动生成地理实体位置相关码段。依照生成的位置码段，与数据库中的实体进行编码匹配，最终将检索范围限制在包含该实体的最小四叉树网格内。图3中（a）（b）分别为江苏省和南京市的格网划分与Morton编码，表2为江苏省部分市区的行政区划位置码：

如图3（a）中所示，通过两次划分将江苏省所处空间分为3层，各地级市根据其空间位置存储在不同层次的结点中，如完全包含南京市的最小结点为第2层中Morton码003的结点，依据其行政区划代码3201得到顺序码为01，最终得到南京的行政区划位置码为00301。同理可得，完全包含苏州的最小结点为第1层中Morton码01的结点，其行政区划位置码为01905;扬州处在第1次划分的分割线上，只有根结点可完全包含该政区实体，因此其行政区划位置码为09910。图中根据巡查人员所处A点位置信息，依照点与多边形关系判断出该巡查员位于南京市范围内，因此自动生成行政区划码段为00301。确定行政区划范围之后，如图3（b）所示，在003结点的基础上通过同样的方法继续进行格网划分和位置关系判定，可以自动生成网格单元位置编码为129914（位置关系判定得到所处网格单元顺序码为14）。在确定网格单元的基础上，根据上报的地理实体位置信息，可知包含该实体的最小四叉树结点位于四叉树中第5层，Morton码为21999，因此生成的实体编码为21999999000（顺序码默认为000）。至此便可获得上报地理实体编码为“003011299141299999900000”，进而在数据库中通过编码匹配筛选出符合条件的实体进行进一步匹配。

通过编码筛选之后只有很少的地理实体进入候选集，可大大减少与待匹配的实体进行精确匹配的时间。在河湖数据中，点状实体多为水利设施，在空间分布上较为分散，可通过计算点实体间的曼哈顿距离完成匹配;线状实体多为单线河、航道数据等，可依次通过计算长度偏差、首点终点连线的方向偏差进一步缩小检索范围，最终通过计算Hausdorff距离实现精确匹配;面状实体则可依次计算质心距离、面积重叠比排除候选集中大部分实体，最后计算Hausdorff距离完成匹配。

4结语

本文针对网格化河湖管理的数据，提出了一种基于四进制Morton码的分层式地理实体编码方案，并讨论了面向河湖数据对象的逐层筛选式的地理實体匹配策略。通过地理实体编码将其空间位置信息存储在编码字段中，检索时将空间位置的检索转换为编码之间的相似性匹配，提高了检索效率，配合逐层筛选的地理实体匹配方式，为网格化河湖数据管理中快速定位、快速检索与准确匹配提供了重要方法。

参考文献

[1]李德仁，宾洪超，邵振峰.国土资源网格化管理与服务系统的设计与实现[J].武汉大学学报（信息科学版），2008（01）：1-6.

[2]李琦，罗志清，郝力，安真臻.基于不规则网格的城市管理网格体系与地理编码[J].武汉大学学报（信息科学版），2005（05）：408-411.

[3]彭瑞，江瑞.关于地理实体编码设计和应用的研究[J].现代测绘，2012，35（03）：23-26.

[4]张天蛟，严泰来，王海蛟，杨永侠.基于Morton码的土地空间网格数据组织与检索[J].农业工程学报，2013，29（S1）：235-243.

作者信息

蔡赟 1989-12，男，江苏省扬州市，江苏中诚土地房地产评估规划咨询有限公司，江苏省扬州市邗江区文汇西路173号  现代广场25幢6楼，225000，13338865952

吕景旭，1996-11，男，，山东省微山县，地图制图学与地理信息工程，东南大学交通学院，南京市江宁区东南大学路2号，211189，15051879652