基于庞加莱对偶的三维自由拓扑模型

拓扑关系是进行空间查询、分析和推理的基础。在三维空间数据多重表达研究中，拓扑关系的多重表达和一致性问题一直没有得到解决，限制了三维拓扑理论的发展和应用。本课题基于庞加莱对偶和组合图理论，研究三维拓扑的多重表达机制和基于欧拉示性数的拓扑算子，建立三维自由拓扑模型，实现三维拓扑信息面向不同抽象层次和应用主题的表达。参考"ISO 19107空间模式"规范，深入研究动态、视点相关以及LOD等条件下，对偶图的生成与基于"边界"和"对偶"关系的拓扑推导、计算方法，解决自由拓扑模型中三维欧式几何的嵌入问题。本课题从模型的理论基础和构建方法入手，从庞加莱对偶和组合图理论的角度阐明三维拓扑多重表达和一致性约束的理论和方法，从对偶图的生成以及拓扑推导算法的角度提出自由拓扑模型中三维欧式几何的嵌入方法，为三维拓扑技术的进一步研究与应用提供新的理论和方法。

拓扑关系是进行空间查询、分析和推理的基础。本课题针对三维地理空间中拓扑关系的多重表达、拓扑关系快速构建以及典型拓扑分析算法展开研究。.　　（1）本课题提出一种基于组合图与庞加莱对偶的三维拓扑模型（Combinatorial Maps and Poincare duality-based Topology Model,CMPTM）。其特点是：1）数据结构简单，仅包含Dart、Dual、alpha等几个基本元素。2）具有严密的数学基础,采用代数方法进行拓扑查询、遍历与拓扑分析。3）拓扑与几何描述分离，支持语义的嵌入。4）能够描述三维流形、非流形对象拓扑关系。.　　（2）针对拓扑关系的构建问题，提出了点/多面体、多边形/多边形等三维几何对象拓扑关系计算算法。针对线数据集拓扑关系构建，提出一种基于空间索引的线数据集拓扑关系构建方法。设计了适用于不同分布模式、不同几何形态三维数据集的空间索引结构Pattern List。提出了基于离群值分离的基态Pattern List生成算法。设计了基于“质变”与“量变”解析的空间目标批量插入算法。提出了基于Pattern List的三维线数据集拓扑构建算法。.　　（3）基于CMPTM中的Dual、alpha操作，设计了拓扑图的深度遍历、广度遍历算法。针对Dijkstra算法适用于稀疏关联矩阵、不支持拓扑网络嵌套、复杂三维目标难以纳入网络分析等问题，提出了基于CMPTM的改进Dijkstra算法。其特点是：1）将深度遍历和目标函数共同作为结点搜索条件，可以有效减少单独依靠目标函数作为搜索条件时的多路径搜索问题。2）通过0、1-orbit运算来代替邻接矩阵，可以支持层次网络拓扑图的嵌套，提高最短路径分析算法的适用性。3）使用orbit()、Dual(orbit())作为结点遍历操作，支持体和复杂边对象的最短路径分析。. （4）面向室内导航应用以及三维楼宇等人口密集场所公共安全需求，开展了楼宇三维寻径分析测试验证。用Dart、Dual作为三维楼宇拓扑模型的基本描述单元，用k-cell来实现三维楼宇数据的拓扑分解，用k-embedding来实现拓扑信息与几何信息的关联，用orbit和alpha来实现拓扑的遍历查找。设计了单点疏散、多点疏散等算法。试验表明本课题所设计的拓扑模型具有灵活的拓扑表达能够，支持拓扑关系的快速构建与分析。