共查询到20条相似文献,搜索用时 93 毫秒
1.
一种高效构建Delaunay三角网的算法 总被引:1,自引:0,他引:1
提出了一种基于改进的Graham扫描法的分块构建不规则三角网算法。采用分割合并的思想,先对平面上的离散点集区域进行分块,然后对各个子块用改进的Graham扫描法生成不规则三角网,再从边界边出发依次合并相邻的三角网子集,直到所有子集合并结束。本算法采用分块的思想缩小了构网时的搜索范围,对子块用改进的Graham法生成三角网提高了算法性能。实验结果表明,本算法使构网效率有很大的提高。 相似文献
2.
基于平衡二叉树的三角网快速生成算法 总被引:2,自引:2,他引:0
为了研究更好的三角网构建的方法,对不规则三角网构建算法进行了研究,提出了一种基于平衡二叉树的Delaunay三角网生成算法,采用分割合并的思想,提高了搜索效率,将离散点集进行划分,通过对各个所分小块子网的合并,完成所论区域的三角剖分。分析了该算法涉及的相邻子网公切线查找、凸壳生成等关键问题。通过具体实验和同其他经典算法效率的比较,该方法具有明显的优越性。 相似文献
3.
高效构建Delaunay三角网数字地形模型算法研究 总被引:38,自引:0,他引:38
在对传统构建Delaunay三角剖分(尤其是分割-合并)算法进行分析的基础上,采用自适应格网划分方法对点集进行排序、分割,并按照逆序合并Delaunay子三角网,然后进行约束处理,快速、高效地实现了Delaunay三角网的构建;对Delaunay子三角网合并、地性线处理、平三角形处理等关键问题进行了描述。实测结果表明,该算法的时间复杂度接近于O(n)。 相似文献
4.
TIN作为DEM的一种重要表达模型,其生成算法一直备受关注。首先对传统的生成算法原理进行总结,并针对其特点进行了分析,对利用凸壳建立TIN的原理和方法进行简单描述。由于许多计算几何学对点集进行限制以简化凸壳的建立过程,对凸壳的生成过程进行了改进。在点集的排序过程中剔除重复点,将点联入原凸壳过程中,排除共线这一特殊情况,建立新的凸壳,直至所有点都被包含在凸壳中。至此,三角网建立完毕。通过对三角形公共边进行LOP优化,使其满足Delau-nay三角网的特性。当所有三角形满足特性时,Delaunay三角网构建完毕。该算法的优势在于构网速度较快,并能够对重复点进行处理,同时在生成网的过程中对共线这种特殊情况进行处理。 相似文献
5.
Delaunay生成算法分类及研究 总被引:1,自引:0,他引:1
《科技信息》2008,(29)
本文介绍了Delaunay三角网的几种快速生成算法,从时间复杂度、健壮性、自动化程度等角度对其性能进行了分析和比较,并指出了改进的算法思想。 相似文献
6.
对Delaunay三角网的构建算法进行研究。提出了一种基于网格索引的构网算法。借助于该算法的特点提出了一种新的点-块-三角形映射机制定位点所在三角形的方法。简化了三角网的优化过程,提高了三角网构建速度。同时在Open-GL开放式三维环境下,进行光照渲染等处理,实现了地形的三维可视化。 相似文献
7.
文章基于逐点插入算法,引入虚拟网格技术将点和三角形重心规则化,优化了点、边和三角形的拓扑存储结构,实现了点、边和三角形的快速查找。并提出了一种快速的凸壳生成算法和二次优化方案。实验表明此算法获得的三角网生成效率明显提高。 相似文献
8.
基于Delaunay三角网的三维Voronoi单胞体积计算 总被引:1,自引:0,他引:1
根据Voronoi单胞的定义,在已知Voronoi单胞顶点的前提下,利用Delaunay三角网将Voronoi单胞划分成若干四面体,通过求解四面体的体积得到Voronoi单胞的体积,最后应用算例验证了该方法的可行性。 相似文献
9.
针对倾斜影像存在尺度变化大、匹配困难的问题,提出一种基于Delaunay三角网约束的倾斜影像匹配方法.首先检测影像上的最大稳定极值区域(Maximally Stable Extremal Regions, MSER)作为初始匹配点,然后利用这些初始匹配点构建Delaunay三角网,并以同名三角形、核线、灰度等作为约束条件,迭代匹配左、右影像上三角网内的尺度不变特征变换(Scale-Invariant Feature Transform, SIFT)特征点.试验表明:所提方法能获得可靠的匹配结果,匹配点分布均匀,具有较高的匹配正确率和匹配精度. 相似文献
10.
矿井动力现象预测的准确性和可靠性,从根本上说取决于对区域构造应力场和活动断块的研究水平,文中对Delaunay三角网剖分法进行了推广及必要的优化,通过在Visual Basic6.0平台上编程实现活动断块的自动识别,绘制出淮南矿区活动断块分布图,极大地减少了人工劳动量,取得了良好的效果. 相似文献
11.
带岛屿多边形Delaunay三角剖分算法 总被引:2,自引:1,他引:1
提出一种适用于任意多边形(含岛屿或不含岛屿)的统一Delaunay三角剖分算法.该算法首先将带岛屿多边形的所有顶点统一构建基于多边形边约束的Delaunay不规则三角网(CD-TIN);基于三角形顶点绕向,提出了多边形域外三角形的判定法则,剔除CD-TIN中的域外三角形,实现了带岛屿多边形的三角剖分.实验表明,该算法在含有大量岛屿的带岛屿多边形三角剖分中具有很高的时间效率和很强的鲁棒性,并成功将其应用到基于剖面的三维矿体建模与可视化系统中,解决了含有夹石或孔洞的矿体剖面多边形三角剖分问题,具有一定的实际应用价值. 相似文献
12.
欧氏Steiner最小树问题是组合优化中一个经典的NP难题,在许多实际问题中有着广泛的应用.由于使用普通智能算法求解较大规模问题时,极易陷入拓扑结构的局部最优,因此,基于Delaunay三角网技术并结合智能算法的有关思想,设计了一种改进的混合型智能求解方法,可大幅度提高算法在寻找更好拓扑结构上的有效性.算法在Matlab环境下编程实现,经大量STEINLIB中的标准数据实例测试和验证,获得了满意的效果,为求解较大规模的欧氏Steiner最小树问题提供了新的有效方法. 相似文献
13.
本文提出了后序插入算法用于绘制二叉树,并使所绘制的二叉树所占用面积达到最小。并给出该算法在C#中的实现及绘制效果。 相似文献
14.
针对传统二叉树在多分类问题上存在分类精度不够高和时间复杂度较高的不足,提出了一种基于二叉树结构双优化的SVM多分类学习算法。此算法利用遗传算法对已经提取的特征参数子集和核参数进行双重优化,以获得最优的主要特征参数,从而有效地解决了样本结构复杂、分布不平坦的多分类识别问题。作者运用UCI数据库中的数据,通过仿真实验,并就经度和时间复杂度与有向无环图法和一对一法作比较,结果表明本文提出的算法具有较好的优越性。 相似文献
15.
在数据结构课程的教学中,一般是通过遍历二叉树抽象地显示1棵二叉树结构,这样学生不容易理解.为此提出了在TC环境下实现的一种直观显示二叉树结构的算法,该算法可以帮助学生加深对二叉树的理解,且对于学生掌握二叉树的运用有极大帮助,同时也是对数据结构课程教学的改进与提高. 相似文献
16.
基于二叉树模型和遍历技术的配电网可靠性评估算法 总被引:2,自引:1,他引:2
提出了一种基于二叉树模型的配电网可靠性评估算法.根据配电网络中任一元件位于馈线或分支线这一特点,将整个网络的元件组合成馈线节点和分支线节点两种集合元件,从而将元件故障等效为相应的节点故障,实现对配电网络模型的简化,采用二叉树模型作为算法的数据结构,易于实现对整个网络节点的遍历及节点的搜索.该算法在可靠性评估过程中没有进行任何近似,计算结果是准确的. 相似文献
17.
针对射频识别(RFID)系统中,多个标签同时响应同一阅读器时产生的信息碰撞问题,提出基于帧分组与二进制搜索树识别的RFID防碰撞算法.该算法首先基于帧时隙ALOHA算法对标签进行识别,并依据碰撞时隙将未识别标签分成若干组,然后运用二进制搜索树算法依次对各组进行确定性识别,最后通过对算法进行性能分析及仿真比较,该算法在吞吐率和识别效率2方面较传统算法都有很大程度的优化,在L=N/2,且当N=100时,该算法的吞吐率较帧时隙ALOHA算法和二进制搜索树算法分别提高10%和34%;在L=N,且当N=100时,该算法的识别效率较帧时隙ALOHA算法和二进制搜索树算法分别提高12%和37%. 相似文献
18.
线索二叉树是“数据结构”课程中讨论的重要内容之一,在计算机领域中有着举足轻重的作用。对各种“数据结构”教材中的二又树线索化算法进行了大量的实验,发现很多教科书对二叉树的线索化算法在实现上存在错误.论文对这些错误进行了修正和实现,提高了“数据结构”课程在理论方面教学的严格性和实用性. 相似文献
19.
在分析二叉树的CreateBTree算法的基础上,利用线性探测再散列方法对CreateBTree算法的中序遍历序列进行预处理来改进CreateBTree算法,使得改进后的CreateBTree算法在最差情况下,时间复杂度由O(N^2)降为O(N)。 相似文献
20.
在深入分析二叉树数据结构的基础上,提出了用OOP法建立二叉树的过程.并用二叉树顺序存储的特性来实现VB下的可视化编程,解决了OOP法实现所碰到的若干问题. 相似文献