基于CPU+GPU架构的多边形数据空间关系查询并行系统

摘要

基于CPU+GPU架构的多边形数据空间关系查询并行系统，该系统由4个模块组成：线段间相交分析模块、环间拓扑关系分析模块、多边形间DE-9IM计算模块以及图层间空间关系查询模块。本发明使用户可以在CPU+GPU架构上，并行加速完成对海量多边形数据的空间关系查询操作，准确输出所有满足空间关系查询条件的多边形数据，有效提高了空间关系查询的处理速度并且保证其准确性。

说明书

技术领域

本发明涉及基于CPU+GPU架构的多边形数据空间关系查询并行系统，属于信息技术领域，主要是综合了异构多核并行技术，计算机图形学技术和空间关系查询技术，解决了在CPU+GPU架构上，对海量多边形数据进行空间关系查询的并行加速问题。

背景技术

随着空间信息获取技术更加成熟，空间数据的数据量急速增加。如何将这些海量、超海量空间数据应用于地学计算，能够快速的得到处理从而获得更有价值的信息，已经成为现今地理信息系统技术创新的热点。随着并行计算机越来越普及，并行技术的逐步成熟，并行计算已经成为解决快速处理大数据问题的主流手段。在数据量巨大的地学领域，依靠并行计算机的强大处理能力已经毫无疑问地成为满足加速需求的最优选择，由此应运而生的地学算法并行化改造，也必然成为大数据时代的重点和难点。

从基于CPU多核的并行到CPU+GPU的异构并行，硬件产品的更新换代对传统地学计算算法的并行化产生了重大的影响。CPU的逻辑处理能力强，而GPU数学计算性能强大，大规模并行处理机制强大。将两者结合成为一个异构平台，发挥各自的特长，是并行计算的发展趋势。在具有如此强大计算能力的架构平台上，对原有的地学计算进行并行化改造，以实现超海量空间数据加速处理，是一项极其有意义的工作。

空间关系查询指的是从空间数据集中查找满足某种空间关系的空间目标的过程。开放地理信息系统协会（Open GIS Consortium，OGC）制定的开源GIS实施标准协议中规定，两个空间几何体之间的空间关系，需要通过基于维度扩展九交模型（Dimensionally Extended9-Intersection Model，DE-9IM）进行判断。

在诸多开源的GIS代码库中，几乎全部使用plane sweep算法及其衍生算法获取两个几何体间的DE-9IM信息。但由于plane sweep算法其本身的逐一扫描特性，致使其无法适应并行化加速改造，也因此无法移植到异构多核架构上。为解决上述问题，需要从可以实现数据并行的方面入手，构建一套全新的并行技术。本发明对于海量多边形数据间空间关系查询算法的并行化改造，正是基于CPU+GPU架构，利用其强大的并行计算能力，大批量处理线段相交运算，从而更快得到所有满足查询条件的多边形数据。

发明内容

本发明的技术解决问题是：克服现有空间关系查询技术不具备并行化改造条件，无法适应CPU+GPU架构的不足，设计了一种基于CPU+GPU架构的多边形数据空间关系查询并行系统，解决了空间关系查询技术的并行化改造问题，可以利用CPU+GPU架构强大的并行计算能力，加速海量多边形数据间空间关系查询处理。

本发明的技术解决方案：一种基于CPU+GPU架构的多边形数据空间关系查询并行系统，包括：线段间相交分析模块、环间拓扑关系分析模块、多边形间DE-9IM计算模块和图层间空间关系查询模块，其中：

线段间相交分析模块：对于输入的两个海量多边形图层数据，分别遍历提取两个海量多边形图层数据中所有多边形的线段信息，将不属于同一图层的独立线段两两组合，利用CPU+GPU架构的并行计算技术，对所有线段组合进行并行分析，得到所有相交线段集合及其相交种类，分析过程中排除不相交的线段组合，只记录所有相交的线段组合，同时记录它们的相交种类；线段相交种类分为为四大类：若交点不是两条线段的四个端点中的任何一点，则为普通相交；若交点是两条线段的四个端点中的一点，则为丁字相交；若交点是两条线段的四个端点中的两点，则为连接相交；若两条线段有公共重合线段，则为叠置相交；最终输出为所有相交线段集合，供环间拓扑关系分析模块调用；

环间拓扑关系分析模块：将环与环之间的拓扑关系有八种：分离关系（Disjoint）、叠置关系（Overlap）、相等关系（Equal）、接触关系（Meet）、完全包含关系（Contains）、被完全包含关系（Inside）、覆盖关系（Covers）以及被覆盖关系（Covered By）；对于输入的两个环，根据组成它们的线段信息，从线段间相交分析模块输出的相交线段集合中提取它们之间线段的相交情况，据此分析环与环之间的拓扑关系，若无任何相交线段出现时，则环与环的拓扑关系为分离关系（Disjoint）、完全包含关系（Contains）或被完全包含关系（Inside），再根据射线法判断环上点与另一环的位置关系，以确定最终拓扑关系；若有相交线段出现时，若出现普通相交，则环与环之间一定为叠置关系（Overlap）；若没有普通相交和丁字相交，所述丁字相交是指什么，同时，一环上所有线段都与另一环上的线段发生叠置相交，则环与环之间一定为相等关系（Equal）；若上述判断均不成立，则根据射线法判断环上点与另一环的位置关系，以最终确定环与环之间是覆盖关系（Covers）、被覆盖关系（Covered By）、接触关系（Meet）还是叠置关系（Overlap）；该模块对输入的环与环进行拓扑关系的分析，该结果将供多边形间DE-9IM计算模块调用；

多边形间DE-9IM计算模块：一个多边形数据由一个外环和任意多个内环组成，外环与内环均为环；维度扩展九交模型（DE-9IM）描述多边形数据之间的空间关系，对于输入的两个多边形数据，调用环间拓扑关系分析模块，分别获得两个多边形数据内环、外环的环间拓扑关系，若两个多边形数据外环间拓扑关系为分离关系（Disjoint）或接触关系（Meet）或叠置关系（Overlap），则可直接确定的DE-9IM；若两个多边形外环拓扑关系为相等关系（Equal），则根据两个多边形是否有内环以及内环间的拓扑关系，确定DE-9IM；同理，若两个多边形外环拓扑关系为覆盖关系（Covers）或完全包含关系（Contains），以及被覆盖关系（Covered By）或被完全包含关系（Inside）时：首先根据两个多边形是否有内环确定DE-9IM参数值；若都有内环，再根据其中一个多边形所有内环与另一个多边形的外环之间的拓扑关系进行计算；若依然无法确定DE-9IM，则分析两个多边形内环之间的拓扑关系，根据分析结果最终确定DE-9IM；该模块对输入的两个多边形计算它们的DE-9IM，该计算结果将供图层间空间关系查询模块调用；

图层间空间关系查询模块：对用户输入的两个海量多边形图层数据，分别记为目标图层和源图层，目标图层作为空间关系查询的被查询对象，源图层作为空间关系查询的辅助查询对象；利用CPU+GPU架构提供的并行计算技术，加载线段间相交分析模块分析两个图层之间所有线段的相交情况；同时在该框架下循环遍历两个图层中的多边形数据，将目标图层多边形数据与源图层多边形数据两两组对，对所有多边形数据组合调用多边形间DE-9IM计算模块输出它们的DE-9IM，比对DE-9IM参数值是否满足用户设定且满足OGC（开放地理信息系统协会）协议的空间关系查询条件，筛选出满足查询条件的所有属于目标图层，即两个海量多边形图层数据中作为被查询对象的图层数据，的多边形数据作为最终输出结果。

所述环间拓扑关系分析模块中，对于输入的两个环数据，设为环Ha与环Hb，根据组成它们的线段信息，从线段间相交分析模块输出的相交线段集合中提取它们之间线段的相交情况，据此分析环与环之间拓扑关系的具体过程如下：

（1）若无任何相交线段出现，则环Ha、Hb的拓扑关系为一定为分离关系（Disjoint）、完全包含关系（Contains）或被完全包含关系（Inside）三者之一；设点p为环Ha边界上任意一点，点q为环Hb边界上任意一点，利用射线法计算点与环之间的位置关系，据此确定最终拓扑关系，具体分析过程如下：

（1.1）若点p不在环Hb的内部，并且点q不在环Ha的内部，则环Ha与环Hb的是分离关系（Disjoint），分析完毕，结束；

（1.2）若点p在环Hb的内部，并且点q不在环Ha的内部，则环Ha与环Hb的是被完全包含关系（Inside），分析完毕，结束；

（1.3）若点p不在环Hb的内部，并且点q在环Ha的内部，则环Ha与环Hb的是完全包含关系（Contains），分析完毕，结束；

（2）若有相交线段出现时，进行如下过程：

（2.1）如果统计结果中至少有一个普通相交，则环Ha和环Hb的拓扑关系为叠置关系（Overlap），分析完毕，结束；

（2.2）如果（2.1）不成立时，同时线段相交情况中没有出现丁字相交，并且线段相交集合中环Ha的所有线段都和环Hb的某条线段发生叠置相交关系，则环Ha与环Hb的拓扑关系为相等关系（Equal），分析完毕，结束；

（2.3）若上述情况均不成立，提取与环Ha的线段发生连接相交和丁字相交的所有环Hb的线段，利用射线法计算所有线段两个端点与环Ha之间的位置关系，据此确定最终拓扑关系，具体分析过程如下：

（2.3.1）若端点都在Ha的内部和边界上，则环Ha与环Hb的拓扑关系为覆盖关系（Covers），分析完毕，结束；

（2.3.2）若端点都在环Ha的外部和边界上，且环Ha内部的一点p1在环Hb的内部，则环Ha与环Hb的拓扑关系为被覆盖关系（Covered By），分析完毕，结束；

（2.3.3）否则，环Ha、环Hb的拓扑关系为接触关系（Meet），即端点都在环Ha的外部和边界上，但环Ha内部没有点在环Hb的内部，分析完毕，结束；

（2.3.4）若分析过程依然没有结束，则环Ha与环Hb的拓扑关系只能为叠置关系（Overlap），分析完毕，结束。

所述的多边形间DE-9IM计算模块中，维度扩展九交模型（DE-9IM）描述多边形之间的空间关系，它是一个3*3的矩阵，为方便运算，记成一组由9个参数值构成的字符串，每一个参数值分别对应于一个多边形内部、边界和外部与另一个多边形内部、边界和外部的相交情况，若相交则为True，记为“T”，不相交则为False，记为“F”，无所谓是否相交则为DONTCARE，记为“*”，例如，若多边形A、B的DE-9IM为“FF*FFTTTT”，该字符串中每个参数值依次所表示的含义为：第一个参数值表示A的内部与B的内部的相交情况，“F”表示不相交；第二个参数表示A的内部与B的边界的相交情况，“F”表示不相交；第三个参数表示A的内部与B的外部的相交情况，“*”表示无所谓是否相交；第四个参数表示A的边界与B的内部的相交情况，“F”表示不相交；第五个参数表示A的边界与B的边界的相交情况，“F”表示不相交；第六个参数表示A的边界与B的外部的相交情况，“T”表示相交；第七个参数表示A的外部与B的内部的相交情况，“T”表示相交；第八个参数表示A的外部与B的边界的相交情况，“T”表示相交；第九个参数表示A的外部与B的外部的相交情况，“T”表示相交。

对于输入的两个多边形数据，设为多边形A和多边形B，调用环间拓扑关系分析模块，分别获得两个多边形内、外环之间的拓扑关系，据此计算多边形间DE-9IM参数值的具体过程如下：

（1）若多边形A外环与多边形B外环的拓扑关系为分离关系（Disjoint），则可确定多边形A和B的DE-9IM的参数值为：“FFTFFTTTT”，计算完毕，结束；

（2）若多边形A外环与多边形B外环的拓扑关系为叠置关系（Overlap），则可确定多边形A和B的DE-9IM的参数值为：“TTTTTTTTT”，计算完毕，结束；

（3）若多边形A外环与多边形B外环的拓扑关系为接触关系（Meet），则可确定多边形A和B的DE-9IM的参数值为：“FFTFTTTTT”，计算完毕，结束；

（4）若多边形A外环与多边形B外环的拓扑关系为相等关系（Equal），具体计算过程如下：

（4.1）若多边形A没有内环，而多边形B有内环，则可确定多边形A和B的DE-9IM的参数值为：“TTTFTFFFF”，计算完毕，结束；

（4.2）若多边形A有内环，而多边形B无内环，则可确定多边形A和B的DE-9IM的参数值为：“TFFTTFTFF”，计算完毕，结束；

（4.3）若多边形A与B均有内环：设多边形A的内环个数为n，记为A_内1…A_内n，多边形B的内环个数为m，记为B_内1…B_内m；设A_内k为一个多边形A内环，顺序统计A_内k(k∈(1,n))与B_内1…B_内m的拓扑关系，八种拓扑关系分别记为AIBINUM_关系；同理，顺序统计B_内j(j∈(1,m))与A_内1…A_内n的拓扑关系，记为BIAINUM_关系；遍历各内环，由统计值AIBINUM_关系可以确定DE-9IM中多边形A外部与多边形B内部的相交值；同理，BIAINUM_关系确定维度扩展九交模型（DE-9IM）中多边形A内部与多边形B外部的相交值，计算完毕，结束；

（5）若多边形A外环与多边形B的外环的拓扑关系为完全包含关系（Contains）或覆盖关系（Covers），具体计算过程如下：

（5.1）若多边形A没有内环，则可确定多边形A和B的DE-9IM的参数值为：“TTTF*TFF*”，计算完毕，结束；

（5.2）若多边形B没有内环，设多边形A的内环个数为n，其中每个内环分别记为A_内1…A_内n；顺序统计A_内k(k∈(1,n))与多边形B外环的拓扑关系，根据统计结果可逐步确定多边形A和B的DE-9IM的参数值，计算完毕，结束；

（5.3）若多边形A与B均有内环，统计多边形A的某个内环A_内k(k∈(1,n))，与多边形B外环的拓扑关系，记为AIBONUM_关系；再遍历统计A_内k(k∈(1,n))与B_内1…B_内m的拓扑关系，记为AIBINUM_关系；设i为包含在B外环中多边形A内环个数，比较i与m的关系，最终确定多边形A和B的DE-9IM的参数值，计算完毕，结束；

（6）若多边形A外环与多边形B的外环的拓扑关系为被完全包含关系（Inside）或被覆盖关系（Covered By），具体计算过程如下：

（6.1）若多边形B没有内环，则确定多边形A和B的DE-9IM的参数值为：“TFFT*FTT*”，计算完毕，结束；

（6.2）若多边形A没有内环，设多边形B的内环个数为m，其中每个内环分别记为B_内1…B_内m；顺序统计B_内j(j∈(1,m))与多边形A外环的拓扑关系，根据统计结果能够逐步确定多边形A和B的DE-9IM的参数值，计算完毕，结束；

（6.3）若多边形A与B均有内环，统计B_内j(j∈(1,m))与多边形A外环的拓扑关系，记为BIAONUM_关系；再遍历统计B_内j(j∈(1,m))与A_内1…A_内n的拓扑关系，记为BIAINUM_关系；设i为包含在多边形A外环中多边形B内环个数，比较i与n的关系，最终确定多边形A和B的DE-9IM的参数值，计算完毕，结束。

基于CPU+GPU架构的多边形数据空间关系查询并行系统，实现步骤如下：

（1）从用户输入的两个海量多边形图层数据中提取线段信息，利用CPU+GPU架构并行分析不同图层间所有线段的相交情况，对于确实相交的线段组合，按照相交分类规则对其进行归类，最终将所有的相交线段数据构成一个统一的集合；

（2）遍历输入的两个海量多边形图层数据，分别记为目标图层和源图层，对来自不同图层的所有多边形数据两两组合，计算目标图层多边形数据相对于源图层多边形数据的DE-9IM；对于一组待计算的两个多边形数据，首先分析它们外环之间的拓扑关系，若可以确定DE-9IM则终止计算，若不可以，则继续分析内环与外环之间的拓扑关系，若依旧无法确定参数值，则最后分析内环与内环之间的拓扑关系以最终确定DE-9IM的参数值；其中环与环的拓扑关系分析需要对（1）中得到的相交线段集合进行查询，以获取属于待计算环的线段之间的相交情况；

（3）DE-9IM记成一组由9个参数值构成的字符串，每一个参数值分别对应于一个多边形内部、边界和外部与另一个多边形内部、边界和外部的相交情况，若相交则为True，记为“T”，不相交则为False，记为“F”，无所谓是否相交则为DONTCARE，记为“*”，例如，若多边形A、B的DE-9IM为“FF*FFTTTT”，该字符串中每个参数值依次所表示的含义为：第一个参数值表示A的内部与B的内部的相交情况，“F”表示不相交；第二个参数表示A的内部与B的边界的相交情况，“F”表示不相交；第三个参数表示A的内部与B的外部的相交情况，“*”表示无所谓是否相交；第四个参数表示A的边界与B的内部的相交情况，“F”表示不相交；第五个参数表示A的边界与B的边界的相交情况，“F”表示不相交；第六个参数表示A的边界与B的外部的相交情况，“T”表示相交；第七个参数表示A的外部与B的内部的相交情况，“T”表示相交；第八个参数表示A的外部与B的边界的相交情况，“T”表示相交；第九个参数表示A的外部与B的外部的相交情况，“T”表示相交。

开放地理信息系统协会（Open GIS Consortium，OGC）制定的开源GIS实施标准协议中规定，多边形间的空间关系按照DE-9IM的部分参数值定义为以下几种，设多边形为A、B：满足“FF*FF****”称为“A、B分离”、满足“T*T***T**”称为“A、B重叠”、满足“F***T****”称为“A、B接触”、满足“T*F**F FF*”称为“A、B相等”、满足“T*****FF*”称为“A包含B”、满足“T*F**F***”称为“A包含于B”以及所有不“分离”的多边形均称为“A、B相交”；依照上述规则，若在步骤（2）中每一组多边形数据的DE-9IM计算出来的同时，将DE-9IM的部分参数值与用户所设定的空间关系查询条件进行比对，以判断该组多边形数据是否满足查询条件，若满足，则输出所有属于目标图层的多边形数据，即输出所有的多边形A，多边形B只作为辅助查询对象不需要作为结果输出。

本发明与现有技术相比的优点在于：使用CPU+GPU架构作为并行计算硬件架构，利用其强大的并行处理能力，快速处理多边形数据的线段相交情况，为后续的多边形间空间关系查询提高效率；通过对多边形空间关系查询算法的并行化改造，使其可以充分利用并行加速处理得到的线段相交情况，并在此基础上，获得空间关系查询结果；本发明最大限度的发挥硬件设备的并行计算效率，在数据规模庞大的情况下，提高多边形数据的空间关系查询速度，并保证其准确性。

附图说明

图1为本发明基于CPU+GPU架构的海量多边形数据空间关系查询的并行处理系统；

图2为本发明方法实现流程图；

图3为本发明线段相交种类示意图；其中（1）为普通相交，（2）为丁字相交，（3）为连接相交，（4）为叠置相交；

图4为本发明环Ha与环Hb之间八种拓扑关系示意图，p、q分别为环Ha、环Hb上的点；H代表环，Ha与Hb分别代表两个不同的环；

图5为本发明环Ha与环Hb为叠置关系（Overlap）时的局部示意图；H代表环，Ha与Hb分别代表两个不同的环；

图6为本发明环Ha与环Hb只有连接和叠置相交情况下，不为相等关系（Equal）的特殊情况示意图；H代表环，Ha与Hb分别代表两个不同的环；

图7为本发明与环Ha的线段发生连接相交或丁字相交的某一条环Hb的线段示意图；H代表环，Ha与Hb分别代表两个不同的环；

图8为本发明多边形A、B外环为分离关系（Disjoint）时示意图；

图9为本发明多边形A、B外环为叠置关系（Overlap）时示意图；

图10为本发明多边形A、B外环为接触关系（Meet）时示意图；

图11为本发明多边形A、B外环为相等关系（Equal）时，A、B内环为叠置关系（Overlap）示意图；

图12为本发明多边形A、B外环为相等关系（Equal）且A、B均有内环时关系判断流程图；

图13为本发明多边形A、B外环为完全包含关系（Contains）或为覆盖关系（Covers）且B没有内环时关系判断流程图；

图14为本发明多边形A、B外环为完全包含关系（Contains）或为覆盖关系（Covers）时，A内环与B外环为叠置关系（Overlap）示意图；中a为完全包含关系（Contains），b为叠置关系（Overlap）；

图15为本发明多边形A、B外环为完全包含关系（Contains）或为覆盖关系（Covers）且A、B均有内环时关系判断流程图；

图16本发明多边形A、B外环为完全包含关系（Contains）或为覆盖关系（Covers）且A、B均有内环时，A、B内环为叠置关系（Overlap）示意图，其中a为完全包含关系（Contains），b为叠置关系（Overlap）。

具体实施方式

为了更好地理解本发明，先对一些基本概念进行一下解释说明。

目标图层：作为空间关系查询中被查询对象的图层。

源图层：作为空间关系查询中辅助查询对象的图层。

DE-9IM：DE-9IM（维度扩展九交模型）描述多边形之间的空间关系，它是一个3*3的矩阵，为方便运算，记成一组由9个参数值构成的字符串，每一个参数值分别对应于一个多边形内部、边界和外部与另一个多边形内部、边界和外部的相交情况，若相交则为True，记为“T”，不相交则为False，记为“F”，无所谓是否相交则为DONTCARE，记为“*”，例如，若多边形A、B的DE-9IM为“FF*FFTTTT”，该字符串中每个参数值依次所表示的含义为：第一个参数值表示A的内部与B的内部的相交情况，“F”表示不相交；第二个参数表示A的内部与B的边界的相交情况，“F”表示不相交；第三个参数表示A的内部与B的外部的相交情况，“*”表示无所谓是否相交；第四个参数表示A的边界与B的内部的相交情况，“F”表示不相交；第五个参数表示A的边界与B的边界的相交情况，“F”表示不相交；第六个参数表示A的边界与B的外部的相交情况，“T”表示相交；第七个参数表示A的外部与B的内部的相交情况，“T”表示相交；第八个参数表示A的外部与B的边界的相交情况，“T”表示相交；第九个参数表示A的外部与B的外部的相交情况，“T”表示相交。

下面结合附图对本发明进行详细说明。

如图1所示，本发明一种基于CPU+GPU架构的海量多边形数据空间关系查询的并行处理系统由线段间相交分析模块、环间拓扑关系分析模块、多边形间DE-9IM计算模块和图层间空间关系查询模块构成。

如图2所示，整个实现过程如下：

（1）图层间空间关系查询模块提供整个系统的运行框架，在用户请求时，首先运行线段间相交分析模块，根据用户输入的两个海量多边形图层数据，提取其中的线段信息，利用CPU+GPU架构并行分析不同图层间所有线段的相交情况，对于确实相交的线段组合，按照相交分类规则对其进行归类，最终将所有的相交线段数据构成一个统一的集合，供环间拓扑关系分析模块调用；

（2）遍历用户输入的两个海量多边形图层数据，分别记为目标图层和源图层，对来自不同图层的所有多边形数据两两组合，再调用多边形间DE-9IM计算模块，计算目标图层多边形数据相对于源图层多边形数据的DE-9IM；对于一组待计算的两个多边形数据，加载环间拓扑关系分析模块，首先分析它们外环之间的拓扑关系，若可以确定DE-9IM则终止计算，若不可以，则继续分析内环与外环之间的拓扑关系，若依旧无法确定参数值，则最后分析内环与内环之间的拓扑关系以最终确定DE-9IM的参数值；其中环与环的拓扑关系分析需要对（1）中得到的相交线段集合进行查询，以获取属于待计算环的线段之间的相交情况；

（3）开放地理信息系统协会（Open GIS Consortium，OGC）制定的开源GIS实施标准协议中规定，多边形间的空间关系按照DE-9IM的部分参数值定义为以下几种，设多边形为A、B：满足“FF*FF****”称为“A、B分离”、满足“T*T***T**”称为“A、B重叠”、满足“F***T****”称为“A、B接触”、满足“T*F**F FF*”称为“A、B相等”、满足“T*****FF*”称为“A包含B”、满足“T*F**F***”称为“A包含于B”以及所有不“分离”的多边形均称为“A、B相交”；依照上述规则，若在步骤（2）中每一组多边形数据的DE-9IM计算出来的同时，将DE-9IM的部分参数值与用户所设定的空间关系查询条件进行比对，以判断该组多边形数据是否满足查询条件，若满足，则输出所有属于目标图层的多边形数据，即输出所有的多边形A，多边形B只作为辅助查询对象不需要作为结果输出。

上述各模块的具体实现过程如下：

1.线段间相交分析模块

（1）对于输入的两个海量多边形图层数据，分别遍历提取两个海量多边形图层数据中所有多边形的线段信息，将不属于同一图层的独立线段两两组合；

（2）利用CPU+GPU架构的并行计算技术，对所有线段组合进行并行分析，得到所有相交线段集合及其相交种类，分析过程如下：

（2.1）排除不相交的线段组合，只记录所有相交的线段组合；

（2.2）对于所有相交的线段组合，判断它们的相交种类，相交种类如图3所示,其中（1）为普通相交，（2）为丁字相交，（3）为连接相交，（4）为叠置相交；

（3）输出所有相交线段的集合，分析完毕，结束。

2.环间拓扑关系分析模块

对于输入的两个环数据，设为环Ha与环Hb，根据组成它们的线段信息，从线段间相交分析模块输出的相交线段集合中提取它们之间线段的相交情况，据此分析环与环之间拓扑关系的具体过程如下：

（1）若无任何相交线段出现，此种情况下，环Ha的外部与环Hb的外部均有交集，环Ha的边界与环Hb的边界均无交集，则环Ha、Hb的拓扑关系为一定为分离关系（Disjoint）、完全包含关系（Contains）或被完全包含关系（Inside）三者之一；设点p为环Ha边界上任意一点，点q为环Hb边界上任意一点，利用射线法计算点与环之间的位置关系，据此确定最终拓扑关系，具体分析过程如下：

（1.1）若点p不在环Hb的内部，并且点q不在Ha的内部，则环Ha的内部与环Hb的内部无交集；环Ha的内部与环Hb的边界无交集，同样环Hb的内部与环Ha的边界亦无交集；环Ha的内部与环Hb的边界和外部均有交集，同样环Hb的内部与环Ha的边界和外部亦均有交集，则环Ha与环Hb的是分离关系（Disjoint），如图4中a所示，分析完毕，结束；

（1.2）若点p在环Hb的内部，并且点q不在环Ha的内部，则环Ha的内部、边界和外部均与环Hb的内部有交集；环Ha的内部与环Hb的边界和外部均无交集；环Ha的外部与环Hb的边界有交集，而环Ha的边界与环Hb的外部无交集，则环Ha与环Hb的是被完全包含关系（Inside），如图4中b所示，分析完毕，结束；

（1.3）若点p不在环Hb的内部，并且点q在环Ha的内部，若点p不在环Hb的内部，并且点q在环Ha的内部，则环Ha的内部与环Hb的内部、边界、外部均有交集；环Ha的边界与环Hb的外部有交集；环Ha的边界和外部与环Hb的内部均无交集；环Ha的外部与环Hb的边界无交集，则环Ha与环Hb的是完全包含关系（Contains），如图4中c所示，分析完毕，结束。

（2）若有相交线段出现时，此种情况下，环Ha的外部与环Hb的外部均有交集，环Ha的边界与环Hb的边界均有交集，再进行如下过程：

（2.1）如果统计结果中至少有一个普通相交，如图5所示，右侧线段代表环Hb的边界，有阴影一侧代表环Hb的内部，另一侧为环Hb的外部。此时环Ha与环Hb为普通相交。环Hb的边界进入环Ha的内部，则环Ha的内部与环Hb的内部、边界、外部均有交集；同理，环Hb的内部亦与环Ha的边界、外部有交集；由于存在环Hb的边界未进入环Ha的部分，所以环Ha的外部与环Hb的边界有交集；同理，环Ha的边界与环Hb的外部亦有交集，上述关系如图4中d所示，则环Ha和环Hb的拓扑关系为叠置关系（Overlap），分析完毕，结束；

（2.2）如果（2.1）不成立时，判断环Ha与环Hb的拓扑关系是否为相等关系（Equal）。反证法可知，如果统计结果中若有丁字相交，则环Ha与环Hb的重叠图像上必然会在丁字相交的交点处出现朝向不同的三条线段，然而，根据OGC简单要素规范可知，环上的任何一点只可能出现朝向不同的两条线段，所以，统计结果中不能出现丁字相交，否则环Ha与环Hb不可能为相等关系（Equal）。此时，统计结果中只有连接相交和叠置相交。但也有可能出现如图6所示的情况：细实线为环Hb，粗虚线为环Ha。若环Ha与环Hb线段相交集合中环Ha的所有线段都和环Hb的某条线段发生叠置相交关系，则不会出现如图7的情况，即环Ha的外部与环Hb的内部和边界均无交集；同理环Ha的内部和边界与环Hb的外界亦均无交集；拓扑关系矩阵如图4中e所示，则环Ha和环的拓扑关系必为相等关系（Equal），同时线段相交情况中没有出现丁字相交，并且线段相交集合中环Ha的所有线段都和环Hb的某条线段发生叠置相交关系，则Ha与Hb的拓扑关系为相等关系（Equal），分析完毕，结束；

（2.3）若上述情况均不成立，提取与环Ha的线段发生连接相交和丁字相交的所有环Hb的线段，利用射线法计算所有线段两个端点与环Ha的位置关系，如图7所示，若环Hb的某一边进入环Ha的内部，阴影一侧代表环Hb的内部，另一侧为环Hb的外部，则环Ha的内部与环Hb的内部、边界和外部均有交集，据此方法确定最终拓扑关系，具体分析过程如下：

（2.3.1）若端点都在环Ha的内部和边界上，环Ha的边界与环Hb的内部无交集而与环Hb的外部有交集，环Ha的外部与环Hb的内部和边界均无交集，拓扑关系矩阵如图4中f所示，则环Ha与环Hb的拓扑关系为覆盖关系（Covers），分析完毕，结束；

（2.3.2）若端点都在环Ha的外部和边界上，环Ha的外部与环Hb的内部、边界均有交集；且环Ha边界上存在一点p1在环Hb的内部，则环Hb的内部与环Ha的内部、边界均有交集，拓扑关系矩阵为图4中g所示，故环Ha与环Hb的拓扑关系为被覆盖关系（CoveredBy），分析完毕，结束；

（2.3.3）若端点都在环Ha的外部和边界上，环Ha的外部与环Hb的内部、边界均有交集；且环Ha边界上不存在点在环Hb的内部，即环Hb的外部与环Ha的内部和边界亦均有交集，拓扑关系矩阵表示如图4中h所示，环Ha、环Hb的拓扑关系为接触关系（Meet），分析完毕，结束；

（2.3.4）若分析过程依然没有结束，则Ha与Hb的拓扑关系只能为叠置关系（Overlap），分析完毕，结束。

3.多边形间DE-9IM计算模块

对于输入的两个多边形数据，设为多边形A和多边形B，调用环间拓扑关系分析模块，分别获得两个多边形内、外环之间的拓扑关系，据此计算多边形间DE-9IM参数值的具体过程如下：

（1）若多边形A外环与多边形B外环的拓扑关系为分离关系（Disjoint），如图8所示，多边形A的内部与多边形B的内部相交且多边形A的边界与多边形B的边界不相交，补全其余参数值，可确定多边形A和B的DE-9IM的参数值为：“FFTFFTTTT”，计算完毕，结束；

（2）若多边形A外环与多边形B外环的拓扑关系为叠置关系（Overlap），如图9所示，多边形A的内部与多边形B的内部相交，且多边形A的内部和多边形B的外部、多边形A的外部与多边形B的内部均相交，补全其余参数值，可确定多边形A和B的DE-9IM的参数值为：“TTTTTTTTT”，计算完毕，结束；

（3）若多边形A外环与多边形B外环的拓扑关系为接触关系（Meet），如图10所示，多边形A的内部与多边形B的内部、多边形A的内部与多边形B的边界、多边形B的内部与多边形A的边界均不相交，补全其余参数值，可确定多边形A和B的DE-9IM的参数值为：“FFTFTTTTT”，计算完毕，结束；

（4）若多边形A外环与多边形B外环的拓扑关系为相等关系（Equal），具体计算过程如下：

（4.1）若多边形A没有内环，而多边形B有内环，则多边形A与B外环重合，多边形B的内部与多边形A的内部相交，多边形B的内部和边界与多边形A的外界均不相交，补全其余参数值，可确定多边形A和B的DE-9IM的参数值为：“TTTFTFFFF”，计算完毕，结束；

（4.2）若多边形A有内环，而多边形B无内环，多边形A的内部与多边形B的内部相交，而多边形A的内部与边界与多边形B的外部均不相交，补全其余参数值，可确定多边形A和B的DE-9IM的参数值为：“TFFTTFTFF”，计算完毕，结束；

（4.3）若多边形A与B均有内环：设多边形A的内环个数为n，记为A_内1…A_内n，多边形B的内环个数为m，记为B_内1…B_内m，如图11所示，具体实施方法如下：

（4.3.1）首先，从A_内1开始，与B_内1…B_内m比较。设A_内k为多边形A的一个内环，顺序统计A_内k(k∈(1,n))与B_内1…B_内m的拓扑关系，八种拓扑关系分别记为AIBINUM_关系。设B_内j(j∈(1,m))为多边形B的一个内环。若A_内k(k∈(1,n))与B_内j(j∈(1,m))出现叠置关系（Overlap），如图12所示。则多边形A的内部与多边形B的内部、多边形A的内部与多边形B的外部、多边形A的外部与多边形B的内部均相交，可确定多边形A和B的DE-9IM的参数值为：“T*T***T**”,计算完毕，结束；

（4.3.2）若未出现叠置关系（Overlap），则继续完成A_内k循环。若A_内k与B_内j仅有分离关系（Disjoint）和接触关系（Meet），即AIBINUM_Disjoint+AIBINUM_Meet＝m，可推出多边形A的外部与多边形B的内部相交。若还出现完全包含关系（Contains）和覆盖关系（Covers）AIBINUM_Disjoint+AIBINUM_Meet+AIBINUM_Contains+AIBINUM_Covers＝m，则多边形A的外部与多边形B的内部一定相交。若AIBINUM_Disjoint+AIBINUM_Meet+AIBINUM_Contains+AIBINUM_Covers≠m，此时若k≠n，则k++，开始新的A_内k与B_内1…B_内m拓扑关系的统计。若k＝n，则循环结束，此时多边形A的外部与多边形B的内部与边界均不相交。同理，顺序统计B_内j(j∈(1,m))与A_内1…A_内n的拓扑关系，记为BIAINUM_关系，结果也分为两种情况：“多边形A的内部与多边形B的外部相交”或“多边形A的内部与边界与多边形B的外部均不相交”。

综合以上计算结果，由于多边形A、B外环相等，多边形A的内部与多边形B的内部肯定相交：

（4.3.2.1）若多边形A的外部与多边形B的内部相交，且多边形A的内部与多边形B的外部有相交，可确定多边形A和B的DE-9IM的参数值为：“T*T***T**”，计算完毕，结束；

（4.3.2.2）若多边形A的外部与多边形B的内部相交，但多边形A的内部与多边形B的外部及边界不相交，可确定多边形A和B的DE-9IM的参数值为：“T*****FF*”，计算完毕，结束；

（4.3.2.3）若多边形A的外部与边界与多边形B的内部不相交，但多边形A的内部与多边形B的外部相交，可确定多边形A和B的DE-9IM的参数值为：“T*F**F***”，计算完毕，结束；

（4.3.2.4）若多边形A的外部与边界与多边形B的内部不相交，且多边形A的内部也与多边形B的外部及边界不相交可确定多边形A和B的DE-9IM的参数值为：“T*F**F FF*”，计算完毕，结束；

（5）若多边形A外环与多边形B的外环的拓扑关系为完全包含关系（Contains）或覆盖关系（Covers），首先可确定多边形A的内部与多边形B的外部一定相交，其余参数计算过程如下：

（5.1）若多边形A没有内环，A的内部与B的内部相交，但A的外部与B的内部、边界均无交集，则可确定多边形A和B的DE-9IM的参数值为：“TTTF*TFF*”，计算完毕，结束；

（5.2）若多边形B没有内环，设多边形A的内环个数为n，其中每个内环分别记为A_内1…A_内n；如流程图如图13所示，首先统计A_内k(k∈(1,n))与多边形B外环的拓扑关系，记为AIBONUM_关系：

（5.2.1）若A_内k与多边形B外环出现叠置关系（Overlap）、被覆盖关系（Covered By）或被完全包含关系（Inside），以叠置关系（Overlap）为例，如图14所示，多边形A的内部与多边形B的内部、多边形B的外部均有交集，且多边形A的外部与多边形B的内部亦有交集，则可确定多边形A和B的DE-9IM的参数值为：“T*T***T**”，计算完毕，结束；

（5.2.2）若无上述三种关系，则继续统计：

（5.2.2.1）若A_内k与多边形B外环出现分离关系（Disjoint）和接触关系（Meet）数目等于n，即AIBONUM_Disjoint+AIBONUM_Meet＝n，则可确定多边形A和B的DE-9IM的参数值为：“T*****FF*”，计算完毕，结束；

（5.2.2.2）若A_内k与多边形B外环出现分离关系（Disjoint）和接触关系（Meet）数目不等于N，即AIBONUM_Disjoint+AIBONUM_Meet≠n，判断AIBONUM_Contains是否为0：

（5.2.2.2.1）若AIBONUM_Contains＝0，可确定多边形A和B的DE-9IM的参数值为：“F***T****”，计算完毕，结束；

（5.2.2.2.2）若AIBONUM_Contains≠0，可确定多边形A和B的DE-9IM的参数值为：“FF*FF****”，计算完毕，结束；

（5.3）若多边形A与B均有内环，设多边形A的内环个数为n，记为A_内1…A_内n，多边形B的内环个数为m，记为B_内1…B_内m。如图15所示，统计A_内k(k∈(1,n))与多边形B外环的拓扑关系，记为AIBONUM_关系，计算过程如下：

（5.3.1）如图15所示，若A_内k与多边形B外环一旦出现叠置关系（Overlap），则多边形A的内部与多边形B的内部以及外部均有交集，且A的外部与B的内部亦相交，可确定多边形A和B的DE-9IM的参数值为：“T*T***T**”，计算完毕，结束；

（5.3.2）若无叠置关系（Overlap）出现，则继续统计：

（5.3.2.1）若A_内k与多边形B外环关系中，分离关系（Disjoint）和接触关系（Meet）数目等于n，即AIBONUM_Disjoint+AIBONUM_Meet＝n，则可判断，多边形A的内部与多边形B的外部相交，多边形A的外部与多边形B的内部均不相交，可确定多边形A和B的DE-9IM的参数值为：“T*****FF*”，计算完毕，结束；

（5.3.2.2）若A内k与多边形B外环关系中，分离关系（Disjoint）和接触关系（Meet）数目不等于n，即AIBONUM_Disjoint+AIBONUM_Meet≠n，则继续统计A_内k与多边形B外环出现完全包含关系（Contains）的数目：

（5.3.2.2.1）若AIBONUM_Contains≠0，则多边形A的内部与多边形B的内部和边界不相交，但与多边形B的外部有交集，多边形A的边界与多边形B的内部以及边界不相交，可确定多边形A和B的DE-9IM的参数值为：“FF*FF****”，计算完毕，结束；

（5.3.2.2.2）若AIBONUM_Contains＝0，继续计算：

（5.3.2.2.2.1）AIBONUM_Equal≠0或AIBONUM_Covers≠0，则可判断多边形A的内部与多边形B的内部不相交但与多边形B的外部相交，且多边形A的边界与多边形B的边界有交集，可确定多边形A和B的DE-9IM的参数值为：“T*****FF*”，计算完毕，结束；

（5.3.2.2.2.2）否则，设i为包含在多边形B外环中所有多边形A内环个数：

（5.3.2.2.2.2.1）一旦A_内k(k∈(1,i))与B_内j(j∈(1,m))出现叠置关系（Overlap），则如图16所示，多边形A的内部与多边形B的外部相交，多边形A的外部与多边形B的内部相交，可确定多边形A和B的DE-9IM的参数值为：“T*T***T**”，计算完毕，结束；

（5.3.2.2.2.2.2）若无叠置关系（Overlap）出现，则继续完成A_内k(k∈(1,i))循环：

（A）若AIBINUM_Disjoint+AIBINUM_Meet+AIBINUM_Contains+AIBINUM_Covers＝m，可确定多边形A和B的DE-9IM的参数值为：“T*T***T**”，计算完毕，结束；

（B）若AIBINUM_Disjoint+AIBINUM_Meet+AIBINUM_Contains+AIBINUM_Covers≠m，判断i与m的大小关系：

（B-1）若i<m，则多边形A的内部与多边形B的外部相交，多边形A的外部与多边形B的内部亦相交，可确定多边形A和B的DE-9IM的参数值为：“T*T***T**”，计算完毕，结束；

（B-2）若i≥m，则多边形A的内部与多边形B的外界相交，A的外部与B的内部和边界相交，可确定多边形A和B的DE-9IM的参数值为：“T*****FF*”，计算完毕，结束；

（6）若多边形A外环与多边形B的外环的拓扑关系为被完全包含关系（Inside）或被覆盖关系（Covered By），具体计算过程（5）相同，只需要将计算所得DE-9IM转置即可。

本发明未详细阐述部分属于本领域公知技术。

以上所述，仅为本发明部分具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本领域的人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。