共查询到18条相似文献,搜索用时 109 毫秒
1.
基于虚拟网格的高效Delaunay三角网生成算法研究 总被引:1,自引:0,他引:1
针对传统逐点插入算法存在时间效率比较低的问题,设计了高效的存储结构,通过引入虚拟网格技术,在三角形定位和点的插入顺序方面作了改进和优化,提出了一种改进的D-三角网生成算法,提高了点插入过程中查找相应三角形的速度,有效的减少了重构三角形的数量,大大改进了逐点插入算法的时间效率.实验结果表明,改进后的算法具有较低的时间复杂度,能快速地生成三角网. 相似文献
2.
基于Qi算法的Delaunay三角网逐点插入法 总被引:1,自引:0,他引:1
Delaunay三角网在很多领域都有着广泛的应用,快速高效地生成Delaunay三角网十分重要。逐点插入法是构建Delaunay三角网中使用最广泛的方法之一。本文深入研究了使用逐点插入法构建不带约束条件Delaunay三角网的过程。在使用该方法生成Delaunay三角网中建立结点拓扑关系这一影响构网效率的关键步骤中引入了Qi算法,简化了该方法生成Delaunay三角网的复杂度。然后在向Delaunay三角网内插入约束边的过程中,再次引入Qi算法,从而提高了构网的效率。为了验证上述模型,我们在Microsoft Visual Studio 2005开发环境下,以C#为开发工具,采用底层开发模式实现了改进的逐点插入法,实验证明引入Qi算法能够提高逐点插入法Delaunay三角网构建及插入约束边的效率。 相似文献
3.
Delaunay三角网在GIS/VR中用途广泛,分割-归并法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法.在研究基于这两种算法的合成算法后,对其进行了两点改进.一是简化凸壳的生成;二是三角形快速定位,通过确定向量之间的关系来解决点的定位问题,避免了复杂运算.实验结果证明,改进后的算法不仅继承原算法兼顾空间和时间的性能,且执行效率有明显提高. 相似文献
4.
5.
一种改进的高效Delaunay三角网的生成算法 总被引:18,自引:0,他引:18
Delaunay三角网在GIS/VR中具有很广泛的用途,而分而治之算法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。本在研究了基于这两种算法的合成算法后,对其进行了修改和优化,形成了高效合成算法。高效合成算法中提出了通过确定点线关系来解决点的定位问题,优化了其LOP的算法,提高了算法的稳定性,使其执行效率得到很明显地提高,本算法的设计思想还可推广到三维空间。 相似文献
6.
7.
生成Delaunay三角网的改进算法 总被引:4,自引:0,他引:4
算法以原“改进的自连接Delaunay三角网生成算法”为基础。其主要方法仍是三角网生长法,但同时采用了逐点插入法中的凸壳。在原封闭点的基础上提出了封闭的边界点的概念,并增加了对边界点和边界边的识别和处理,从而进一步提高了构网效率。另外,采用的用边的法向量对边的某侧的点进行判断的方法也简单实用。 相似文献
8.
讨论了离散点建立Delaunay三角网算法的研究现状,并采用网格划分提高构网速度。由于三角形定位的速度是影响构网速度的关键因素,改进了基于点线关系方向定位算法,充分利用点与三角形的拓扑关系,减少点线关系的方向定位算法中计算重心的次数,从而提高了三角形定位的效率和构网速度。通过测试证明了算法的高效型和稳定性。 相似文献
9.
基于Delaunay三角网的地应力等值线生成算法 总被引:1,自引:0,他引:1
地应力分布是石油工程中非常重要的参数,区域地应力是通过将各单井数据处理计算其应力纵向分布,然后将不同测井深度的地应力进行区域插值,利用地应力等值线表现整个区域的地应力分布情况.介绍了在数据稀疏地区的Delaunay三角网格化算法,通过等值点的插值、追踪、平滑处理,结合MapObject GIS组件实现了等值线的Shapefile格式储存、分层显示,可直接应用于地理信息系统(GIS)的空间数据分析、查询等.该算法可用于实际软件开发、GIS二次开发和GIS应用. 相似文献
10.
一种高效的Delaunay三角网合并生成技术 总被引:10,自引:0,他引:10
在传统的建模方法中,规则三角网方法(GRID)由于是在格网点上对格网周围采样点按照距离远近加权平均,难以在细节上反映原貌,精度不高;不规则三角网方法(TN)按照某种原则(delaunay)将采样点直接民网,建立起模型,但是建模过程复杂,内存耗费很大,当原始采样数据量很大时,效率很低,引进四叉树分块生成标准delaunay网格,并采用凸壳边界跟踪优化合并形成三角网格,大大提高delaunay三角网生成速度,提高了建模效率。 相似文献
11.
12.
13.
针对包括曲线边界和内部带有曲线限定条件的二维Delaunay三角化问题,提出了一种细化算法.首先给出了曲线段的逼近边定义,以保证限定曲线在网格中的存在;然后证明了该算法的收敛性和最终曲线的逼近边集合与原曲线的拓扑一致性,并且生成的网格符合Delaunay优化准则;最后给出了算法的应用实例,验证了其有效性. 相似文献
14.
三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小。此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。 相似文献
15.
基于分治算法构建Delaunay三角网的研究 总被引:8,自引:0,他引:8
蒋红斐 《计算机工程与应用》2003,39(16):81-82,117
提出了一种构建Delaunay三角网的分治算法,该算法利用方格网管理离散点数据,仅需分别对每格中的点进行排序;此外,通过对凸包顶点数据进行分区管理,在搜寻凸包支撑线时,能预先确定出支撑点的范围,减少了搜索工作量,提高了三角网的合并速度。 相似文献
16.
一种基于格子分块的快速Delaunay三角剖分算法 总被引:2,自引:0,他引:2
介绍了一种基于分块格子构造的快速Delaunay平面剖分算法,先对点集以方格为单位分组,每组分别进行Delaunay三角网生成,再把分组构成的网格合并成一个整体。该算法易于理解和实现,占用内存少,运算速度快,具有近优的线性时间复杂度。最后给出的实例也证明了算法的可靠性和实用性。 相似文献
17.