动态Voronoi图的算法实现

文中讨论了一种动态生成Voronoi图的构造算法。该算法以Delaunay三角网和相应的Voronoi图的对偶关系为基础,利用3个额外生长点,动态实现Delaunay三角网,然后根据优化后的三角网生成最终的Voronoi图。     

一种基于Graham三角剖分生成Delaunay三角网的算法

目的提出一种基于Graham三角剖分生成Delaunay三角网的算法,加快Delaunay三角网的生成速度.方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网.结果通过500至10000个点的测试,表明这种基于Graham三角剖分生成Delaunay三角网的生成速度快于传统基于凸包生成Delaunay三角网的生成速度.结论采用可见点表的数据结构以及利用点、边、三角形的有序性的特点构建Delaunay三角网,是提高建网速度的关键.     

基于半边数据结构的逐点插入Delaunay三角剖分算法

目的 根据传统的三角剖分算法,提出一种基于半边数据结构的逐点插入Delaunay三角剖分算法,提高三角网的构网效率.方法 在逐点插入Delaunay三角剖分算法中引入半边数据结构,在半边数据结构基础上定义Dart三元组,并为Dart三元组定义一组拓扑和几何操作,实现基于半边数据结构的逐点插入Delaunay三角剖分算法.结果 结合随机生成数据,通过实验结果 比较,证明基于半边数据结构的逐点插入Delaunay三角剖分算法具有较好的执行效率,并且随着点个数的增多,这种优势越加明显.结论 半边数据结构及其拓扑和几何操作能够较好地适应Delaunay三角剖分,提高了构网效率.     

应用一级邻近点生成加权Voronoi图的思想

加权Voronoi图是普通Voronoi图的一种扩展形式,在Voronoi图中各Voronoi边是在2个互为一级邻近点的点之间形成的,基于该理论,给出了一种生成加权Voronoi图的思想:用Delaunay三角网先找出各点的一级邻近点,再按加权Voronoi图的性质计算出各点的Voronoi边的数据,最后根据数据画出加权Voronoi图.     

改进的构建约束Delaunay三角网的算法

当前构建约束Delaunay三角网的算法在影响域为凹多边形的情况下不是很稳定,甚至失效。在介绍了Delaunay三角网的相关的概念和算法基础上,重点研究了约束Delaunay三角网生成算法以及影响域为凹多边形的相关问题,提出基于对角线交换的改进算法。实验表明,该算法能够解决影响域为凹多边形等的各种特殊情况,程序稳定简单,易实现。     

基于Crust算法的虚拟人台重建

对三维人体扫描数据进行精简处理并依据关键点提取半身人台数据.利用Voronoi图和Delaunay三角剖分的性质,在Matlab的平台上实现了经典的Crust曲面重建算法并得到基于真实人体的三维个性化人台模型.本文的建模方法便捷、准确,为建立大量个性化人台模型奠定了基础.     

矢量化网格剖分算法在服装衣片图像中的应用

矢量化网格剖分是服装衣片图像的二维-三维转换和虚拟服装设计的基础工作之一.在传统的网格生成和剖分算法基础上,提出了一种适合于服装衣片图像的多边形网格剖分算法;重点论述了网格划分、质点的生成过程和三角网格连接算法.算法仿真结果表明,该算法具有边界清晰、失真度小、自适应强和自动化程度高等特点,适合于任意形状的服装衣片.     

移动点的反向最近邻查询

反向最近邻（RNN）查询是空间数据库查询的一个重要的问题。随着无线通讯的发展,时空数据库中反向最近邻查询问题越来越受到关注。本文基于Voronoi图的定义和性质,采用一种不同于Delaunay三角剖分的另外一种三角剖分进行研究,其优势在于对于某个特定点,包含它的三角形的数量较少,查询效率较高。     

二维多边形剖分算法分析

对二维多边形的剖分算法进行了分析 ,提出了一种用梯形来剖分非单调二维多边形的通用算法。算法包括 3部分 :初始化、梯形化和优化 (后处理 ) ,所处理的多边形可以包含孔 ,孔可以嵌套     

基于凸包切割的不规则三角网及其邻接关系的生成算法

不规则三角网（TIN）是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明：本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.