陈 云

1厦门精图信息技术有限公司，福建 厦门，361008

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

王艳东等［3］阐明了中华人民共和国国家标准《地球空间数据交换格式》是一个完备的、简单的、包容性强的空间数据转换标准；陈泽民［4］指出了中国矢量数据交换格式在应用中存在的若干问题；也有学者采用线序排列算法对无序边界进行排序［5，6］；刘小伟等［7］实现了VCT文件到Shape的文件转换；费中强等［8］实现了从VCT到DXF的数据格式转换；王井利等［9］实现了VCT矢量格式到GDB的转换算法；鲍文东等［10］实现了土地利用矢量数据交换文件VCT到Map Info数据格式的转换。但是这些研究都没有涉及从其他格式转换成VCT的内容。郭胜涛等［11］采用文件缓存方式导出VCT数据；陈若尘等［12］实现了基于ArcGIS Engine的GIS数据格式转换；陈文玲等［13］基于MapObjects组件实现了从Shape格式到VCT格式的转换；陈红华等［14］基于空间ETL实现了VCT数据交换；吴小芳等［15］基于数据引擎思想实现了GIS数据的集成与共享，但没有涉及面间接线处理的内容；刘子立等［16］实现了基于节点共面的VCT3.0面间接线构建算法，但转换效率相对较低；也有学者实现了基于最大共边的转换算法［17，18］，算法较为高效，但主要面向单图层转换；文献［19］中提出了多图层的构建算法，但未考虑并行计算；周琛等［20］实现了VCT文件到Shape文件的并行转换方法；蒋波涛等［21］采用Map Reduce方法提升性能。综上所述，VCT中的面要素要求使用间接坐标来描述，它需要按照一定的顺序（顺时针或者逆时针）记录组成该多边形数据的线要素和一些其他属性信息。针对这种情况，本文给出了一种根据多图层面要素的构成线段构建面要素间接线的并行处理算法。

1 算法设计

1.1 最大共边算法

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

面要素由节点构成，在VCT矢量图中不同的面要素之间存在重叠的节点，如图1所示。图1（a）中，要素1的面节点顺序编号为ABCDA；要素2的面节点顺序编号为ADCMLKA。图1（b）中，要素1的面节点顺序编号为ABCDA；要素2的面节点顺序编号为DEFGD；要素3的面节点顺序编号为HIJH；要素4的面节点顺序编号KPQK；要素5的外环节点顺序编号为ADGFEDCMLKQPA，内环节点顺序编号为HJIH，需要注意的是，面要素因节点D通过两次，将被检测为无效图形。

图1 宗地、地类图斑示例Fig.1 Examples of Parcels and Land Type Patches

最大共边算法主要过程如下：

1）将矢量图层数据中的各节点排序去重后进行唯一编号。以图1（a）为例，节点集为A、B、C、D、M、L、K，记为0，1，…，6。

2）将矢量图层数据中所有线段采用首末节点编号形成坐标，利用1维线降维成0维点的方式进行处理，类似于步骤1）进行排序去重后，删除反向线段，仅保留一个方向的线段，再进行唯一编号。以图1（a）为例，线段集为A B、B C、C D、D A、C M、M L、L K、K A，记为1，2，…，8。

3）根据图层线段集合中的各线段，对各要素的组成线段进行编号，由于线段方向不同，线段编号存在正负。例如，图1（a）要素2的编号结果为−4，−3，5，6，7，8。

4）根据上述图层线段集合中的各线段建立共线段映射表，关键字为线段编号，值为共边信息，格式为“图层要素编码|（环）面索引号”，分隔符为“|”。例如，映射表中图1（a）线段C D的关键字为3，共线信息为“1|0”和“2|0”，默认第一个面索引起始为0。

5）将矢量图层各要素中具有相同共边信息的相邻线段进行合并。例如，图1（a）中，要素1中线段A B和B C的共边信息都是“1|0”，进行合并后生成新的合并共边，将该共边编号全局增1，并添加到共线段映射表。如果合并过程碰到环岛类型，则转至步骤6），否则重复执行本步骤，直到没有该合并的共边。

6）针对环岛类型的新共线段，根据其首节点的相邻节点来判断矢量化方向，并进行唯一正负编号。以图1（b）为例，要素3中，线段H I和线段I J合并后，形成新的共线段H J。此后，共线段H J和线段H J合并时，则无法判断此环是顺时针方向还是逆时针方向，应采用相邻节点的方法来判断方向。假设图1（b）要素3中，合并后新共线段为H H［H I J H］，起点为H，矢量化方向的下一相邻节点为I，则要素3的面间接线与新共线段的方向相同；而要素5中内环起点为H，矢量化方向的下一相邻节点为J，与新共线段不同，则方向与新共线段的方向相反。处理完成后，进入下个要素面进行合并，继续执行步骤5）。

1.2 多图层应用设计

最大共边算法为了适应多图层处理情况，针对上述步骤进行如下扩展处理：

①在步骤1）中，利用参与的多个面图层建立全局唯一节点集。以图1（a）和图1（b）为例，全局唯一节点集为A、B、C、D、E、F、G、H、I、J、K、L、M、P、Q，记为0，1，…，14。

②在步骤2）中，利用参与的多个面图层建立全局唯一线段集。

③在步骤3）中，遍历多个面图层，并对要素面中的线段进行正负编号。

④在步骤4）中，对共边信息采用“图层名称或图层索引号|图层要素编码|（环）面索引号”扩展格式以适应多图层的应用扩展。以图1（a）和图1（b）为例，线段C D的共边信息分别为“ZD|1|0”“ZD|2|0”和“DLTB|1|0”“DLTB|5|0”，默认外环面索引为0。

⑤在步骤5）中，针对每个图层的共线段进行合并，直到无法再合并为止。

1.3 MapReduce性能提升

针对多图层实际应用情况，对上述算法进行优化设计，引入Map Reduce框架，进一步提升面间接线构建效率。具体算法设计如下：

①采用Map Reduce并行处理框架生成唯一节点集。Map并行处理子过程：对于每一图层，按照步骤1）生成该图层的唯一节点集。Reduce单线程处理子过程：首先将每个图层的唯一节点集合并到总节点集；然后对总节点集再执行排序去重过程；最后生成唯一总节点集。

②采用Map Reduce框架生成唯一线段集。Map子过程：对于每个图层，按步骤2）生成该图层的唯一线段集。Reduce子过程：首先将每个图层的唯一线段集添加到总线段集；然后再执行排序和线段去重并保留单向线段过程；最后形成唯一总线段集。

③采用Map Reduce框架按最小线段建立共线段映射表。Map子过程：对于每个图层，按步骤3）进行正负编号，同时按步骤4）建立该图层的共线段映射表。Reduce子过程：将每个图层处理好的共线段映射表整合到总的共线段映射表中（添加过程如下：针对每个图层共线段映射表中的各个共线段，查找总的共线段映射表中是否存在，如果存在，则对共线段信息进行合并；如果不存在，则把该共线段添加到总的共线段映射表中），最终得到最小共线段映射表。

④为后续最小共线段合并成最大共线段做准备，此时仅采用Map框架对最小共线段映射表中的每条共线段的共线信息进行排序。

1.4 面间接线检测方法

在面间接线构建完成后，为了检验生成的面间接线的正确性，本文给出一种快速自动测试设计方案，形成闭环管理。具体算法设计如下：

①针对上述并行算法生成的面间接线数据，将面间接线按方向进行首尾拼接，重新形成一条完整的线。假设生成的面间接线数据如下：间接线1的顺序节点为A D；间接线2的顺序节点为D C；间接线3的顺序节点为A B C…。以图1（a）的要素1为例，假设要素1生成的面间接线结果为（−1，3，−2），则要素1面间接线按顺序进行拼接后形成完整线（记为ZD_FEATURE1_LINE1）的顺序节点结果为D A B C D，已去掉中间重复节点。

②判断拼接线是否封闭，如果不是，则生成的面间接线有误，则面间接线构建失败。例如，ZD_FEATURE1_LINE1的首尾节点都为D，因此生成正确。

③将拼接线进行双份扩充处理，形成双倍线。例如，图1（a）要素1的拼接线ZD_FEATURE1_LINE1进行双倍扩展处理后，形成双倍线（记为ZD_FEATURE1_LINE1_TWICE）顺序节点为D A B C D A B C D，已去掉一个重复的拼接节点D。

④判断要素面中原始顺序节点数据是否是其对应双倍线的子集。例如，图1（a）要素1的原始顺序节点数据为A B C D A，显而易见，可以从其双倍线ZD_FEATURE1_LINE1_TWICE中查找到完全匹配的子序列A B C D A，这表明要素1的面间接线生成成功；否则面间接线构建失败。

⑤利用上述自动检测过程可以同时处理不同图层、不同要素、不同面对象，相互间并不冲突，易于采用并行算法实现，因此可以复用§1.3的Map处理过程进行性能优化。

2 算法实现与比较

算法程序通过地理信息系统开发平台King⁃Map V6.0实现，King Map V6.0平台升级版基于QT5.9开发，通过C/C++语言实现，采用Qt Con⁃current框架的blocking Mapped Reduced机制实现Map Reduce功能，多次采用阻塞机制是因为前后步骤之间需要同步，保持数据一致性。该平台运行环境为VMware虚拟机：Windows7 SP1旗舰版64位操 作 系 统；DDR3 800 MHz 4 GB内 存；Intel（R）Core（TM）i5⁃4200U@1.60 GHz 2.30 GHz双核处理器；硬盘50 GB，5 400 r/min。算法程序以某镇的行政区图层（64个要素）、宗地图层（290个要素）和地类图斑图层（1 730个要素）为例进行间接线的构建和导出，检验结果表明，导出的结果数据真实可靠。不同算法的性能比较结果如表1所示。

从表1中可以看出，本文算法在双线程情况下，经过1.014 s从64个行政区、290个宗地和1 730个地类图斑中构建7 904个间接线。虽然达不到理论上的性能提升效果，但性能仍有所提升，约提升15.6%。相较于节点共面算法，本文算法性能大幅提升。对导出结果进行检验，确认导出数据正确且所有的间接线不重叠和不重复，符合VCT的要求，如图2所示。

表1 算法性能比较Tab.1 Comparison of Performances of Different Algorithms

图2 导出的数据Fig.2 Export Data

3 结束语

本文通过面要素的共边合并，提出了一种并行构建多图层面要素间接线的算法，同时给出了一种面间接线构建是否有效性的高效并行检测方法。该算法已在地理信息系统开发平台KingMap V6.0上编程实现并进行测试。结果表明，该算法可靠，不仅在性能上大幅提升，还解决了一些无效图形问题。例如，同一个面多次经过同一个节点。但是，该算法仍然存在不足之处，有待在分布式环境下进行扩展设计和实现，后续会对此问题进行研究。