线目标间存在多种空间拓扑关系约束条件，是数据组织、更新与一致性检查的基础^{[1, 2]}。例如在空间数据增量更新中，河流往往相对稳定，道路为基础设施，发展迅速。新修道路后，一般通过外业测量新增道路的空间位置，再通过与已有地图数据进行叠加，通过拓扑关系计算、语义规则等方法来处理一致性冲突、构建变化后的河流等。如新修道路与已有河流间如存在“交叉”关系则被认为是存在冲突，需要插入桥梁或隧道等符号；而存在“相接”关系在某些比例尺中则是合理的。道路和较小河流在中小比例尺中常用线目标来表达，如在图 1中(见文末)，亮红色线表示更新后的道路，绿色线表示已有地图中的河流。图 1(a)、图 1(c)表示的是“交叉”关系，表示道路跨越了河流，需要插入桥梁或隧道符号。图 1(b)表示的是“相接”关系，可能是合理关系，或道路与河流平行，由于表达的尺度和精度等原因导致道路与河流重叠。因此线目标间的相接、交叉关系的区分在空间更新与质量控制处理中有着重要作用。

图 1中的道路跨越河流的拓扑关系在目前通用的4I、9I模型中都表达为“内部/内部”有交，但“内部/内部”有交又包括多种细分情况，如交点的“相接”、“交叉”,交线的“相接”、“交叉”等，而4I、9I模型不能区分上述细分情况。

近年来，随着拓扑关系研究与应用的深入发展，国内外多位学者在线/线拓扑关系的分类与细化计算方面开展了大量的研究工作，取得了可喜的研究成果。文献^[3]对线/线交进行了相接、交叉类型的细化分类，但未给出具体计算算法。文献^[4]提出了线线空间关系描述的拓扑链模型与线目标间拓扑关系的细化计算方法，其中涉及线/线交的相接、交叉的计算算法，但该方法仅适用于交点的相接、交叉关系的判断，不能计算交线的相接、交叉类型。文献^[5]提出的线目标间拓扑关系细化计算的分解一组合方法，将线分解，计算局部拓扑关系，再将局部拓扑关系按照一定顺序组成拓扑链来表达线线之间的拓扑关系，此方法不能判断相接交线与交叉交线。文献^[6]提出的GIS线目标间空间关系的集成表达方法，建立一个综合描述线目标拓扑、方向、距离关系的方法，此模型中涉及多种空间关系的度量，描述复杂，不易于交流。而在Oracle空间数据库中应用广泛的空间线线拓扑关系也只给出了11种基本空间拓扑关系查询的操作算子，文献^[7]提出的基于Oracle Spatial的空间线线拓扑关系判断的实现，描述了33种线线空间关系，但并不包括相接、交叉分类^{[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]}。

总之，目前尽管在线/线拓扑关系的描述、区分与细化计算方面取得了可喜的研究成果，但仍缺少线/线“相接”“交叉”细化类型的判断算法，不能满足数据更新、数据质量检查等对拓扑关系细化计算的应用需求。因此本文提出一种基于局部平面分割的线/线交点和交线的相接、交叉类型的判断算法。该算法采用局部平面分割的基本思想，在线/线交的邻域内，一条线将邻域平面分割成两个平面区域，通过判断另一条线中与交相连的两线段是否处于同一个平面区域，确定该交的相接、交叉类型。

文献^[3]将线/线交的相接、交叉类型定义为：两线l_A、l_B相交，如图 2所示(粗直线表示l_A，细虚线表示l_B)，构建交的邻域，在交的邻域内，将与交点(线)相连的线段按顺时针排序，得出线段序列T(k)=(a₁,a₂,a₃,a₄)。如果同一线目标中的两线段在该序列中不相邻，称为交叉交类型，如图 2(a)、(b)所示，a₁、a₃属于线l_A，a₂、a₄属于线l_B；如果同一线目标中的两线段在该序列中相邻，称为相接交类型，如图 2(c)、(d)所示，即a₁、a₂属于线l_A，a₃、a₄属于线l_B^[2]。

图 2 线/线交的相接、交叉定义示意图 Fig. 2 Examples of the crossing and touching intersection types

图选项

通过分析图 2，发现交的邻域总会被线目标分割。如图 2中l_A总是把邻域分成两个平面区域，l_B中与交相连的两线段总会落在这两个平面区域内。而且在交叉交的邻域内，T(k)中l_A、l_B与交相连的线段序列相互交叉，l_B中的两线段处于两个不同的平面区域。在相接交的邻域内，l_B中的两线段落在同一平面区域。因此，如果可以判断l_B中与交相连的两线段是否被l_A分割到同一平面区域，就可以判断交的相接、交叉类型，这就是局部平面分割的思想。

应用于局部平面分割的计算几何原理是由矢量叉积的性质推出的。性质描述为：设向量M、Q，若M×Q>0,则M在Q的顺时针方向。若M×Q＜0,则M在Q的逆时针方向。若M×Q=0,则M与Q共线，但可能同向也可能反向。

根据上述定理求已知坐标的两点B₁、B₂是否被已知线段l_A1A2分割到同一平面区域，可以判断矢量叉积 与的符号是否相同，总结为式(1)

点击浏览公式

此时，如果Side(l_A1A2,B₁,B₂)值为true，那么B₁、B₂在线段l_A1A2的同一侧，即分割到同一平面区域。这一方程可以直接应用到最简单的平面分割情况——点A₁、A₂与交点P在一直线上时(如图 2(a)所示)，直接判断矢量、、之间的关系。

如果点A₁、A₂与交点P不在一直线上时，即折线段l_A1PA2将邻域分割成两个平面区域Ⅰ、Ⅱ，如图 3(a)。向量与及其延长线将邻域分割成ⅰ、ⅱ、ⅲ、ⅳ4个辅助性区域，如图 3(b)，此时区域Ⅰ与辅助性的区域ⅰ完全相等，选取将这一独立的辅助性区域(ⅰ区或Ⅰ区)内的一点——例如A₁、A₂的中点P_Z，作为参考点，向量叉积×与×的正负符号就代表了Ⅰ区内任一以点P为起点的向量与与叉积的结果。如果判断、是否在同一平面区域，只需要将(×，×)、(×，×)与(×、×)作比较，分别判断、与是否在同一区域，当、与都在同一区域或都不在同一区域时，交点是相接交，否则是交叉交。以判断与是否在同一区域为例，总结为式(2)

点击浏览公式

如果Side(l_A1PA2,B₁,P_Z)的值是true，那么与在同一区域。同理可以判断。

图 3 折线段分割局部平面的计算原理 Fig. 3 The calculation principle of segment splitting the disc

图选项

利用式(1)和式(2)可以计算所有相接/交叉的交点类型。而交线的邻域中存在更复杂的平面分割，如图 2(b)、(d)。此时需要进行简化。如果分别以交线的首尾节点P₁、P₂为圆心做辅助性的节点圆形邻域，如图 4(a)、(b)，那么在每一个节点圆形邻域内，线l_A都将邻域圆分割为两个不同的区域。引入交线的方向P₁→P₂，被分割的平面区域统一就归纳为l_P1→P2的左侧区域与l_P1→P2的右侧区域。此时，利用上述分割定理分别确定PB₂、PB₁处于节点圆邻域中的左侧区域还是右侧区域，就可以判断B₁、B₂是否处于l_P1→P2的同一侧。

图 4 交线相接/交叉类型的计算方法 Fig. 4 The method of dividing line intersections into touching and crossing

图选项

假设：线l_A、l_B相交于点P，l_A中与点P相连的形状点为A₁、A₂，l_B中与点P相连的形状点为B₁、B₂。

此时，基于上述理论，在线/线交点的邻域中，选取l_A将邻域分割为两个平面区域。由于分割线的类型不同，使用的原理也不同。所以，先判断l_A在邻域内的部分是否是直线段。判断方法：交点P是否是l_A的形状点。

如果P不是l_A的形状点，那么l_A在邻域内的部分是直线段。将矢量代入式(1)，判断的值，如果Side(l_PA2,B₁,B₂)=true，那么B₁、B₂在被分割到同一平面区域，交点P是相接；如果Side(l_PA2,B₁,B₂)=False，那么B₁、B₂被分割到不同平面区域，交点P是交叉。总结为规则一。

规则1：P不是形状点

如果Side(l_PA2,B₁,B₂)值为真，那么交点P是相接交，否则交点P是交叉交。

如果P是l_A的形状点，计算l_A1A2的中点P_Z，分别将代入式(2)，如果Side(l_A1PA2,B₁,P_Z)=true,那么B₁与点P_Z被分割到同一平面区域。同理，如果Side(l_A1PA2,B₂,P_Z)=true，那么B₂与点P_Z被分割到同一平面区域。如果B₁、B₂被分割到同一平面区域，那么交点P是相接。如果B₁、B₂被分割到不同平面区域，那么交点P是交叉。总结为规则2。

规则2：P是形状点

如果Side(l_A1PA2,B₁,P_Z)∧Side(l_A1PA2,B₂,P_Z)值为真，那么交点P是交叉交，否则交点P是相接交。

3.2 交线相接\交叉类型计算规则

假设：线l_A、l_B相交于线l_P1P2，交线l_P1P2的端点是P₁、P₂，l_A中分别与点P₁、P₂相连的形状点为A₁、A₂，l_B中分别与点P₁、P₂相连的形状点为B₁、B₂。

此时，可以利用直线分割平面原理进行计算。引入l_A的方向，交线的方向P₁→P₂，这两个方向必须完全一致。此时，在P₁的节点圆形邻域中确认B₁的左右位置，在P₂的节点圆形邻域中确认B₂的左右位置，就可以求出B₁相对l_A的左右位置的值，用Right(l_A,B₁)表示，值为布尔型，B₁在l_A的右侧时值为真，B₂相对l_A的左右位置Right(l_A,B₂)，就可以总结出交线l_P1P2的类型。

以求点B₁的位置为例，查找交线中与P₁相连的节点P_f，第一步同样是判断A₁→P₁→P_f是否是一直线段。判断方法可以采用：判断交线节点P₁是否是l_A的形状点。

如果P₁不是l_A的形状点，那么l_A在节点邻域邻域内的部分是直线段，根据×的叉积结果判断与向量(与P₁→P₂的方向一致)的左右关系，如果×＜0，那么Right(l_A,B₁)=True，在l_A的右侧。

规则3：P不是形状点

Right(l_A,B₁)=×＜0 ?true:false

如果P₁是l_A的形状点，此时求B₁与l_A1P1Pf的左右关系。求出A₁、P_f的中点P_Z1，将向量代入式(2)，求出(×)·(×)>0&(×)·(×)>0的值，确认B₁与P_Z1是否分布在同一区域。根据规则3计算P_Z1与有向线l_A的左右位置关系Right(l_A,P_Z1)=×＜0 ?true:false。如果B₁与点P_Z1被分割到同一平面区域，B₁与点P_Z1所处的左右位置关系相同；如果B₁与点P_Z1被分割到不同的平面区域，B₁与点P_Z1所处的左右位置关系相反。总结为规则4。

规则4：P是形状点

如果Side(l_A1P1Pf,B₁,P_Z1)值为真，那么Right(l_A,B₁)=Right(l_A,P_Z1)，否则Right(l_A,B₁)=﹁ Right(l_A,P_Z1);

同理可以判断B₂，查找交线中与P₂相连的节点P_l，计算的关键在于统一交线的方向，即确定P_l→P₂→A₂的方向与P₁→P₂的方向一致。这样才能确保求得的B₁、B₂的左右位置是绝对的。最后，总结B₁、B₂的左右位置得出交线的类型，总结为规则5。

规则5：如果Right(l_A,B₁)∧Right(l_A,B₂)值为真，那么交线l_P1P2是交叉交，否则交线l_P1P2是相接交。

总结3.1与2.2，可以将线线交的相接\交叉类型计算归纳如下。

假设：线l_A与线l_B，求出两线的交类型。函数Inter(l_A,l_B)为求线l_A与线l_B的交。定义P_Z为变量点对(q₁,q₂)的中点；定义l_A的节点与形状点为点集shapept。Right(l_A,B₁)是求点B₁与有向线l_A的左右方向的函数，值为布尔型，B₁在l_A的右侧时值为真。

(1)Inter(l_A,l_B)得出交集，其中交点集为Pt，交线集为Line。

(2)求交点集Pt中的每一个元素Pt[i]的相接\交叉类型。查找l_A中与Pt[i]相连的节点A₁、A₂，l_B中与Pt[i]相连的节点B₁、B₂。如果Pt[i]与shapept中的元素相等，令P_Z为(A₁,A₂)的中点，进行Side(l_A1PA2,B₁,P_Z)∧Side(l_A1PA2,B₂,P_Z)运算，值为真时点Pt[i]是交叉，值为假时点Pt[i]是相接，利用规则一求出Pt[i]的类型；如果Pt[i]与shapept中的元素全不相等，进行Side(l_PA2,B₁,B₂)运算，值为真时点Pt[i]是相接，值为假时点Pt[i]是交叉。

(3)求交线集Line中的每一个元素的类型。计算的流程总结如图 5所示。其中，Line[i]表示交线集Line中元素，头结点为P₁，尾节点为P₂。A₁是l_A中与P₁相连的节点，P_f是Line[i]中与P₁相连的节点，B₁是l_B中与P₁相连的节点。如果P₁→A₁→P_f在一条直线上，即P₁是形状点shapept，利用规则3求出B₁的左右位置，其中l_A1Pf表示由点A₁→P_f的有向线段。否则，令P_Z为(P₁,P_f)的中点，利用规则4求出B₁的左右位置，其中l_A1P1，l_P1Pf表示由点P₁、A₁与P₁、P_f构成的两条直线段。l_A中与P₂相连的节点是A₂，Line[i]中与P₂相连的节点是P_l，l_B中与P₂相连的节点是B₂。如果P_l→P₂→A₂在一条直线上，利用规则3求出B₂的左右位置；否则，令P_Z为(P₂,P_l)的中点，利用规则4求出B₂的左右位置。最后规则5求出Line[i]的类型。

图 1 道路线与河流线相交的3种细分类型 Fig. 1 Three intersection types including between rivers and roads

图选项

图 5 交线相接\交叉计算流程 Fig. 5 Calculation flow chart of dividing intersections into touching and crossing

图选项

为了验证本文的方法与模型，在增量采编原型系统上，用Visual Studio 2008的C#编程实现了基于局部平面分割的线/线交相接、交叉类型计算方法。

图 6是一幅1∶25万中国行政区道路与河流网地形图的局部，其中，道路经过更新，图中红色的线表示更新后的道路，绿色线表示河流。选取这一条更新后的道路线(红色粗实线)，与一条相交的河流线(深绿色粗实线)，用本文提出的方法计算了该道路线与该河流线之间相接、交叉交的类型，并且分别用蓝色高亮显示相接交与交叉交。计算结果如图 6所示，(a)图中高亮显示了两条线的交叉交，包括一条交线与两个交点，(b)图中高亮显示了两条线的相接交，只有一个交点。试验验证了本文计算方法的正确性。可以在判断相接、交叉类型的基础上进行下一步处理，在交叉交的位置按照实际情况插入跨河的桥梁或隧道。

图 6 试验实例图 Fig. 6 Data of test

图选项

论文阐述了直线分割平面的计算原理，根据几何代数中直线分割平面定理，按照一条直线分割平面、两条相交直线分割平面和有向直线段分割平面3种情况推导出3个原理方程；提出了计算交相接/交叉类型时的5条规则，分别适用于交点邻域中的两种不同的分割情况和交线头尾节点邻域中的两种不同的分割情况；给出了线线交叉、相接交分类计算的算法流程。最后，在数据更新系统平台中用Visual Studio 2008的C#编程实现了该方法，并以中国道路与河流网为实验数据进行了试验，验证了算法的正确性。

目前在拓扑关系描述区分方面的模型较多，但在拓扑关系细化计算方面的成果仍不能满足应用需求。因此本文的后续研究工作包括：① 将继续研究线线拓扑关系的其他细化算法，并考虑将线线交叉、相接细分类型判断算法应用到线面拓扑关系的细化计算中；② 探索线线交叉、相接细分类型的实际应用，如，GIS不同类型线要素间具有交叉、相接关系类型在数据库更新中所对应的目标重构与更新处理方法，在数据质量控制中对应的冲突类型与处理算法等。