基于结点加密的边线捕捉处理方法*

张青年

(中山大学地理科学与规划学院，广东 广州 510275)

在地图编辑和空间数据更新等工作中，需要对多个来源的空间数据进行融合处理。但由于不同来源的空间数据采用的数据分类体系、位置精度和数据现势性存在差异，同一地物在不同来源的地图上的位置和形状并不相同［1－4］。例如，我国地形图与海图不一致的问题普遍存在，海岸线在地形图和海图上的形状和性质都有差异［5］，一般应将地形图上的海岸线调整到海图上的参考海岸线图形位置［6］。

对象捕捉是一种基本的地图编辑功能［7］，用户利用该功能可以迅速、准确地将输入图形捕捉到线的结点、直线的交点和圆的圆心等参考图形上的某些特殊点，从而能精确地绘制图形。显然，利用对象捕捉可以实现图形数据整合处理。通过批量捕捉处理，将输入图形捕捉到容限距离内的参考图形位置，从而消除输入图形与参考图形之间的不一致。现有捕捉处理方法有两种捕捉方式，都是通过移动图形的结点来实现的。第一种捕捉方式仅移动输入图形的结点到参考图形位置，而参考图形的形状和位置保持不变。第二种捕捉方式则同时移动输入图形和参考图形，使两者在新的中间位置上重合，是一种广义的结点捕捉方式［8－9］。

由于不同来源的图形数据在位置精度和现势性等方面存在差异，通常不宜采用广义结点捕捉方式进行图形数据融合。在大多数情况下，需要以选定的参考图形为准，将输入图形改正到参考图形位置。例如，在土地利用变更调查等工作中，应该以上一年度的土地利用现状图为参考图，修改本年度的土地利用变更图斑边线，消除前后两个年度的图斑边线在容限距离内的不一致，以避免产生细小狭长的变更过程图斑。目前，一些GIS软件可自动将输入图层上的结点捕捉到参考图层上的图形，但并不能实现输入边与容限距离内的参考边完全一致。

1 结点捕捉存在的问题

在CAD和GIS等图形处理软件中，对象捕捉都是针对结点进行处理的，其基本功能是将正在绘制的图形结点抓取到已有参考图形上的某个特殊点。如果对大量结点进行批量捕捉处理，则发展成为一种图形数据融合方法。例如，ArcGIS软件的ArcToolBox模块中提供了捕捉工具，它将输入图层中的边线捕捉到参考图层中的边线上。实际上，它将输入边上所有在容限距离内的结点捕捉到参考边线上的垂足点或参考边线结点。

CAD和GIS等图形处理软件基于结点层次进行图形捕捉，并不能将输入边捕捉到与容限距离内的参考边完全重合的位置。如图1所示，输入边在参考边两侧小幅度摆动，其间距小于容限值。利用ArcGIS软件进行捕捉处理，将捕捉类型设置为Vertex，捕捉后的输入边有2处与参考边不重合。如果将捕捉类型改为Edge，则捕捉后的结点与参考边结点不重合。总之，捕捉处理过程中只移动了输入边的结点，没有有效地调整输入边的形状，因此不能与参考边完全重合。

图1 将输入边的结点捕捉到参考边Fig.1 Snap input edge to the location of reference edge

显然，必须在输入边上插入附加结点，通过捕捉移动附加结点来改变输入边的局部形状，才能使输入边与容限距离内的参考边完全重合。如图2所示，输入边到参考边的结点q2的距离小于容限，但在不插入附加结点的情况下无法将输入边捕捉到q2位置。在输入边上按指定间距插入5个结点p3～p7，其中p5靠近q2，可以被捕捉到q2处。此外，通过插入附加结点，实际上对输入边进行了分段，从而可对各段边线分别进行捕捉处理。例如，图2中附加结点将输入边分为6段，其中结点p3～p7到参考边的距离都小于容限，将被捕捉到参考边上。于是输入边的p3－p7段被捕捉到参考边，而p1－p3和p7－p2段不捕捉。

图2 基于插入的附加结点进行捕捉Fig.2 Snap an edge with added nodes

结点捕捉的另一个问题是捕捉后的边线可能出现自相交错误。如图3所示，输入边的结点v2、v3、v4和v5到参考边的距离小于容限而被捕捉到参考边，捕捉之后v'2v'3与v'3v'4、v'3v'4与v'4v'5之间存在自相交问题。本文通过引入附加的结点顺序调整步骤来解决线自相交问题。

图3 输入边捕捉处理后的自相交问题Fig.3 The self-intersections on snapped edge

2 基于结点加密的捕捉算法

如前所述，结点层次的捕捉算法只能完成对原有结点的捕捉，并且结点捕捉之后存在自相交问题。本文针对结点捕捉算法的两个局限，增设结点加密和结点顺序调整两个步骤，从而使结点和结点之间的线段都捕捉到与参考边重合，即发展成一种边线层次的捕捉算法。此外，针对现有算法将结点全部捕捉到垂足点或者全部捕捉到参考边结点的僵化配置问题，本文算法依据具体条件灵活选取垂足点或参考边结点作为目标捕捉位置。即，输入边结点的容限距离内有参考边结点时以其为捕捉点;否则以该结点在参考边上的垂足点为捕捉点。

2.1 主要数据结构

主要数据结构为边线结点链表SnapList，其数据元素为结构类型:

社会主义核心价值观如何培育与践行？习近平总书记2014年5月中旬到上海考察时指出，“培育和践行社会主义核心价值观，贵在坚持知行合一、坚持行胜于言，在落细、落小、落实上下功夫。”志愿服务作为普通老百姓自觉的助人行为，充分体现了细、小、实的特点，是培育和践行社会主义核心价值观重要载体。笔者拟结合泉州志愿服务开展的现状与特点，探讨完善志愿服务，培育与践行社会主义价值观的思路。

struct SnapPoint

{

IPoint pt;∥坐标点

bool bIsAdded;∥是否附加结点

bool bMoved;∥是否被捕捉

int refGeomOID，refPartIndex，refSegmentIndex;∥参考几何体OID，参考部件序号，参考线段序号

IPoint refPoint;∥捕捉点

double refDistance;∥到参考几何体的距离

double fromPointDistance;∥到参考线段起点的距离

}

2.2 算法步骤

本算法通过结点加密、结点捕捉和结点顺序调整等多个步骤对边线进行捕捉处理，主要步骤为:

1)加密结点。依次读入输入边ledit的各个结点，在相邻两个结点之间以容限d为间距插入附加结点。如图4所示，空心点为插入的附加结点。为每个结点新建为一个SnapPoint元素，其中原有结点的 bIsAdded为 false，附加结点的 bIsAdded为Ture。将各个SnapPoint元素依次写入SnapList链表。

图4 加密结点Fig.4 Insert nodes on the edited line

2)查找最近的捕捉点。对于SnapList链表中的每个元素vi，查找在其容限d内的参考边并计算到该参考边上的最近距离和最近距离点，将其记录到 refGeomOID、 refPartIndex、 refSegmentIndex、refDistance和 refPoint字段，并将 bMoved赋值为True。

若在结点vi的容限距离d内找到多条参考边，取refDistance最小者为捕捉目标，并更新refGeomOID、refPartIndex、refSegmentIndex和 refDistance和refPoint。如图5所示，结点 vi到参考边 lref和的距离都小于容限，取间距更小的参考边为vi捕捉的目标对象。

图5 将间距最小的参考边作为捕捉目标Fig.5 The nearest reference works as snapping target

若在结点vi的容限距离d内没有任何参考边，并且它是一个bIsAdded值为True的附加结点，将其从链表中删除。

3)调整捕捉点到参考边结点。依据refGeomOID、refPartIndex、refSegmentIndex取得结点 vi的捕捉点所在的参考线段。若该结点到参考线段的某个端点uk的距离小于容限，则将其捕捉点改为端点uk。如图6所示，v3到参考线段的端点u4的距离小于容限，将其捕捉点由垂足u3改为结点u4;v1和v2在参考边上的捕捉点分别为结点u1和垂足点u2，保持不变。

图6 将捕捉点调整到参考线段的端点Fig.6 Adjust snapped points to segments'ends

4)调整结点次序。遍历SnapList链表，依据bMoved、refGeomOID和refPartIndex将其划分成若干个子序列。同一个子序列中的各个结点全部未捕捉，或者全部被捕捉到同一条参考边;不同的子序列中的结点被捕捉到不同的参考边。同一个子序列中的各个结点的捕捉点所在的参考线段序号应该是单调增加或单调减少的。如果某个子序列中起点和终点对应的参考线段序号是增大的，但其内部某些相邻结点对应的参考线段序号是减小的，则在这些参考线段序号减小的结点的捕捉点处发生了方向反转，引起自相交问题;反之，如果某个子序列中起点和终点对应的参考线段序号是减小的，参考线段序号增大的结点的捕捉点处发生了方向反转。具体检测时，如果相邻两个捕捉点的refSegmentIndex相等，还需进一步计算fromPointDistance来判断结点前进方向。

若相邻两个捕捉点v'i到v'i+1存在方向上的反转，依次回退检测v'i的前一个捕捉点v'i－1到v'i+1是否存在方向上的反转;若满足反转条件，继续比较v'i－1的前一个捕捉点v'i－2，直到某个前驱捕捉点v'k到v'i+1不存在方向反转为止。此时，将v'i+1从链表中删除后重新插入到v'k之后的位置，从而消除v'i+1引起的反转现象。依次处理该子序列中的反转捕捉点，直到消除所有反转现象。

如图7所示，输入边ledit上的5个原有结点v2、v3、v4、v5、v6和1个附加结点v8被捕捉到参考边lref上。输入边捕捉处理后的结点序列为v'1、v'2、v'3、v'4、v'5、v'8、v'6、v'7。其中，v'2v'3与 v'3v'4、v'3v'4与 v'4v'5、v'3v'4与 v'5v'8之间存在自相交问题。经过纠正处理后，结点序列将调整为v'1、v'4、v'2、v'5、v'8、v'3、v'6、v'7。

图7 处理捕捉点顺序反转引起的自相交问题Fig.7 Processing reversed snapped points

(5)依据链表中保留的结点的捕捉点构造一条新边线。其中，某个结点无捕捉点时用原坐标点代替。判断边线上相邻的三个结点是否共线，删除共线的多余的结点，得到最终的捕捉处理结果。

3 实验结果与分析

在土地利用变更调查中，新调绘的本年度变更图斑需要与上一年度的地类图斑协调一致。如图8(a)所示，分别以本年度的变更图斑和上一年度的地类图斑为输入图形和参考图形，输入边与参考边非常接近但又不完全重合。本次实验中将捕捉容限设定为1 m，输入边上全部10个结点到参考边的距离都小于容限，线段v9v10到结点h的距离大于容限。

本文算法捕捉处理结果见图8(b)。其中，输入边按间距1 m加密结点。分析捕捉线发现，输入边上的全部结点都被捕捉到参考边;而且除线段v8v9之外，其余组成线段与参考边完全重合。实际上，除参考边的结点h之外，输入边和参考边相互之间的距离均小于容限，因此捕捉处理是完全的和准确的。

作为比较，我们给出了ArcGIS软件捕捉处理的结果，其捕捉类型设为Edge和Vertex，分别见图8(c)和图8(d)。ArcGIS提供批量捕捉结点的功能，其捕捉结果有一定的代表性。在图8(c)中，输入边上的线段 v1v2、v2v3、v3v4、v5v6和v8v9未被捕捉到与参考边重合;线段v3v4与v4v5之间存在自相交问题。在图8(d)中，结点v5和v7未被捕捉到参考边，线段 v1v2、v6v7、v7v8和v8v9未被捕捉到与参考边重合。这两种捕捉结果都不符合要求，未实现有效的边线捕捉。

从结点捕捉的有效性看，本文算法将原结点捕捉和附加结点都捕捉到容限距离内参考边上正确的位置;而ArcGIS软件计算的捕捉点偏离参考边上对应的结点，或者没有捕捉到容限距离内的参考边。从结点之间的线段来看，本文算法将各条线段准确捕捉到容限距离内与参考边重合的位置;而ArcGIS软件捕捉处理后的线段并不与参考边完全重合。从图形的拓扑正确性看，本文算法处理结果中不存在线自相交错误;而ArcGIS软件处理结果不能排除自相交错误。这三个方面体现了本文算法的有效性和可靠性。

4 结论

根据以上研究和实验，可以得到以下结论:

1)通过调整捕捉点到容限距离内的参考边的结点，本文算法实现了输入边结点与参考边结点的严密配准。

2)本文算法在边线上插入附加结点，实现了边线层次的配准和捕捉处理。通过对附加结点的捕捉和移动，使一些直线段转换为折线段，从而捕捉到与容限距离内的参考边完全重合的位置。

3)结点捕捉改变了结点的相对位置，从而引起线自相交错误。本文算法引入的结点顺序调整处理步骤有效地消除了结点次序反转现象，解决了捕捉后的边线的自相交问题。

4)本文方法实现了线层次的图形捕捉处理，相对于以ArcGIS为代表的结点捕捉算法而言能更有效地进行图形数据融合。

［1］SAALFELD A.Conflation:automated map compilation［J］.International Journal of Geographical Information Systems，1988，2(3)，pp.217 －228.

［2］SERVIGNE S，UBEDA T.A Methodology of Spatial Consistency Improvement of Geographic Databases ［J］.GeoInformatica，2000，4(1):7－34.

［3］SAMAL A，SETH S，CUETO K.A feature-based approach to conflation of geospatial sources［J］.International Journal of Geographical Information Science，2004，18(5)，pp.459－489.

［4］鲁伟，谢顺平，邓 敏，周立国.多源空间数据间不一致性研究现状及其进展［J］.测绘科学，2009，34(4):57－60.

［5］韩凌云，杨英力.地形图与海图拼接的矛盾问题及其处理［J］.海洋测绘，2003，23(4):33－35.

［6］吕蓬，张立朝，王耿峰.空间数据融合在海图中的应用［J］.测绘通报，2007，(11):43－45，56.

［7］吴磊，黄先锋，舒宁.GIS大数据量编辑处理中快速捕捉的优化策略［J］.武汉理工大学学报:交通科学与工程版，2005，29(2):315－318.

［8］刘文宝，夏宗国，崔先国.GIS结点捕捉的广义算法及误差传播模型［J］.测绘学报，2001，30(2):140－147.

［9］邓敏，刘文宝，冯学智.GIS中地理边线不一致性的处理［J］.遥感学报，2005，9(4):343－348.