基于线性和岛屿约束的Delaunay三角网构建算法研究

针对基于线性和岛屿约束的Delaunay三角网构建算法的不足,从减少算法计算机实现步骤出发,研究改进了线段相交判断、首三角形确定等影响域多边形搜索相关算法;在分析当前存在的多边形三角剖分算法基础上,给出了存在重复点(悬边)的多边形三角剖分算法;在影响域多边形搜索阶段充分利用多边形间的拓扑关系信息,消除了岛屿约束内部三角形删除时需遍历三角形数据的不足.算法涵盖线性和岛屿约束的构建,综合性强,效率高且易于实现.     

面向矢量数据叠加分析的拓扑一致性处理研究

在叠加分析、缓冲区分析、拓扑分析等各种矢量数据分析过程中,首要面对的便是矢量数据拓扑一致性问题。拓扑一致性处理是对GIS矢量数据中由于采集、存储、压缩、转换导致的空间拓扑关系不一致问题进行的拓扑处理,其使得待处理数据在容限范围内具有拓扑一致性,从而便于后续相关分析功能的进行。该文在分析和总结已有拓扑一致性处理算法的基础上,提出了一种更为高效的拓扑一致性处理改进算法,包括弧段间拓扑处理、节点与弧段间拓扑处理、节点间邻近搜索等核心过程。对比实验表明,该算法在保证拓扑一致性处理效果的基础上具有较高的处理性能,是一种实用性较强的拓扑一致性处理算法。     

一种基于TIN的地形剖面线生成算法

在目前已有基于规则格网(Grid)生成地形剖面线的基础上，提出了一种适用于不规则三角网(TIN)的剖面线生成算法。该算法充分利用TIN中各三角形间存在的拓扑关系，实现了与剖面线相交三角形的快速搜索，大大提高了算法的执行效率。由于地形简化后的TIN仍保留三角形间的拓扑关系，该剖面线生成算法还适用于多分辨率的海量TIN数据。     

二维Delaunay三角网的任意点删除算法研究

针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

一种新的土地利用图斑边界一致化改正算法

针对边界一致化改正过程中存在的边界提取不准确以及未能自动维持图斑拓扑一致性的问题,该文提出了一种新的三角剖分算法,对共享边界不一致的图斑进行自动检测和改正。在最大最小角原则和非法边原则的基础上,采用基于四边形的方法进行三角剖分,自动提取并平滑图斑缓冲区域间的骨架线以代替共享边界,达到边界一致化的目的。应用该算法与Delaunay三角网算法分别对第三次全国国土调查中的土地利用数据进行边界改正,实验结果表明:该算法不仅能够有效解决Delaunay三角网中骨架线延伸方向无法确定的问题,而且生成的新边界能够近似拟合原边界的自然弯曲形态,保持图斑边界的拓扑一致性。     

地图矢量数据拓扑关系生成算法

拓扑关系的建立是地图矢量数据管理和更新的重要内容。在综合多种典型拓扑算法优点的基础上,详细描述了拓扑关系生成算法的主要过程,并在线要素互相交断链、结点匹配和特殊情况处理等方面对算法进行了改进。最后以1∶25万济宁市地形图数据进行了实验,结果表明该算法在效率方面优于传统算法。     

基于简单要素模型的多边形分割算法

多边形是GIS研究和应用中使用最频繁的几何对象,该文描述了基于简单要素模型的任意多边形分割算法。从计算几何出发,结合GIS空间数据的特点,将基于简单要素模型的多边形分割算法设计为:1)对多边形及分割线的边界排序,基于扫描线及外包矩形检测查找可能相交的线段,提高相交线段的搜索效率;2)计算交点生成结点信息(包括交点坐标、线号及交点的出入),并存储在独立的单向链表中;3)根据结点链表和原多边形坐标搜索结果多边形。该算法能够分割任意简单多边形(凹凸、曲线边界和带洞的多边形)以及有共享边的多边形。最后在MapGIS7.0平台上,实现了基于简单要素类的多边形分割功能。     

面向指路标志系统的交通网络数据模型及应用

指路标志指示的信息与路网的拓扑数据、几何特征和交通网络的服务规则紧密相关。在传统的弧段—结点数据模型基础上拓展了结点—邻近结点拓扑关系,加入与交叉口相关的路网几何特征和交通网络服务规则,建立面向指路标志系统的交通网络数据模型。将这种数据模型应用于广州市城市路网的指路标志系统中,实现了城市路网指路标志的自动生成。     

简单要素模型下多边形叠置分析算法

现有的矢量空间叠置分析多采用拓扑模型,要求建立完整的数据拓扑关系。该文采用简单要素模型,以多边形叠置交运算为例,介绍简单要素模型下空间叠置分析的具体实现,着重讨论多边形交运算的交替搜索算法,在线段求交中对连续出入点、重交点等特殊数据进行处理。在实际应用中,该算法可较好解决大规模复杂数据层的叠置交运算,比同规模的拓扑叠置运算效率高。     

基于GIS的高质量约束Delaunay三角网格剖分

在分析现有非结构化网格剖分算法的基础上,提出了一种GIS支持下的改进分治算法实现约束Delaunay三角网格剖分.该方法利用了GIS的空间拓扑关系对算法输入数据进行预处理,基于三角形的统一数据结构实现了网格细化,对输出剖分网格进行准确的拓扑和约束条件的检查,并基于推进阵面算法思想,结合空间邻近拓扑关系实现了三角剖分节点和网格的重新编号,方便了实际问题中开边界条件的赋值,提高了计算效率.实例应用表明,该方法大大简化了数值模型非结构化网格剖分的前处理过程,集成了几种综合算法的优点,在保证原分治算法时间复杂度的基础上,提高了约束条件下Delaunay三角网格生成的质量.