基于Delaunay三角剖分生成Voronoi图算法

针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。

无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法

为同时满足覆盖与节能应用需求,本文提出了无线传感器网络中一种最小刚性拓扑控制算法MRTc(Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation).该算法基于Voronoi覆盖机制,准确控制节点工作状态,实现活动节点对目标区域的完全覆盖.在此基础上,MRTc利用Delaunay三角剖分图的特点,构建出适用于无线传感器网络的最小刚性拓扑结构.该结构有效约束了网络平均节点度,且同时具有容错性、覆盖性和稀疏性.此外,MRTc引入节点功率控制策略,在维持网络完全覆盖的基础上最小化节点能耗.仿真结果进一步验证了本文提出的MRTc算法的有效性.

三维约束Voronoi剖分

分析了约束面(点、线段、凸多边形)在三维Voronoi网格存在的条件,提出一种构造三维约束Voronoi剖分的算法.该算法的基本思想是在限定线的球覆盖基础上,借助限定面的约束Regular三角化生成关于限定面对称分布的生长点.理论上,对任意的分段线性复合形约束,该算法可以生成满足此约束的Voronoi网格.最后,给出了实例验证以说明文中算法的有效性.

运用加权Voronoi图进行点集剖分的两种方法

在加权Voronoi图定义的基础上,提出了点集剖分的两种新方法:基于线的剖分法和基于角度的剖分法.运用新方法对点集进行加权Voronoi剖分,可以得到各点更加合理、有效的影响区域.

基于地球网格剖分的球体3D-Voronoi图生成

球体3D-Voronoi图是球面Voronoi图向球体空间扩展产生的,可用于空间目标管理与空间行为建模。在全球空间网格剖分与编码基础上,提出了一种基于地球网格剖分的球体3D-Voronoi图生成算法。首先针对生长元为点集和全要素两种情况,分别给出了球体3D-Voronoi图的定义;然后阐述了基于活动像素生长的球体3D-Voronoi图生成算法的原理和具体实现步骤;最后以雷达探测威胁源和火力打击威胁源为生长元生成球体3D-Voronoi图,并提取边界网格,用于减少飞行器路径规划搜索网格范围,验证了算法的有效性。

基于Voronoi图和三角剖分的闭合曲线重建

以Voronoi图和Delaunay三角剖分为基础,针对二维闭合曲线集的采样点集,提出一种曲线重建算法。该算法按给定采样密度对曲线集进行采样,从而用一条或多条线段准确地重建曲线集,将采样点密集程度的度量定义为点集的本地特征值度量,以此要求采样达到一定的密集程度。理论分析证明该算法的时间复杂度为O(nlogn)。

一种基于逐点插入Delaunay三角剖分生成Voronoi图的算法

采用改进的逐点插入算法生成Voronoi图。该算法在逐点插入的过程中生成凸壳,进而生成Delaunay三角剖分。在生成Voronoi图的实现过程中,通过遍历三角形的边顶点快速识别相关的三角形组,进而生成Voronoi图。试验结果表明,该算法能实现,成功生成Voronoi图。

基于三角剖分与质心原理的三维插值方法对比

本文针对空间三维体插值加密与成像问题,进行建模、求解和相关分析并给出两种解题方法及其优劣对比。

基于投影加权Voronoi图的GIS空间竞争分析模型研究

提出加权Voronoi图的一种新形式———投影加权Voronoi图,由此形成平面剖分中的空隙(竞争三角形)可用于GIS空间竞争分析模型。进而分析不同的剖分模型以及竞争三角形的特性和分布。最后提出这种空间分析方法的应用领域。

平面散点集Delaunay三角剖分的一种高效方法

以平面散点集逐点插入的Delaunay三角化的方法为基础,在三角化过程中采用一定策略,将其改进成为一种简单易行而高效的方法,能够适应包括多岛、多连通域等复杂情况的各种边界,能够生成贴体的三角网,网格能够保证符合Delaunay法则。

利用类Delaunay三角剖分实现Voronio图

1引言 计算几何在计算机辅助设计、计算机图形学(特别是三维图形生成技术)及机器人等领域是非常重要的.特别在近年来,受到了学术界的极大关注.Voronoi图是计算几何的一个重要分支.在气象、生态、空中交通管制、城市规划等领域都得到广泛应用.

基于Matlab三维数据点三角剖分方法研究

逆向工程中点云数据点三角划分处理,在散乱数据插值曲面构造、快速原型制造以及有限元分析等方面有着重要的应用。根据Delaunay三角划分理论及Lawson优化准则,借助于Matlab中用于点云处理模块快速实现了空间散乱数据点的直接三角划分,给出了数据点三角划分程序代码,并以某小客车车身外表面点云数据处理过程加以验证,给出其外形数据点Delaunay三角划分以及凸壳包络图,由此可以早期发现逆向设计过程中可能存在的问题,从而减少后期修改次数,极大缩短新产品的开发周期,提高了设计精度。

持续性三角剖分算法研究

详细介绍了Guy Blelloch 等人提出一种新的支持持续性三角剖分的表示和一个新的三维凸包算法，同时介绍了基于该表示的地形模拟算法的实现，并比较度量了其实际应用的性能。

Voromoi图和Delaunay三角剖分的计算及应用

论述了Ｖｏｒｏｎｏｉ图及其几何对偶Ｄｅｌａｕｎａｙ三角剖分的计算方法，重点探讨了Ｄｅｌａｕｎａｙ三角剖分的优化性质及其有限元网格自动生成过程中的应用，在此基础上提出了一种自动生成三角形有限元网格的新算法。

二维约束Voronoi网格构造及其尺寸、质量控制

给出二维约束Voronoi网格的有关概念,分析了约束线段在二维Voronoi网格存在的条件,提出了一种二维约束Voronoi网格构造算法;并对二维约束Voronoi网格的尺寸和质量控制进行了研究;最后给出了实例以说明算法的有效性.该算法计算快速,适应性广,在诸多领域具有广泛的应用前景.

基于结点逼近提取的平面点集Voronoi图构建算法

提出一种基于结点空间逼近、精确提取以及面向拓扑关系生成的2维平面点集的构建方法。主要给出了搜索矩形域及其剖分概念、Voronoi图的基本性质、矩形域与Voronoi图结点关系的定理及其证明、基于链队的矩形域剖分和结点逼近机制及结点提取策略、基于条带有序表的最近邻近发生元快速检索算法、矢量Voronoi图的拓扑关系建立算法等。经过算法分析和程序试验验证本文算法的时间复杂度为O(nlog2n),本方法可以扩展到平面任意发生元Voronoi图的构建,具有简洁、高精度、鲁棒性、高效、适合于海量数据等特点,并且具有较好的实用价值和应用前景。

基于区域Voronoi图的复杂形体的三维重建算法

针对目前由二维轮廓线重建三维实体的方法要求轮廓线间距小、形状相似,对轮廓分叉及孔洞的解决有诸多限制且计算量大费时等问题,提出了Delaunay三角剖分与体素重建的思想相融合的方法。首先将断层图像轮廓近似表示成平面多边形,并利用Voronoi图进行划分,然后对其进行三角剖分。最后通过最短路径把这些三角形连接到相邻断层轮廓线的顶点上,扩展成四面体,从而直接完成三维重建。试验结果表明,该方法能较好地解决轮廓的分叉、孔洞等问题,且减少了数据量。

基于Voronoi图的变电站选址方法

由于Voronoi图在规划选址中具有独特优势,充分利用V图的特性并结合变电站站址的选取原则来指导新建站址的选择。对V图的定义、性质及V图的对偶图Delaunay三角剖分进行了简单的介绍,对生成Delaunay三角剖分及V图的Lawson算法进行了详细的阐述。对于新建站址的选择,以现有变电站为基础,将V图应用于负荷均匀分布和非均匀分布两种情况并对负荷非均匀分布下新建站址选择的交替迭代方法进行了实例仿真。规划结果表明该选址方法能有效地解决新建变电站的位置选择问题。

无线传感器网络中的分布式平面t-支撑拓扑控制算法

在确保无线传感器网络连通的前提下,每个节点自适应地调整自己的发射功率,通过最小化节点的能耗和减少节点间的通信干扰,达到延长网络生存时间的目的.基于 Voronoi划分和局部Delaunay三角剖分,提出一种新的几何结构PSLDel图(planar symmetric local Delaunay triangulation)以及其分布式构造算法,为无线传感器网络建立连通、稀疏、平面、t-支撑的底层逻辑拓扑,每个节点将依据最远的逻辑邻居调整到最小发射功率.仿真实验表明,PSLDel图在逻辑邻居、最小发射功率和通信干扰等性能方面接近集中式构造的UDel图,而且PSLDel图的网络延迟稍微优于 UDel图;与分布式构造的AUDel图相比,PSLDel图的通信开销至少可以降低55%,从而有利于提高无线传感器网络的能量使用效率.

增量构造Voronoi区域的改进算法

将Voronoi区域的半平面公共交集转换为Voronoi顶点与半平面的位置关系,提出一种简单的裁剪规则实现Voronoi区域的增量构造;该算法可以有效地处理半直线Voronoi边与直线Voronoi边以及节点共线等特殊情况。理论分析与实验结果表明,该增量构造Voronoi区域的平均时间复杂度是近似线性的。