局部网格狭长三角形的品质改善及实现

通过对传统三角剖分的讨论 ,提出了局部网格狭长三角形品质改善的方法 ,此方法通过对狭长三角形的删除和对新产生的顶点作算法的调整 ,有效地改善了狭长三角形 ,使三角网格具有良好的形态 .

一种新的求解最小权三角划分的免疫算法

提出了一种基于自适应免疫遗传算法的求解最小权三角划分(MWT)问题的方案,通过自适应地调整疫苗库的进化和有选择地注射疫苗,提高了新算法的收敛速度和全局搜索能力,结合具体的MWT问题,给出了疫苗更新与注射算子构造的具体方案。仿真实验表明,新算法能产生比免疫算法更好的划分效果,尤其适合大规模点集,有较大的实用价值。

基于PVM的最小权三角划分并行遗传算法研究

平面点集的三角划分在计算机图形学,三维可视化等领域具有广泛地应用,在许多应用中需要提供形状最优的三角划分。但该类问题推测属于NP完全问题。为了快速有效地求解最小权三角划分(MWT)问题,提出了一种基于PVM的并行遗传算法来近似获取全局最优解,并系统地测试算法中一些重要的并行控制参数,包括迁移代数和节点平均负载对算法性能的影响。实验结果表明,该方法简单,可靠,大大缩短了优化过程的时间,提高获取全局最优解的概率。

基于径向基函数的点云岛屿孔洞自动修复

研究了利用点云获得的模型的孔洞修复,针对目前主要通过人工修复带有岛屿面片的孔洞耗时较长的问题,提出了一种基于径向基函数(RBF)自动修复岛屿孔洞的方法。该方法首先利用最小权重三角化法修复模型主体上的孔洞,其次计算模型主体上孔洞与岛屿面片的相关性,利用模型主体上孔洞和与其相关岛屿面片周围点来计算径向基函数,最后将粗修复后细分的点调整到径向基函数描述的曲面上。实验表明,与其他方法相比,该方法能快速、准确地修复缺陷模型。

狭长三角网格优化方法的研究及实现

传统的三角划分不适合许多实际的应用 ,在复杂表面进行三角划分过程中 ,往往会出现局部狭长三角形。通过对传统优化方法的讨论 ,文中提出了局部网格狭长三角形优化的方法 。

周培德三角剖分不是最小权三角剖分

平面点集的 (欧几里德 )最小权三角剖分问题是计算几何和算法领域的一个长期悬而未决的公开问题 .周培德于文献 [1]中提出了一个新的平面点集三角剖分算法 ,并称该算法能够获得最小权三角剖分 .文中通过给出反例 ,证明了该三角剖分不是最小权三角剖分 ,因此 ,最小权三角剖分问题仍有待于进一步研究 .

平面上两个点集间距离的O(nlogn)算法

定理"平面上两个点集的距离所在边是Voronoi图的Delaunay三角剖分中一条边"是本文的核心,在该定理基础上,本文提出如何用Voronoi图的Delaunay三角剖分算法求平面上两个点集的距离,并分析其复杂性.

基于最优三角剖分的矿区GIS索引裁剪算法

矿区GIS中尺度较大的地物即"大型结点",如果不加处理地插入到CP树中,结点之间的重叠区域大大增加,导致查询效率降低。为此提出一种基于凸多边形最优三角剖分矿区GIS-CP索引树"大型结点"裁剪算法,算法保证裁剪后结点具有较好的几何形态以减少插入产生的重叠。实验分析表明,对"大型结点"通过裁剪预处理再插入要比不进行裁剪预处理,检索效率高很多。

基于最优三角剖分的矿区GIS索引裁剪算法

矿区GIS中尺度较大的地物即"大型结点",如果不加处理地插入到CP树中,结点之间的重叠区域大大增加,导致查询效率降低。为此提出一种基于凸多边形最优三角剖分矿区GIS-CP索引树"大型结点"裁剪算法,算法保证裁剪后结点具有较好的几何形态以减少插入产生的重叠。仿真实验对本文的裁剪算法进行性能分析。结果表明,本文的裁剪算法是可行的、高效的,其性能明显高于其它同类其它算法。

《周培德三角剖分不是最小权三角剖分》一文商榷——反例不成立

周培德三角剖分是否能得到最小权三角剖分 ,周培德在《周培德三角部分不是最小权三角剖分》一文撰写之前已有新的结论 ,本文还指出《周培德三角剖分不是最小权三角部分》

遗传算法与模拟退火算法在最小权三角剖分中的比较

针对平面点集的最小权三角剖分问题,在实测的基础上,首先得出遗传算法和模拟退火算法的优良参数,然后在优良参数的条件下进行运行效率上的比较,所得结论为在点集规模较大时,模拟退火算法明显优于遗传算法。所得结论对于采用这两种算法解决其他问题也具有借鉴意义。

基于蚁群算法的最小权三角剖分求解

计算机研究者大多采用不同的进化算法解决最小权三角剖分,但都存在收敛速度慢、且易于早熟的缺点。为此,通过分析原有蚁群模型的不足和蚁群算法求解最小权三角剖分存在的问题,提出采用改进的蚁群模型结合选择点集最大允许剖分的方法,为加快收敛和抵制早熟引入对角线调整机制形成新的融合算法。实验结果表明,该算法在收敛速度、收敛效果和计算时间上都优于现有算法。

最小权三角划分的进化算法

提出了一种解决平面点集最小权三角划分的新方法——最小权三角划分进化算法。针对平面点集最小权三角划分问题的特点，提出了新的交叉算子和变异算子，即多边形交叉算子与三角形变异算子。从而保证了经交叉与变异操作后得到的后代仍为合理的三角划分，加快了算法的收敛速度。研究了进化算法的几个主要参数（如：解群规模、交叉概率、变异概率及自适应系数）对算法性能及收敛性的影响，并给出了影响曲线。计算结果表明，新算法能得到比贪心算法更优的结果。