最大共边算法在多图层面间接线构建中的应用

陈云

(厦门精图信息技术有限公司 福建厦门361008）

1 引言

VCT(矢量数据交换格式)是土地利用中的一种非常重要的数据交换格式，是全国土地调查和土地利用数据库更新的重要基础。国土资源部在国家标准《地理空间数据交换格式》[1]基础上制定了矢量数据交换格式VCT1.0、VCT2.0[2]和VCT3.0[3]。VCT1.0 采用未建立拓扑关系TOPO:0 的空间矢量数据交换格式[4]；VCT2.0 采用TOPO:1 的空间矢量数据交换格式，要求“面要素采用TOPO:1 方式，使用间接坐标描述面要素，封闭边界由线要素组成”；VCT3.0 中要求“面要素中的<面的特征类型>::=100，100 表示由间接坐标构成的面对象”，此外VCT3.0 还要求地类图斑（面）、宗地（面）两个层必须引入同一组线对象。

王艳东等在文献[5]中阐明了《地球空间数据交换格式》CNSDTF 是一个完备的、简单的、包容性强的空间数据转换标准，但并没有给出具体如何转换的过程；陈文玲等实现了基于MapObjects 组件中Shape 格式到Vct 格式的转化[6]，并没有涉及面间接线处理内容；刘子立等实现基于节点共面的VCT3.0面间接线构建算法[7]，但转换效率相对较低；文献[8]中虽然有给出多图层处理的一些思路，但并没有给出具体的算法。综上所述VCT 中的面要素要求使用间接坐标来描述,它需要按照一定的顺序(顺时针或者逆时针) 记录组成该多边形数据的线要素和其他一些属性信息，针对这种情况，现给出了一种根据多图层面要素的构成线段构建面要素间接线的快速算法。

2 最大共边算法

2.1 算法原理

无论是TOPO:0 和TOPO:1，还是面对象必须由引用线对象的间接坐标构成，其本质是减少数据存储的冗余。所以从空间数据导出的间接线即要保证能构成所有面要素，同时间接线的数量也要最少，不同间接线应不重叠和不重复。为了达成这个目标，在进行构建间接线时，需要对每个面状要素的构成节点进行分析。按每个面的构成节点顺序进行重叠判断，根据节点与不同面之间的重叠及连续性判断间接线的构成。

面要素是由节点构成，在VCT 矢量图中不同的面要素之间存在重叠的节点，如图1、图2 所示。除线段AB 和线段BC，并把新共线段AC 的映射信息添加到地类图斑图层要素1 面间接线信息中；类似的，将宗地图层要素1 的面间接线信息中删除线段AB 和线段BC，并把新共线段AC 的映射信息添加到宗地图层要素1 面间接线信息中；同时，更新共线段映射表，即从共线段映射表中删除共线段AB和共线段BC，并添加新共线段AC。上述过程也是体现了最大共边的思路。

图1 地类图斑（DLTB）-面间接线示例

图2 宗地（ZD）-面间接线示例

（8）在合并过程中，存在无法合并的情况：其一、图层要素（环）面的相邻间接线的共边信息不同，例如图1 中要素1 中的线段BC 和线段CD；其二、虽然相邻间接线的共边信息相同，但存在共边信息中对应的要素（环）面不存在该相邻间接线，例如图1中要素1 中的线段CD 和线段DA，其共线信息中的地类图斑图层要素5 外环对应的线段AD 和线段DC 并不相邻，以及图2 中要素1 对应的线段CD 和线段DA 并不相邻，还有宗地图层要素2 对应的线段AD 和线段DC 也不相邻。因此，在合并过程中，引入预判过程，对符合条件的才进行合并更新。

（9）在合并更新过程中，对于环岛情况，存在方向可能不对的情况，需要特殊处理。例如：图1 中地类图斑图层要素3 中，线段HI 和线段IJ 进行合并后，形成新的共线段HJ，此后，共线段HJ 和线段HJ进行合并时，则无法判断此环是顺时针方向还是逆时针方向。由此，采用相邻节点的办法来判断是顺时针方向还是逆时针方向。例如：图1 中地类图斑图层要素3 中，合并后新共线段为HH(HIJH)，起点为H，矢量化方向的下一相邻节点为I，则与新共线段的方向相同；而地类图斑图层要素5 中内环起点为H，矢量化方向的下一相邻节点为J，与新共线段不同，则方向与新共线段的方向相反。

（10）需要注意，针对多图层的情况，通常存在如下情况，例如：宗地图层要素2 的边KA，在地类图斑图层中被要素4 节点P 打断，但实际宗地图层中要素2 直接用KA 边表示，中间并没有节点P。因此针对这种情况，为了不改变宗地图层的拓扑结构，对KA 边不进行打断处理，此时，构建间接线KA 与KP是分别独立的间接线，其间接线信息也是不同的。上述构建方法也是兼容这种特殊情况。

（11）在完成合并后，提出一种检测方法，验证生成的面间接线是否正确。通过对上述图层要素生成的面间接线数据CommonLineVec，通过把面间接线按方向首尾进行拼接，重新形成一条完成的线LinePointVec，首先判断该线是否封闭，如果不是，则生成的面间接线有误；接着把拼接后的线按双份扩充处理成DoubleLinePointVec，例如图1 要素1 拼接后的线LinePointVec 的节点结果如BCDAB，则线DoubleLinePointVec 的节点如BCDABCDAB，即中间去掉一个重复的拼接节点B；然后，通过原始节点数据polygonLineVec，依次遍历DoubleLinePointVec，在DoubleLinePointVec 中找到完全匹配的子序列ABCDA，则表明面间接线生成成功，否则面间接线构建失败。

2.2 算法流程设计

算法总体流程如图3 所示, 其中关键环节之图层相邻共边合并（27）流程如图4 所示，以及有效性检测（30）流程如图9 所示。在图4 中，关键步骤之相邻线段合并成候选共边（27.9）流程如图5 所示，以及关键步骤之预判两个相邻线段合并是否有效（27.10）的流程如图6 所示，还有关键步骤之新合并共线段（27.11）的流程如图7 所示。特别地，图7 中处理环岛类型共线信息（27.11.10）步骤如图8 所示。

图3 总体流程

图8 处理环岛类型共线信息流程

图9 图层面间接线检测流程

2.3 算法实例

算法程序通过地理信息系统开发平台KingMap V6.0 进行验证，平台通过C/C++语言实现。平台运行环境为虚拟机：Win7 SP1 旗舰版64 位操作系统；DDR3 800MHz 4GB；Intel(R) Core(TM) i5-4200U @1.60GHz 2.30GHz 双核处理器，其中虚拟机CPU 分配单核双线程；硬盘50GB，5400 转。算法程序以某镇的行政区图层和地类图斑图层进行间接线的构建和导出，经过验证导出的结果数据真实可靠。不同算法性能结果如表1 所示。

表1 算法性能比较

从表1 可以看出，本文算法程序经过0.955 秒从64 个行政区和1730 个地类图斑中构建4729 个间接线。根据对导出结果的验证，确认导出数据正确且所有的间接线不重叠和不重复，符合VCT 的要求，如图10 和图11 所示。其中，最小共边算法生成的20915 条间接线，通过相邻间接线合并后，使得间接线数量最少，最终行政区和地类图斑两个图层仅需4729 条间接线来构建。

图10 地类图斑图层面间接线结果

图11 行政区图层面间接线结果

3 结束语

通过面要素的共边合并提出了一种构建面要素间接线的算法，解决了多图层面间接线构建的问题；同时，还提出了一种图层面间接线有效性检测算法。该算法已在地理信息系统开发平台KingMap V6.0上编程实现并进行测试，验证了算法的可靠性。该算法不仅从性能得到大幅提升，同时，还解决了一些无效图形问题，例如：同一个面多次经过同一个节点。