共查询到16条相似文献，搜索用时 437 毫秒
1.
针对基于线性和岛屿约束的Delaunay三角网构建算法的不足,从减少算法计算机实现步骤出发,研究改进了线段相交判断、首三角形确定等影响域多边形搜索相关算法;在分析当前存在的多边形三角剖分算法基础上,给出了存在重复点(悬边)的多边形三角剖分算法;在影响域多边形搜索阶段充分利用多边形间的拓扑关系信息,消除了岛屿约束内部三角形删除时需遍历三角形数据的不足.算法涵盖线性和岛屿约束的构建,综合性强,效率高且易于实现. 相似文献
2.
约束Delaunay三角网点删除的一体化凸耳消元法(IEE) 总被引：4，自引：1，他引：3
对Delaunay三角网(CD—TIN)点删除算法——凸耳消元法(EE)进行剖析,提出约束Delaunay三角网的点删除算法——体化凸耳消元法(IEE)。该算法将CD-TIN的点删除转化为点的影响域重构,并保证重构后的CD—TIN满足CD—TIN的可视性与空圆法则,确保了CD—TIN的拓扑完备性,实现了CD—TIN中约束点与非约束点删除的一体化操作和局部更新,并得到实验验证。 相似文献
3.
二维Delaunay三角网局部更新:点插入与点删除 总被引：16，自引：3，他引：13
二维Delaunay三角网的局部更新在地学分析、道路CAD、城市规划等领域有着广泛的用途,点插入和点删除则是其中最重要、最基本的操作。该文针对原有逐点插入法和凸耳权值点删除算法存在的不足,利用动态包围三角形和特征三角形分别对其进行改进,在设计的具有拓扑关系Delaunay的三角网数据结构基础上,实现Delaunay三角网的快速局部更新,且使之满足Delaunay特性。最后通过模拟实验验证了算法的正确性和高效性。 相似文献
4.
一种高准确度的约束Delaunay三角网生成算法研究 总被引：1，自引：0，他引：1
约束线段的嵌入是CDT两步法的关键步骤之一,目前该方面的研究还不够完善,主要忽视了影响区域是凹多边形和影响区域内包含悬挂点的情况.该文研究带有约束条件的Delaunay三角网的生成问题,考虑了约束线段影响区域的特殊情况,采用递归割耳法嵌入约束线段,先将影响区域调整为简单多边形,再递归寻找并割去多边形的耳,最终将影响区域重新三角剖分.该方法可有效提高约束DIelaunay三角网的质量. 相似文献
5.
不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。 相似文献
6.
《地理与地理信息科学》2020,(4)
土石方量计算是工程建设的重要步骤,其计算精度是提高工程质量的首要问题。针对利用无约束不规则三角网计算土石方量时存在的计算精度问题,该文利用三维激光点云数据,根据约束Delaunay三角网的构建原理,探讨了基于等高线约束的Delaunay三角网方法在土石方量计算中的应用。首先,以土石方的等高线作为约束线,利用迭代算法对无约束不规则三角网进行剖分,构建等高线约束Delaunay三角网,并进行土石方量计算。然后,将计算结果与无约束不规则三角网、方格网法计算结果进行对比与误差分析,验证了该方法的计算精度,为基于三维点云数据的土石方量精确计算提供了参考。 相似文献
7.
《地理与地理信息科学》2016,(3)
从众源轨迹数据中提取道路几何数据相对于传统的道路数据获取方法具有低成本、高现势性的优点。然而,由于轨迹数据采样稀疏、数据量大、高噪音等特征使得道路中心线提取仍显困难。针对该问题,提出一种基于约束Delaunay三角网的道路中心线提取方法。首先对预处理后的车辆轨迹线构建约束Delaunay三角网,根据整体长边约束准则删除长边以提取道路面域多边形;然后对道路面多边形二次构建Delaunay三角网,提取道路中心线。利用北京市一天时间的出租车轨迹数据进行算法实验,将实验结果与栅格化方法结果进行定性定量地评价分析。结果表明该方法提取的道路中心线数据在几何、拓扑精度方面比栅格化方法提高约10%以上。另外,以复杂环形道路为例,证明了该方法比栅格化方法更适合于复杂道路结构、较大密度差异的轨迹数据。因此,该方法不仅适合大数据处理、结果精度高,且算法成熟、易于实现。 相似文献
8.
简要介绍了地质建模概念及层状地质体建模方法,考虑到Delaunay三角剖分良好的边界约束适应能力,提出了一种以地质层面Delaunay三角网为约束条件进行约束四面体剖分构建地质模型的方法。在通过对南京河西地区钻孔数据进行自适应插值处理后,应用此算法构建该地区的三维地下浅层空间地质体模型,实践证明该方法能够得到可视化效果较好的地质模型,并可高效地支撑地学空间分析与计算,为城市规划提供更好的决策支持。 相似文献
9.
《地理与地理信息科学》2019,(6)
针对边界一致化改正过程中存在的边界提取不准确以及未能自动维持图斑拓扑一致性的问题,该文提出了一种新的三角剖分算法,对共享边界不一致的图斑进行自动检测和改正。在最大最小角原则和非法边原则的基础上,采用基于四边形的方法进行三角剖分,自动提取并平滑图斑缓冲区域间的骨架线以代替共享边界,达到边界一致化的目的。应用该算法与Delaunay三角网算法分别对第三次全国国土调查中的土地利用数据进行边界改正,实验结果表明:该算法不仅能够有效解决Delaunay三角网中骨架线延伸方向无法确定的问题,而且生成的新边界能够近似拟合原边界的自然弯曲形态,保持图斑边界的拓扑一致性。 相似文献
10.
针对目前各种点插入算法的不足,提出一种二维Delaunay三角网任意点插入算法。首先基于凸壳区分点的位置,并利用三角形面积坐标、重心和点与有向线段关系三者构建的融和算法搜索插入点所在三角形,然后通过构建和优化新三角形完成点的插入,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。 相似文献
11.
多边形主骨架线提取算法的设计与实现 总被引：1，自引：0，他引：1
在Delaunay三角网的基础上对骨架线节点进行了分类,通过确定主骨架线的两个端点,运用回溯法提取了多边形的主骨架线,同时给出了详细的算法步骤,并在Visual C++2003环境下实现了该算法。较之其他算法,该算法思路简捷,易于编程,生成的主骨架线形态优良,较好地反映了多边形的主体形状特征和主延伸方向。 相似文献
12.
Several algorithms have been proposed to generate a polygonal ‘footprint’ to characterize the shape of a set of points in the plane. One widely used type of footprint is the χ-shape. Based on the Delaunay triangulation (DT), χ-shapes guaranteed to be simple (Jordan) polygons. This paper presents for the first time an incremental χ-shape algorithm, capable of processing point data streams. Our incremental χ-shape algorithm allows both insertion and deletion operations, and can handle streaming individual points and multiple point sets. The experimental results demonstrated that the incremental algorithm is significantly more efficient than the existing, batch χ-shape algorithm for processing a wide variety of point data streams. 相似文献
13.
GPU加速的多边形叠加分析 总被引：2，自引：0，他引：2
叠加分析是地理信息系统最重要的分析功能之一,对多边形图层进行叠加分析要花费大量时间。为此,将GPU用于多边形叠加分析过程中的MBR过滤及多边形剪裁两个阶段。对MBR过滤阶段,提出了基于GPU的通过直方图及并行前置和实现的MBR过滤算法。对多边形剪裁阶段,通过改进Weiler-Atherton算法,使用新的焦点插入方法和简化的出入点标记算法,并结合并行前置和算法,提出了基于GPU的多边形剪裁算法。对实现过程中可能出现的负载不均衡情况,给出了基于动态规划的负载均衡方法。通过对这些算法的应用,实现对过滤阶段及精炼阶段的加速。实验结果表明,基于GPU的MBR过滤方法相对CPU实现的加速比为3.8,而基于GPU的多边形剪裁的速度比CPU实现快3.4倍。整体上,与CPU实现相比,GPU加速的多边形叠加提供了3倍以上的加速比。 相似文献
14.
多边形是GIS研究和应用中使用最频繁的几何对象,该文描述了基于简单要素模型的任意多边形分割算法。从计算几何出发,结合GIS空间数据的特点,将基于简单要素模型的多边形分割算法设计为:1)对多边形及分割线的边界排序,基于扫描线及外包矩形检测查找可能相交的线段,提高相交线段的搜索效率;2)计算交点生成结点信息(包括交点坐标、线号及交点的出入),并存储在独立的单向链表中;3)根据结点链表和原多边形坐标搜索结果多边形。该算法能够分割任意简单多边形(凹凸、曲线边界和带洞的多边形)以及有共享边的多边形。最后在MapGIS7.0平台上,实现了基于简单要素类的多边形分割功能。 相似文献
15.
简单要素模型下多边形叠置分析算法 总被引：1，自引：0，他引：1
现有的矢量空间叠置分析多采用拓扑模型,要求建立完整的数据拓扑关系。该文采用简单要素模型,以多边形叠置交运算为例,介绍简单要素模型下空间叠置分析的具体实现,着重讨论多边形交运算的交替搜索算法,在线段求交中对连续出入点、重交点等特殊数据进行处理。在实际应用中,该算法可较好解决大规模复杂数据层的叠置交运算,比同规模的拓扑叠置运算效率高。 相似文献