判断折线自相交的完备算法与快速显示技术

魏志云 王国光 李成翔

摘要：折線自相交是地理信息系统（Geographic Information System，简称GIS）空间线性数据检查处理中的一个重要问题，如何快速判断、准确定位是这个问题的关键。在对MicroStation API熟练掌握并运用的基础上，对折线自相交中存在交叉、重复、重叠的情况进行全面分析，解决了API开发库函数无法对线段重叠情况下的相交判断问题，并最终实现求交结果的预览和快速显示功能，极大方便用户快捷、准确地辨识折线自相交的类型和位置。

关键词：GIS；MicroStation；自相交；快速显示

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）06-0229-03

在地理信息数据质量控制中，折线自相交是影响线型数据质量的关键因素，在地图综合、空间分析等领域有着广泛的应用。例如，地图上的等高线、水系、境界等线状要素的综合，要求同代表某一要素的折线自身不能相交。但是由于地图上的曲线具有复杂、多样和密集等特点，运用一定的算法化简后不可避免地产生自相交，因此需要设计一套合适的算法来消除这种现象。

近年来，国内外学者在判断折线自相交方面开展了一些工作，但都存在效率不高的问题。MicroStation是一款三维CAD设计软件，具有强大的API开发库函数，为该软件的二次开发提供了很好的接口。目前该软件库函数对于线段内部相交的情况有较好的解决，而对于线段重叠的情况则没有考虑，因此设计一套完备的求交算法，弥补线段求交的不足显得非常必要。

本文利用MicroStation API开发库函数求解一般情况下的折线自相交，详细分析了折线自相交在重复、重叠情况下的自相交，全面而又准确地判断出折线自相交的类型和位置，为用户快速判断折线自相交提供了一种可靠方法。

1折线自相交判断相关定义

1.1折线自相交的定义

设有折线L={p₁，…p_i，…p_n}，（i=1，2，…，n），p_i是折线上顺次相连线段的端点。若除了相邻线段间的连接端点p₁，p₂，…，p_n外，折线上的线段之间还存在其他的交点，则定义此折线为自相交折线。

1.2判断折线自相交的一般算法

判断折线自相交一般采用如下算法：对于折线三上的线段，按照其连接顺序分解为n-1条两点组成的线段，然后两两判断这些线条之间是否相交，根据交点情况和自相交的定义来判断折线L是否自相交。该算法很成熟，在相关论文中已经有介绍，在此不予给出。

折线自相交的一般算法对于线段内部相交适用，但对于线段重叠情况下的相交无法判断，如完全重叠、部分重叠等。本文在MicroStation已有函数的基础上，补充折线自相交在重叠情况下的判断，完善了折线自相交的全部情况。

1.3折线自相交的分类

为了更好的说明问题，将自相交分为：重点式自相交、交叉式自相交、重叠式自相交三种情况，相交结果分成重复点、交点＼重叠点、重叠线三类。

（1）重点式自相交判断

重点式自相交是折线中连续两个或者多个顶点出现在同一位置，也即折线中存在长度为零的线段，它是折线自相交中一种常见类型。在绘制地图线性要素的时候，难免会出现重复点现象，如图1所示。

对折线中重复点进行排除算法比较简单，只需要比较当前点与下一个节点坐标是否相等即可，若该点与下一顶点坐标一样，则判断该点为重复点，并将下一顶点删除，依此循环判断。

（2）交叉式自相交判断

交叉式自相交是折线中不平行线段之间产生交点，包括内部点和端点，它是折线自相交的一种普遍类型。交叉式自相交判断用到MicorStation API中三维线段求交函数mdlVec_inter-sectXYZLines，该函数需要分别输入两条线段的首尾端点坐标以及容差，输出交点坐标、交点分别在两条线段中的比例参数paramAP和paramBP。

根据比例参数paramAP、paramBP，在排除外部相交的情况下，可将交叉式自相交分为如下4类。

（3）重叠式自相交判断

为了加快判断速度，在判断重叠式自相交之前，增加两线段是否平行的判断，这里用到MicroStation API中向量平行测试函数mdlVec_areParallel。

重叠式自相交是折线中平行线段间的重叠，包括重叠点和重叠线，它是折线自相交的一种特殊类型。重叠点是指两线段中某一端点坐标相同；重叠线是指两线段中某一段坐标相同。为了全面分析相交的情况，本文采取端点距离判断法，实现重叠式自相交的判断，其算法思想如下：

2）一端点重合

如果端点距离Dist（i，j）、Dist（i，j+1）、Dist（i+1，j）、Dist（i+1，j+1）中仅有一个为零，则判断为一端点重合，相交结果为重叠点或重叠线。首先将其分为如下4大类，然后每大类又可分成3种具体情况，需要根据其余四个距离之间的关系进一步判断相交结果，其示意图解如表3。

3）无端点重合

如果端点距离Dist（i，j）、Dist（i，j+1）、Dist（i+1，j）、Dist（i+1，j+1）都不为零，则判断为无端点重合，相交结果要么是部分重合，也即相交结果为重叠线，要么不相交。本文对于部分重合的情况罗列如下。

2判断折线自相交的完备算法

基于以上对折线自相交判断的详细分类和求解方法介绍，研究出一套完整的折线自相交判断算法，该算法基本步骤如下。

第一步：设折线选择集LS的个数为m，遍历LS，获取折线LS（i）的坐标信息，其中i=0，1，…，m-1；

第二步：首先對折线LS（i）进行重点式自相交判断，若有重复点，则将重复点添加到相交集合中，并将该重复点从折线点集中删去。

第三步，设折线LS（i）上点的个数为n，则将折线看成n-1条依次相连的线段构成，判断折线自相交即可分解为判断这n-1条线段两两之间是否相交。将第i条线段记为L（j），其中j=0，1，…，n-3；其后的n-j-1条线段中的一段记为L（k），其中k=j+1，…，n-2。第{条都要与其后的n-j-1条线段进行求交计算，时间复杂度为O（n²）。

第四步：判断线段L（j）与线段L（k）矩形外包是否有交集，若有交集，则跳到第五步，否则返回到第三步进行下一对线段的相交判断；

第五步：应用MicroStation自带三维求交函数mdlVec_inter-sectXYZLines进行求交计算，若求交成功，则根据比例参数进一步判断是否交叉式自相交，若是交叉式自相交则求出交点，并将交点添加到相交集合中，返回到第三步进行下一对线段的相交判断；若不成功，则跳到第六步。

第六步：应用MicroStation自带向量平行测试函数mdlVec_areParallel判断两条线段是否平行，若平行，则进行重叠式自相交判断，并求出重叠点或重叠线的坐标，并将相交结果添加到相交集合中，最后返回到第三步进行下一对线段的相交判断。

根据以上步骤，其算法流程图如图4所示。

3计算结果的预览和快速显示

为了让用户更加方便地了解相交的位置和类型，本算法增加了相交结果的预览和陕速高亮显示功能。

相交结果预览采取序号和相交类型组成，相交类型可分为三种：交点/重叠点、重叠线、重复点，分别用0、1、2及以上表示，其对应关系如表4所示。

在MicroStation中，开发者可以通过绘制临时元素和临时几何图形两种方式实现相交结果的高亮显示。二者的区别在于MicroStation Development Library（MDL）函数只能创建一个普通的元素，然后将该元素转化为临时元素，当视图变化、元素较多时，临时元素会不断地被创建，占用较大内存，显示延迟；而通过MicroStation API中的IviewTransients接口可以定义任意几何形状，无需创建元素，能更方便快速地控制其在视图更新过程中的显示。

显然，用户期望知道相交结果的位置，然后手动修改，而不希望该相交结果变成临时元素被不断添加到视图中，影响效率。因此，本文采取第二种方法，通过IviewTransients接口生成临时几何图形，用户可以通过双击预览数据列表行，精确定位该相交位置。

从图5、图6测试实例中我们可以得出，根据以上算法求解的自相交情况与实际情况相当吻合，用户可以掌握全部自相交的数据，并能快速定位，提高了查找效率，为用户进一步调整提供了很大的方便。

4结束语

本文在MicroStation API的基础上，对折线自相交进行了详细分类，。考虑了折线自相交会出现的所有情况，采用距离判断法解决折线某段重合下的自相交，从而设计出判断折线自相交的完备算法。由于在进行自相交计算之前需要通过矩形外包交集测试，因此该算法能快速判断线性元素是否自相交。

利用IviewTransients接口实现相交结果的快速显示，对于海量数据自相交结果的显示，其优越性更加明显。该算法提高了数据处理效率和数据的准确性，便于用户准确定位并进行手动调整，具有实现简单、检查全面、易于查找、稳定性好等特点。