专利摘要

本发明公开了一种多环多边形自相交模式识别及处理方法，包括获取多环多边形中组成该多环多边形的节点与线段，以逆时针方向进行标识，获取该多环多边形的外环和内环；计算每个线段的最小外包矩形，并建立R树索引，识别与某一线段的最小外包矩形彼此相交的所有最小外包矩形，组成多个最小外包矩形对，放入该线段的待处理候选集中等步骤。优点是：依据构成自相交模式要素之间的空间关系，细化多环多边形自相交的模式类别，并利用要素间拓扑及距离关系，实现不同类型自相交模式的自动识别；利用顾及冲突区域及最小可视距离约束的移位和内缩算法，对多环多边形的各种自相交模式进行处理，保证处理结果同时满足拓扑、形状一致性和视觉可分辨性。

权利要求

1.一种多环多边形自相交模式识别及处理方法，其特征在于：包括如下步骤，

S1、获取多环多边形中组成该多环多边形的节点与线段，以逆时针方向进行标识，获取该多环多边形的外环和内环；

S2、计算每个线段的最小外包矩形，并建立R树索引，识别与某一线段的最小外包矩形彼此相交的所有最小外包矩形，组成多个最小外包矩形对，放入该线段的待处理候选集中；

S3、在该线段的待处理候选集中任选一个最小外包矩形对，判断其内线段的相互位置，若其内线段位于同一边界线，则转化为单环多边形自相交进行处理；若其内线段分别位于内环和外环，则进入S4；若其内线段位于不同的内环，则转化为多边形共享边界一致性改正问题进行处理；

S4、针对该最小外包矩形对，任选其中一条线段作为参考线段，由所述R树索引探测与该参考线段相邻或相交的匹配线段，得到由该参考线段和与其对应的匹配线段构成的自相交线段对，并获取该自相交线段对中两条线段各自的首末节点；计算该自相交线段对中两线段首末节点之间的距离、匹配线段的首末节点到参考线段之间的距离，并将以上距离与预设的距离阈值进行比较判断，进而确定该多环多边形的自相交模式；

S5、判断R树索引中所有的线段是否全部完成计算，若否，则返回步骤S2，选择下一条线段进行计算；若是，则识别算法结束，进入步骤S6进行处理；

S6、判断该多环多边形内环的各个线段与外环的距离是否都小于距离阈值，若否，则采用移位算法进行处理；若是，则采用内缩算法进行处理；

所述移位算法具体为，根据距离阈值设置合理的移位距离，并根据探测到的该多环多边形各种自相交模式出现的位置，依据各种自相交模式，分别确定其初始移位方向；然后通过Delaunay三角网进行潜在冲突区域探测，即针对多环多边形的内环和外环边界线，建立约束Delaunay三角网，并以内环线段为基本单元，以桥接三角形高的最小值作为其与外环的距离，其中桥接三角形是指存在一边为内环边界的三角形；最后，依据潜在冲突，调整移位方向，即若某一内环线段与外环之间的距离小于距离阈值，则说明不宜向该方向移位，则需在初始移位方向中减去该方向，并以校正后的方向作为最终移位方向，沿最终移位方向移动移位距离；

所述内缩算法具体为，沿节点角平分线方向，将该节点向该多环多边形内部移动移位距离，并与最近边界相隔的距离为原有判断时确定的距离阈值。

2.根据权利要求1所述的多环多边形自相交模式识别及处理方法，其特征在于：步骤S4具体包括如下内容，

S41、若存在某一匹配线段首末节点到参考线段首末节点之间的距离为0，且匹配线段首末节点到参考线段之间的距离大于距离阈值，则判定该多环多边形存在外环上的节点与内环上的节点相交产生的自相交模式；

S42、若存在匹配线段首节点到参考线段之间的距离为0，匹配线段末节点到参考线段之间的距离大于距离阈值，且匹配线段首节点到参考线段首末节点之间的距离大于距离阈值；或者存在匹配线段末节点到参考线段之间的距离为0，匹配线段首节点到参考线段之间的距离大于距离阈值，且匹配线段末节点到参考线段首末节点之间的距离大于距离阈值，则判定该多环多边形存在外环上的节点或线段与内环上的线段或节点相交产生的自相交模式；

S43、若匹配线段与参考线段相交，则判定该多环多边形存在外环上的线段与内环上的线段相交产生的自相交模式；

S44、若存在某一匹配线段首末节点到参考线段首末节点之间的距离大于0但小于等于距离阈值，且匹配线段首末节点到参考线段之间的距离大于距离阈值，则判定该多环多边形存在外环上的节点与内环上的节点相离产生的自相交模式；

S45、若存在匹配线段首节点到参考线段之间的距离大于0但小于等于距离阈值，匹配线段末节点到参考线段之间的距离大于距离阈值，且匹配线段首节点到参考线段首末节点之间的距离大于距离阈值；或者，存在匹配线段末节点到参考线段之间的距离大于0但小于等于距离阈值，匹配线段首节点到参考线段之间的距离大于距离阈值，且匹配线段末节点到参考线段首末节点之间的距离大于距离阈值，则判定该多环多边形存在外环上的节点或线段与内环上的线段或节点相离产生的自相交模式；

S46、若存在匹配线段首末节点到参考线段之间的距离均大于0但小于等于距离阈值，则判定该多环多边形存在外环上的线段与内环上的线段相离产生的自相交模式；

S47、若存在匹配线段首末节点到参考线段之间的距离均为0，且匹配线段首末节点到参考线段首末节点之间的距离大于0，则判定该多环多边形存在外环上的线段与内环上的线段部分共线产生的自相交模式；

S48、若存在匹配线段首节点到参考线段首节点之间的距离为0，且匹配线段末节点到参考线段末节点之间的距离为0；或者存在匹配线段首节点到参考线段末节点之间的距离为0，且匹配线段末节点到参考线段首节点之间的距离为0，则判定该多环多边形存在外环上的线段与内环上的线段完全共线产生的自相交模式；

S49、判断该线段的待处理候选集中所有的最小外包矩形对是否全部处理完成；若否，则返回步骤S3；若是，则判断某一类自相交模式是否重复出现；若重复出现，则判定该多环多边形存在某一类自相交模式重复出现的复杂自相交模式；若不重复出现，则判断该多环多边形是否同时出现多类自相交模式，若是，则判定该多环多边形存在多类自相交模式同时出现的复杂自相交模式，若否，则结束判断，进入步骤S5。

3.根据权利要求2所述的多环多边形自相交模式识别及处理方法，其特征在于：各个自相交模式的初始移动方向分别为

A、针对外环上的节点与内环上的节点相交产生的自相交模式；探测该模式相交点，并获取该相交点与其在内环上关联的两条线段所构成的夹角，则其初始移动方向为，沿该夹角角平分线方向且指向该多环多边形内部；

B、针对外环上的节点或线段与内环上的线段或节点相交产生的自相交模式；该模式的初始移动方向获取方式与A相同；

C、针对外环上的线段与内环上的线段相交产生的自相交模式；探测该模式中的两条内环线段，并获取该两条线段所构成的夹角，则其初始移动方向为，沿该夹角角平分线方向且指向多环多边形内部；

D、外环上的节点与内环上的节点相离产生的自相交模式；探测该模式中位于内环上的节点，并获取该节点与其在内环上关联的两条线段所构成的夹角，则其初始移动方向为沿该夹角角平分线方向且指向多环多边形内部；

E、外环上的节点或线段与内环上的线段或节点相离产生的自相交模式；该模式的初始移动方向获取方式与D相同；

F、外环上的线段与内环上的线段相离产生的自相交模式；探测该模式中位于外环上的线段，则其初始移动方向为，垂直于该线段并指向该多环多边形内部；

G、外环上的线段与内环上的线段部分共线产生的自相交模式；该模式的初始移动方向获取方式与F相同；

H、外环上的线段与内环上的线段完全共线产生的自相交模式；该模式的初始移动方向获取方式与F相同；

I、某一类自相交模式重复出现的复杂自相交模式；该模式的初始移动方向为各个自相交模式修正方向向量之和；

J、多类自相交模式同时出现的复杂自相交模式；该模式的初始移动方向可转化为各个独立自相交模式的处理。

4.根据权利要求1所述的多环多边形自相交模式识别及处理方法，其特征在于：所述移位距离为距离阈值的两倍。

说明书

技术领域

本发明涉及地图制图学技术领域，尤其涉及一种多环多边形自相交模式识 别及处理方法。

背景技术

多边形自相交是相交计算的一种特殊形式，也是影响数据质量的一个关键 因素。通常，多边形自相交出现于使多边形形状发生明显改变的数据操作中， 如空间叠加运算、地图综合变换等，虽然在一次计算中，多边形自相交数量极 少，但其会造成明显的拓扑错误，并直接使后续的地图操作宕机，因此，高效、 准确的探测多边形自相交并将其处理为简单多边形十分重要。

在计算几何中，多边形是指平面上一组节点(大于2个)按一定方向(顺时 针或逆时针)顺次连接所围成的封闭连通区域，根据围成该封闭区域的闭合曲 线数量，可将多边形分为两类，一类为单环多边形，即仅包含一条封闭曲线， 另一类为多环多边形，即包含两条或多条封闭曲线，也称为含孔(洞)多边形。 单环多边形的自相交问题已经有相关专利进行讨论，本发明仅关注多环多边形 自相交模式的识别和处理问题。

在多环多边形中，沿边界线逆时针走一周回到出发点，若连通区域位于边 界的左侧，则该边界线为外环；若连通区域位于边界的右侧，则该边界线为内 环。对于多环多边形的处理，现有研究更多的关注点在于样条曲线的自相交处 理，比如国外学者针对动态轮廓模型在表达图象中物体轮廓时存在的多边形自 相交情况进行了讨论。然而，这种方法依赖于描述样条曲线的数学函数，计算 复杂度较高。在地图制图学领域，构成封闭曲线的数据结构通常为polyline， 其由各个节点顺次相连，却并不具有连续、曲率变化均匀等特点，因此，上述 方法无法应用于GIS领域多边形自相交的处理。此外，国外研究人员从拓扑预处理的角度出发，通过设置多项拓扑保持规则，探测和去除多边形自相交情况， 如线段不能自相交、线段与线段不能相互重叠等。这种方法从一定程度上解决 了多边形自相交问题，然而，本质上其对多边形自相交的处理是对组成该多边 形边界线的处理，当然对应的修复过程也依据线段拓扑规则进行处理，如线打 断、删除重复线中的一条等。事实上，多环多边形自相交与边界线段自相交是 两种截然不同的情况，依据线段自相交进行多边形自相交处理，无法顾及内环 与外环的空间关系以及视觉可分辨特征，导致可识别的自相交类型十分有限， 且处理结果仍存在明显的拓扑错误及空间占位冲突。

发明内容

本发明的目的在于提供一种多环多边形自相交模式识别及处理方法，从而 解决现有技术中存在的前述问题。

为了实现上述目的，本发明采用的技术方案如下：

一种多环多边形自相交模式识别及处理方法，包括如下步骤，

S1、获取多环多边形中组成该多环多边形的节点与线段，以逆时针方向进行 标识，获取该多环多边形的外环和内环；

S2、计算每个线段的最小外包矩形，并建立R树索引，识别与某一线段的最 小外包矩形彼此相交的所有最小外包矩形，组成多个最小外包矩形对，放入该 线段的待处理候选集中；

S3、在该线段的待处理候选集中任选一个最小外包矩形对，判断其内线段的 相互位置，若其内线段位于同一边界线，则转化为单环多边形自相交进行处理； 若其内线段分别位于内环和外环，则进入S4；若其内线段位于不同的内环，则 转化为多边形共享边界一致性改正问题进行处理；

S4、针对该最小外包矩形对，任选其中一条线段作为参考线段，由所述R树 索引探测与该参考线段相邻或相交的匹配线段，得到由该参考线段和与其对应 的匹配线段构成的自相交线段对，并获取该自相交线段对中两条线段各自的首 末节点；计算该自相交线段对中两线段首末节点之间的距离、匹配线段的首末 节点到参考线段之间的距离，并将以上距离与预设的距离阈值进行比较判断， 进而确定该多环多边形的自相交模式；

S5、判断R树索引中所有的线段是否全部完成计算，若否，则返回步骤S2， 选择下一条线段进行计算；若是，则识别算法结束，进入步骤S6进行处理；

S6、判断该多环多边形内环的各个线段与外环的距离是否都小于距离阈值， 若否，则采用移位算法进行处理；若是，则采用内缩算法进行处理；

所述移位算法具体为，根据距离阈值设置合理的移位距离，并根据探测到的 该多环多边形各种自相交模式出现的位置，依据各种自相交模式，分别确定其 初始移位方向；然后通过Delaunay三角网进行潜在冲突区域探测，即针对多环 多边形的内环和外环边界线，建立约束Delaunay三角网，并以内环线段为基本 单元，以桥接三角形高的最小值作为其与外环的距离，其中桥接三角形是指存 在一边为内环边界的三角形；最后，依据潜在冲突，调整移位方向，即若某一 内环线段与外环之间的距离小于距离阈值，则说明不宜向该方向移位，则需在 初始移位方向中减去该方向，并以校正后的方向作为最终移位方向，沿最终移 位方向移动移位距离；

所述内缩算法具体为，沿节点角平分线方向，将该节点向该多环多边形内部 移动移位距离，并与最近边界相隔的距离为原有判断时确定的距离阈值。

优选的，步骤S4具体包括如下内容，

S41、若存在某一匹配线段首末节点到参考线段首末节点之间的距离为0，且 匹配线段首末节点到参考线段之间的距离大于距离阈值，则判定该多环多边形 存在外环上的节点与内环上的节点相交产生的自相交模式；

S42、若存在匹配线段首节点到参考线段之间的距离为0，匹配线段末节点到 参考线段之间的距离大于距离阈值，且匹配线段首节点到参考线段首末节点之 间的距离大于距离阈值；或者存在匹配线段末节点到参考线段之间的距离为0， 匹配线段首节点到参考线段之间的距离大于距离阈值，且匹配线段末节点到参 考线段首末节点之间的距离大于距离阈值，则判定该多环多边形存在外环上的 节点或线段与内环上的线段或节点相交产生的自相交模式；

S43、若匹配线段与参考线段相交，则判定该多环多边形存在外环上的线段 与内环上的线段相交产生的自相交模式；

S44、若存在某一匹配线段首末节点到参考线段首末节点之间的距离大于0 但小于等于距离阈值，且匹配线段首末节点到参考线段之间的距离大于距离阈 值，则判定该多环多边形存在外环上的节点与内环上的节点相离产生的自相交 模式；

S45、若存在匹配线段首节点到参考线段之间的距离大于0但小于等于距离阈 值，匹配线段末节点到参考线段之间的距离大于距离阈值，且匹配线段首节点 到参考线段首末节点之间的距离大于距离阈值；或者，存在匹配线段末节点到 参考线段之间的距离大于0但小于等于距离阈值，匹配线段首节点到参考线段之 间的距离大于距离阈值，且匹配线段末节点到参考线段首末节点之间的距离大 于距离阈值，则判定该多环多边形存在外环上的节点或线段与内环上的线段或 节点相离产生的自相交模式；

S46、若存在匹配线段首末节点到参考线段之间的距离均大于0但小于等于距 离阈值，则判定该多环多边形存在外环上的线段与内环上的线段相离产生的自 相交模式；

S47、若存在匹配线段首末节点到参考线段之间的距离均为0，且匹配线段首 末节点到参考线段首末节点之间的距离大于0，则判定该多环多边形存在外环上 的线段与内环上的线段部分共线产生的自相交模式；

S48、若存在匹配线段首节点到参考线段首节点之间的距离为0，且匹配线段 末节点到参考线段末节点之间的距离为0；或者存在匹配线段首节点到参考线段 末节点之间的距离为0，且匹配线段末节点到参考线段首节点之间的距离为0， 则判定该多环多边形存在外环上的线段与内环上的线段完全共线产生的自相交 模式；

S49、判断该线段的待处理候选集中所有的最小外包矩形对是否全部处理完 成；若否，则返回步骤S3；若是，则判断某一类自相交模式是否重复出现；若 重复出现，则判定该多环多边形存在某一类自相交模式重复出现的复杂自相交 模式；若不重复出现，则判断该多环多边形是否同时出现多类自相交模式，若 是，则判定该多环多边形存在多类自相交模式同时出现的复杂自相交模式，若 否，则结束判断，进入步骤S5。

优选的，各个自相交模式的初始移动方向分别为

A、针对外环上的节点与内环上的节点相交产生的自相交模式；探测该模式 相交点，并获取该相交点与其在内环上关联的两条线段所构成的夹角，则其初 始移动方向为，沿该夹角角平分线方向且指向该多环多边形内部；

B、针对外环上的节点或线段与内环上的线段或节点相交产生的自相交模式； 该模式的初始移动方向获取方式与A相同；

C、针对外环上的线段与内环上的线段相交产生的自相交模式；探测该模式 中的两条内环线段，并获取该两条线段所构成的夹角，则其初始移动方向为， 沿该夹角角平分线方向且指向多环多边形内部；

D、外环上的节点与内环上的节点相离产生的自相交模式；探测该模式中位 于内环上的节点，并获取该节点与其在内环上关联的两条线段所构成的夹角， 则其初始移动方向为沿该夹角角平分线方向且指向多环多边形内部；

E、外环上的节点或线段与内环上的线段或节点相离产生的自相交模式；该 模式的初始移动方向获取方式与D相同；

F、外环上的线段与内环上的线段相离产生的自相交模式；探测该模式中位 于外环上的线段，则其初始移动方向为，垂直于该线段并指向该多环多边形内 部；

G、外环上的线段与内环上的线段部分共线产生的自相交模式；该模式的初 始移动方向获取方式与F相同；

H、外环上的线段与内环上的线段完全共线产生的自相交模式；该模式的初 始移动方向获取方式与F相同；

I、某一类自相交模式重复出现的复杂自相交模式；该模式的初始移动方向 为各个自相交模式修正方向向量之和；

J、多类自相交模式同时出现的复杂自相交模式；该模式的初始移动方向可 转化为各个独立自相交模式的处理。

优选的，所述移位距离为距离阈值的两倍。

本发明的有益效果是：1、对于相交型多环多边形，本发明建立的移位算法 则取得了有合理的结果，内环多边形在自相交节点处向多边形内部进行移位， 既保留了原始内环多边形的形状，又符合内环和外环拓扑相离的要求。2、对于 相离型多环多边形，本发明通过移位算法同样取得了良好的效果，原始图形内 视觉邻近的节点和线段，在简化后内环和外环之间距离被扩大，有效避免了内 环与外环之间的空间占位冲突。3、对于共线型多环多边形，本发明方法则通过 移位或内缩算法，在保证多环多边形形状特征的情形下，保证了内环和外环的 拓扑一致性。4、对于组合型多环多边形，本发明方法通过方向向量求和，获得 了整体移位或内缩方向，简化结果既符合拓扑、形状及视觉一致性约束，又不 会产生新的空间冲突。

附图说明

图1为本发明中多环多边形自相交模式识别流程图；

图2为本发明中多环多边形自相交模式示意图；

图3为本发明中多环多边形自相交模式移位算法处理示意图；

图4为本发明中多环多边形自相交模式内缩算法处理示意图；

图5为本发明中多环多边形自相交模式处理结果示意图；

图6为部分多环多边形所对应的全局效率指数图；

图7为对比实验中典型自相交多边形处理结果对比图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图，对本 发明进行进一步详细说明。应当理解，此处所描述的具体实施方式仅仅用以解 释本发明，并不用于限定本发明。

实施例一

如图1至图5所示，本实施例中，提供了一种多环多边形自相交模式识别及处 理方法，包括如下步骤，

S1、获取多环多边形中组成该多环多边形的节点与线段，以逆时针方向进行 标识，获取该多环多边形的外环和内环；

S2、计算每个线段的最小外包矩形，并建立R树索引，识别与某一线段的最 小外包矩形彼此相交的所有最小外包矩形，组成多个最小外包矩形对，放入该 线段的待处理候选集中；

S3、在该线段的待处理候选集中任选一个最小外包矩形对，判断其内线段的 相互位置，若其内线段位于同一边界线，则转化为单环多边形自相交进行处理； 若其内线段分别位于内环和外环，则进入S4；若其内线段位于不同的内环，则 转化为多边形共享边界一致性改正问题进行处理；

S4、针对该最小外包矩形对，任选其中一条线段作为参考线段，由所述R树 索引探测与该参考线段相邻或相交的匹配线段，得到由该参考线段和与其对应 的匹配线段构成的自相交线段对，并获取该自相交线段对中两条线段各自的首 末节点；计算该自相交线段对中两线段首末节点之间的距离、匹配线段的首末 节点到参考线段之间的距离，并将以上距离与预设的距离阈值进行比较判断， 进而确定该多环多边形的自相交模式；

S5、判断R树索引中所有的线段是否全部完成计算，若否，则返回步骤S2， 选择下一条线段进行计算；若是，则识别算法结束，进入步骤S6进行处理；

S6、判断该多环多边形内环的各个线段与外环的距离是否都小于距离阈值， 若否，则采用移位算法进行处理；若是，则采用内缩算法进行处理；

所述移位算法具体为，根据距离阈值设置合理的移位距离，并根据探测到的 该多环多边形各种自相交模式出现的位置，依据各种自相交模式，分别确定其 初始移位方向；然后通过Delaunay三角网进行潜在冲突区域探测，即针对多环 多边形的内环和外环边界线，建立约束Delaunay三角网，并以内环线段为基本 单元，以桥接三角形高的最小值作为其与外环的距离，其中桥接三角形是指存 在一边为内环边界的三角形；最后，依据潜在冲突，调整移位方向，即若某一 内环线段与外环之间的距离小于距离阈值，则说明不宜向该方向移位，则需在 初始移位方向中减去该方向，并以校正后的方向作为最终移位方向；

所述内缩算法具体为，沿节点角平分线方向，将该节点向该多环多边形内部 移动，并与最近边界相隔的距离为原有判断时确定的距离阈值。

本实施例中，多环多边形的自相交模式识别实质在于内环与外环之间拓扑关 系的确定，而内环与外环之间拓扑关系确定的关键在于节点与节点、节点与线 段、线段与线段之间距离及拓扑关系的计算。为此，本发明通过计算多环多边 形各个线段要素的外包框，并为其建立R树索引，通过快速识别彼此相交的最小 外包矩形，初步获取可能相邻或相交的成对线段。

对照附图1，对于两个彼此相交的最小外包矩形框，若其内的线段分别属于 内环或外环，则任选其中的一条线段作为参考线段，假设另一条线段首末端节 点与参考线段首末端节点之间的距离分别为D00、D01、D00、D01，到参考线段的 距离分别为S0、S1、，设置距离阈值St，并以步骤S4中的规则进行自相交模式识 别；步骤S4具体包括如下内容，

S41、若存在某一匹配线段首末节点到参考线段首末节点之间的距离为0，且 匹配线段首末节点到参考线段之间的距离大于距离阈值，则判定该多环多边形 存在外环上的节点与内环上的节点相交产生的自相交模式(PatternI-(a))；即若 存在某一Dij＝0；(i＝0,1；j＝0,1)，且其余节点之间距离均大于St，则这两条线段构成 自相交模式PatternI-(a)；

S42、若存在匹配线段首节点到参考线段之间的距离为0，匹配线段末节点到 参考线段之间的距离大于距离阈值，且匹配线段首节点到参考线段首末节点之 间的距离大于距离阈值；或者存在匹配线段末节点到参考线段之间的距离为0， 匹配线段首节点到参考线段之间的距离大于距离阈值，且匹配线段末节点到参 考线段首末节点之间的距离大于距离阈值，则判定该多环多边形存在外环上的 节点或线段与内环上的线段或节点相交产生的自相交模式(PatternI-(b))；即若 存在S0＝0，S1＞St，且D0j＞St；(j＝0,1)；或者，S0＞St，S1＝0，且D1j＞St；(j＝0,1)， 则这两条线段构成自相交模式PatternI-(b)；

S43、若匹配线段与参考线段相交，则判定该多环多边形存在外环上的线段 与内环上的线段相交产生的自相交模式(PatternI-(c))；即若两条线段相交，则 这两条线段构成自相交模式PatternI-(c)；

S44、若存在某一匹配线段首末节点到参考线段首末节点之间的距离大于0 但小于等于距离阈值，且匹配线段首末节点到参考线段之间的距离大于距离阈 值，则判定该多环多边形存在外环上的节点与内环上的节点相离产生的自相交 模式(PatternII-(a))；即若存在某一对节点之间的距离0＜Dij＜St；(i＝0,1；j＝0,1)， 且剩余两节点之间距离大于St，则这两条线段构成自相交模式PatternII-(a)；

S45、若存在匹配线段首节点到参考线段之间的距离大于0但小于等于距离阈 值，匹配线段末节点到参考线段之间的距离大于距离阈值，且匹配线段首节点 到参考线段首末节点之间的距离大于距离阈值；或者，存在匹配线段末节点到 参考线段之间的距离大于0但小于等于距离阈值，匹配线段首节点到参考线段之 间的距离大于距离阈值，且匹配线段末节点到参考线段首末节点之间的距离大 于距离阈值，则判定该多环多边形存在外环上的节点或线段与内环上的线段或 节点相离产生的自相交模式(PatternII-(b))；即若存在0＜S0≤St，S1＞St，且 D0j＞St；(j＝0,1)；或者，0＜S1≤St，S0＞St，且D1j＞St；(j＝0,1)，则这两条线段构成 自相交模式PatternII-(b)；

S46、若存在匹配线段首末节点到参考线段之间的距离均大于0但小于等于距 离阈值，则判定该多环多边形存在外环上的线段与内环上的线段相离产生的自 相交模式(PatternII-(c))；即若0＜S0≤St且0＜S1≤St，则这两条线段构成自相交 模式PatternII-(c)；

S47、若存在匹配线段首末节点到参考线段之间的距离均为0，且匹配线段首 末节点到参考线段首末节点之间的距离大于0，则判定该多环多边形存在外环上 的线段与内环上的线段部分共线产生的自相交模式(Pattern III-(a))；即若存在 S0＝0，S1＝0，且Dij＞0；(i＝0，1；j＝0，1)，则这两条线段构成自相交模式 Pattern III-(a)；

S48、若存在匹配线段首节点到参考线段首节点之间的距离为0，且匹配线段 末节点到参考线段末节点之间的距离为0；或者存在匹配线段首节点到参考线段 末节点之间的距离为0，且匹配线段末节点到参考线段首节点之间的距离为0， 则判定该多环多边形存在外环上的线段与内环上的线段完全共线产生的自相交 模式(PatternIII-(b))；即若D00＝0且D11＝0，或D01＝0且D10＝0，则这两条线段构 成自相交模式PatternIII-(b)；

S49、判断该线段的待处理候选集中所有的最小外包矩形对是否全部处理完 成；若否，则返回步骤S3；若是，则判断某一类自相交模式是否重复出现；若 重复出现，则判定该多环多边形存在某一类自相交模式重复出现的复杂自相交 模式(PatternIV-(a))；若不重复出现，则判断该多环多边形是否同时出现多类 自相交模式，若是，则判定该多环多边形存在多类自相交模式同时出现的复杂 自相交模式(PatternIV-(b))，若否，则结束判断，进入步骤S5。

本实施例中，根据单环多边形基本构成要素(节点与线段)之间的距离及拓 扑关系，本发明将多环多边形自相交分为4种模式：(1)相交型：多环多边形外 环与内环的基本构成要素之间存在相交情况；(2)相离型：多环多边形外环与 内环的基本构成要素彼此相离，但距离小于最小可视距离阈值；(3)共线型： 多环多边形外环与内环之间存在一条或多条线段重合的情况；(4)组合型：在 一个多环多边形中存在多个上述自相交关系。进一步依据参与自相交的要素类 型，将其分为10类；下面结合图2具体说明这10类自相交模式：

PatternI-(a)：外环上的节点与内环上的节点相交产生的自相交模式，该类型 常见的情况是两环的两个节点共点，如图2(a)所示，多边形P中内环L1的节点 S2与外环L2节点S5共点；

PatternI-(b)：外环上的节点(或线段)与内环上的线段(或节点)相交产生 的自相交模式，该类型常见的情况是某一环的节点在另一环的线段上，如图2(b) 所示，多边形P中内环L1的节点S3在外环L2的边S0S1上；

PatternI-(c)：外环上的线段与内环上的线段相交产生的自相交模式，该类型 常见的情况是两环的两个线段相交，但交点不是节点，如图2(c)所示，多边 形P中内环L1的边S1S2与外环L2的边S0S3相交于点a，内环L1的边S4S6与外环L2的 边S0S1相交于点b，交点a、b并不是多边形的节点；

PatternII-(a):外环上的节点与内环上的节点相离且间距小于最小可视距离 产生的自相交模式，如图2(d)所示，多边形P中内环L1的节点S4与外环L2的节 点S1距离小于最小可视距离；

PatternII-(b)：外环上的节点(或线段)与内环上的线段(或节点)相离且 间距小于最小可视距离产生的自相交模式，该类型常见的情况是某一环的节点 与另一环的线段间的距离小于给定距离阈值，且该节点到相邻边上的投影点的 距离远远小于节点到该边的两个端点的距离，如图2(e)所示，多边形P中内环 L1的节点S3与其在外环L2的边S0S1上的投影点a的距离小于最小可视距离，且远 小于节点S3到节点S0和节点S1的距离；

PatternII-(c)：外环上的线段与内环上的线段相离且间距小于最小可视距离 产生的自相交模式，如图2(f)所示，多边形P中内环L1的边S1S2与外环L2的边S4S5相离且间距小于最小可视距离；

PatternIII-(a)：外环上的线段与内环上的线段部分共线产生的自相交模式， 如图2(g)所示，多边形P中内环L1的线段S1S2与外环L2的线段S4S5部分重叠；

PatternIII-(b)：外环上的线段与内环上的线段完全共线产生的自相交模式， 如图2(h)所示，多边形P中内环L1的线段S1S2与外环L2的线段S4S5完全重叠；

PatternIV-(a)：上述某一类自相交模式重复出现在一个多环多边形内形成的 复杂自相交情况，如图2(i)所示，PatternI-(a)两次出现在一个多环多边形内；

PatternIV-(b)：上述多类自相交模式同时出现在一个多环多边形内形成的复 杂自相交情况，如图2(j)所示，PatternI-(a)、PatternII-(a)与PatternIII-(a)同 时出现在一个多环多边形内。

本实施例中，结合附图3和图4，具体说明步骤S6中，采用移位算法进行处理 和采用内缩算法进行处理的处理过程；

采用移位算法进行处理具体为：根据距离阈值设置合理的移位距离，通常可 以将移位距离设置为2倍的距离阈值，并根据探测各中自相交模式出现的位置， 依据自相交类型，分别确定初始移位方向；然后通过Delaunay三角网进行潜在 冲突区域探测，即针对多环多边形的内环和外线边界线，建立约束Delaunay三 角网，并以内环线段为基本单元，以桥接三角形高的最小值作为其与外环的距 离，其中桥接三角形是指存在一边为内环边界的三角形；最后，依据潜在冲突， 调整移位方向，即若某一内环线段与外环之前的距离小于移位距离阈值，则说 明不宜向该方向移位，则需在初始移位方向中减去该方向，并以校正方向为最 终移位方向。

如图3(a)所示，对于某一PatternI-(b)型自相交多边形，f1为初始移位方向， 可以发现，在移位过程中，内环L2上的线段S1S2会与外环L1发生相交，产生新的 冲突，为此，构建Delaunay三角网探测内环各线段与外环的间距，图3(b)阴 影区域即为线段S1S2与外环的桥接三角形区域，三角形高的最小值小于距离阈值， 则在移位过程中需去除垂直方向f2，如图3(c)所示，得到最终移位方向f，沿 此方向移动Dt(移位距离)即为最终结果。

采用内缩算法具体为：在某些极端条件下，如内环多边形的各个线段与外环 的距离均小于距离阈值，或各方向向量相互抵消时，采用内缩算法进行处理。 内缩算法为沿节点角平分线方向，将该点向多环多边形内部移动，并与最近边 界相隔最小可视距离。如图4(a)所示，对于无法移位的情况，采用内缩算法， 将点S0沿角平分线f1方向缩进Dt(移位距离)得到最终结果，如图4(b)所示。

不同类型的自相交模式均可采取上述移位、内缩算法进行处理，其区别在于 初始方向的确定，为此，本发明作如下规定：

具体的，结合附图5具体说明各个自相交模式的初始移动方向

A、针对外环上的节点与内环上的节点相交产生的自相交模式(PatternI-(a))；探测该模式相交点，并获取该相交点与其在内环上关联的两条线段所构成的夹 角，则其初始移动方向为，沿该夹角角平分线方向且指向该多环多边形内部； 图5(a)为该模式沿该方向进行移位处理的结果示意图；

B、针对外环上的节点或线段与内环上的线段或节点相交产生的自相交模式(PatternI-(b))；该模式的初始移动方向获取方式与A相同；图5(b)为该模式 沿该方向进行移位处理的结果示意图；

C、针对外环上的线段与内环上的线段相交产生的自相交模式(PatternI-(c))；探测该模式中的两条内环线段，并获取该两条线段所构成的夹角，则其初始移 动方向为，沿该夹角角平分线方向且指向多环多边形内部；图5(c)为该模式 沿该方向进行移位处理的结果示意图；

D、外环上的节点与内环上的节点相离产生的自相交模式(PatternII-(a))； 探测该模式中位于内环上的节点，并获取该节点与其在内环上关联的两条线段 所构成的夹角，则其初始移动方向为沿该夹角角平分线方向且指向多环多边形 内部；图5(d)为该模式沿该方向进行移位处理的结果示意图；

E、外环上的节点或线段与内环上的线段或节点相离产生的自相交模式(PatternII-(b))；该模式的初始移动方向获取方式与D相同；图5(e)为该模式 沿该方向进行移位处理的结果示意图；

F、外环上的线段与内环上的线段相离产生的自相交模式(PatternII-(c))； 探测该模式中位于外环上的线段，则其初始移动方向为，垂直于该线段并指向 该多环多边形内部；图5(f)为该模式沿该方向进行移位处理的结果示意图；

G、外环上的线段与内环上的线段部分共线产生的自相交模式 (PatternIII-(a))；该模式的初始移动方向获取方式与F相同；图5(g)为该模式 沿该方向进行移位处理的结果示意图；

H、外环上的线段与内环上的线段完全共线产生的自相交模式(PatternIII-(b))；该模式的初始移动方向获取方式与F相同；图5(h)为该模式沿该方向进行内缩 处理的结果示意图；

I、某一类自相交模式重复出现的复杂自相交模式(PatternIV-(a))；该模式 的初始移动方向为各个自相交模式修正方向向量之和；图5(i)所示，最终移 位方向f为两个自相交模式修正方向向量f1、f2之和；

J、多类自相交模式同时出现的复杂自相交模式(PatternIV-(b))；该模式的 初始移动方向可转化为各个独立自相交模式的处理；图5(j)为该模式沿该方 向进行移位及内缩处理的结果示意图。

实施例二

如图6和图7，本实施例中，依托中国测绘科学研究院研制的WJ-III地图工作 站，嵌入本发明提出的多环多边形自相交模式识别及简化方法，采用实际数据 对本发明方法的合理性和可行性进行验证。

实验数据选取贵州省5个县域第二次全国土地调查数据，单个数据集平均包 含面状要素50,000个，初始比例尺为1:10,000。经地图综合操作处理后，选取 其中的过程数据进行实验分析。实验中线段相交容差为0.0001m，节点距离容差 为0.01m，最小可视距离设置为图上0.4mm。实验环境为单台PC机，系统版本为 Windows7，系统类型为32位操作系统，CPU为Intel Core2 Quad Q8400，主频为 3.40GHz，内存(RAM)为3.35GB，硬盘总大小为60GB(固态)。对5幅地图进行 多环多边形自相交处理的时间分别为64.1s，65.3s，65.7s，64.3s和64.6s。

采用本发明方法、现有的Martinez-Llario方法、人工协同检查结果进行对 比分析，对本发明方法的识别率进行验证。统计结果如表1所示；表1中，记本 发明方法为X、现有的Martinez-Llario方法为Y、人工协同检查为Z；各自相交 模式，PatternI-(a)记为A、PatternI-(b)记为B、PatternI-(c)记为C、PatternII-(a)记 为D、PatternII-(b)记为E、PatternII-(c)记为F、PatternIII-(a)记为G、PatternIII-(b) 记为H、PatternIV-(a)记为I、PatternIV-(b)记为J。其中，人机协同检查是指首 先基于多环多边形定义，建立多边形标准化算法，由计算机找出存在问题的多 环多边形，进而由制图专业人员逐一检查这些多边形并对其自相交模式进行分 类。可以看出，地图综合操作较容易导致多环多边形自相交问题，在各个图幅 内均产生了不同数量的自相交情况，虽然数量较少，但均对地图质量有直接影 响。在识别准确率方面，总体来说，对于4大类10小类自相交问题，本发明方法 均可识别，且数量与人工识别同为89个，识别率达到了100％。与此不同， Martinez-Llario方法可以识别PatternI-(b)、PatternI-(c)、PatternIII-(a)和 PatternIII-(b)这四种情况，对于相离型及复合型无法识别，识别数量为44个，其 整体识别率仅为49.44％，这充分说明现有方法对多环多边形自相交模式的识别 类型十分有限，无法有效满足实际需求。

表1实验区多环多边形自相交模式识别结果统计

为了验证本发明方法对多边形自相交识别与简化的合理性，实验引入图论计 算多边形全局效率指数进一步量化分析。全局效率指数描述网络中的节点如何 交互，反映网络中信息传播的顺畅程度。对多环多边形构建无向拓扑结构图 G＝(V,E)，其中，V代表多边形边界上的所有节点，E代表邻近两节点相连形成 的边，以节点之间的传输路径倒数之和与节点数量的比值作为多边形的全局效 率指数(E(G))，数学公式为：

其中，N为节点总数，为节点i到节点j的路径个数。由全局效率指数的计 算公式可知，对于一个简单多边形，其指数值为1；若存在自相交问题，则因产 生冗余传播而使其值小于1。

统计5个数据集内所有多环多边形简化前后的全局效率指数，并按数值大小 进行升序排列，顺序选取指数值位于前100的多环多边形，绘制折线图如图6所 示。可以发现，对于简化前的各个多环多边形，共有60个多边形全局效率指数 小于1，说明这些多环多边形存在自相交情况，其中的最小值为0.22，说明存在 多个自相交节点，极大的降低了网络的连通效率。由于拓扑无向图中对相交的 判断未考虑视觉可分辨因素，29个相离型自相交多边形的全局效率指数在简化 前被计算为1。经Martinez-Llario方法简化后，共有24个多边形的全局效率指 数得到了提高，对应于24个共线型多环多边形，而对于相交型多环多边形，由 于采用节点打断的处理方式，其全局效率并未发生变化，然而，上述多环多边 形的全局效率均小于1，说明仍然存在自相交情况。与此不同的是，经本发明方 法简化后，所有多环多边形的全局效率指数均为1，说明所有多环多边形均被简 化为简单多边形，不再存在自相交情况。

对于相交型，选取内环面积最大的多边形；对于相离型，选取距离最大的多 边形；对于共线型，选取共线长度最大的多边形；对于组合型，选取单一模式 出现次数最多及同一多环多边形中不同类型自相交模式最多的多边形，将这些 多边形作为代表性较强的情形简化结果进行可视化分析，以验证本发明方法的 有效性及合理性，如图7所示，可以发现：

对于相交型，Martinez-Llario采取的处理方法是在相交点处进行打断，可 以发现，这种方式并不适用于多环多边形自相交的处理，处理后的内环和外环 仍为拓扑相接关系，而实际上，二者应为拓扑相离关系；本发明建立的移位算 法则取得了有合理的结果，内环多边形在自相交节点处向多边形内部进行移位， 既保留了原始内环多边形的形状，又符合内环和外环拓扑相离的要求。

对于相离型，Martinez-Llario方法由于未能识别该种类型而未做处理；本 发明通过移位算法同样取得了良好的效果，原始图形内视觉邻近的节点和线段， 在简化后内环和外环之间距离被扩大，有效避免了内环与外环之间的空间占位 冲突。

对于共线型，Martinez-Llario方法可识别出共线区域，然而由于其采取“融 合重叠部分”方式进行修复，导致多环多边形被强行更正为单环多边形，多边 形形状特征发生了明显改变；与此不同的是，本发明方法则通过移位或内缩算 法，在保证多环多边形形状特征的情形下，保证了内环和外环的拓扑一致性。

对于组合型，Martinez-Llario方法不能进行整体处理，而是将其离散为独 立的自相交模式，依次进行处理，处理结果同样存在明显错误；本发明方法通 过方向向量求和，获得了整体移位或内缩方向，简化结果既符合拓扑、形状及 视觉一致性约束，又不会产生新的空间冲突。

通过采用本发明公开的上述技术方案，得到了如下有益的效果：

本发明提供了一种多环多边形自相交模式识别及处理方法，对于相交型多环 多边形，本发明建立的移位算法则取得了有合理的结果，内环多边形在自相交 节点处向多边形内部进行移位，既保留了原始内环多边形的形状，又符合内环 和外环拓扑相离的要求。对于相离型多环多边形，本发明通过移位算法同样取 得了良好的效果，原始图形内视觉邻近的节点和线段，在简化后内环和外环之 间距离被扩大，有效避免了内环与外环之间的空间占位冲突。对于共线型多环 多边形，本发明方法则通过移位或内缩算法，在保证多环多边形形状特征的情 形下，保证了内环和外环的拓扑一致性。对于组合型多环多边形，本发明方法 通过方向向量求和，获得了整体移位或内缩方向，简化结果既符合拓扑、形状 及视觉一致性约束，又不会产生新的空间冲突。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技 术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这 些改进和润饰也应视本发明的保护范围。

一种多环多边形自相交模式识别及处理方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。