三维约束Voronoi剖分

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

二维限定Voronoi网格剖分细化算法

给出了限定点、限定线在Voronoi网格中存在的充要条件,提出了二维限定Voronoi网格细化算法,通过设置初始检测带,然后细分检测带来实现限定Voronoi网格的剖分;同时证明了该算法对于任意平面线段图输入限定条件的收敛性.对于生成的限定Voronoi网格,给出了尺寸控制和质量控制算法,并对其时间复杂度进行了分析.最后通过实例验证了文中算法的有效性.     

二维限定PEBI网格生成技术的研究

该文给出了二维限定PEBI网格的有关概念,对其生成技术进行了分析和研究,提出了一种简捷有效的生成算法-控制圆算法。最后给出了用于油藏数值模拟领域的PEBI网格例子,验证了该算法的正确性和有效性。     

三维限定Voronoi网格剖分细化算法

针对分段线性复合形约束条件下的三维限定Voronoi剖分问题,提出一种细化算法.首先证明了分段线性复合形中的元素在最终生成的三维限定Voronoi网格中可表示为Power图结构;受此启发,提出了对限定线段平面片分别进行一维二维Power图细化以实现三维限定Voronoi 网格生成的细化算法,并且证明了该算法对于任意分段线性复合形收敛.最后通过实例验证了文中算法的有效性.     

二维黎曼流形的Voronoi图生成算法

提出采用黎曼流形描述研究对象和基于坐标卡生成Voronoi图的算法思路.讨论了黎曼流形上研究Voronoi图的难点,并给出了存在定理,该定理说明了坐标卡上Voronoi图的存在条件.按照算法思路和存在定理,详细描述了二维黎曼流形上创建坐标卡的算法,并给出流形上转换函数和混合函数的定义方法.最后描述了基于坐标卡生成Voronoi图的算法,并给出了具体实例.     

分区加权Voronoi图的生成及其应用

分区加权Vorond图是Voronoi图和加权Voronoi图的推广，它可以用来模拟移动通信当中基站发射天线分扇区以不同功率向周围发射时所覆盖区域的形状。本文给出了分区加权Voronoi图的定义和它的离散生成算法．以及由此算法生成的分区加权Voronoi图的实例。     

交互式轮廓线骨架的提取

为精确抽取自由绘制的二维轮廓线骨架,提出了一种新的自适应骨架提取方法.将用户绘制的轮廓线,采用离散曲率约束,自适应调整步长,提取样点,进行最小二乘法实现样条曲线拟合,有效地突出了曲线形状特征;依据曲线模型的特征点,改进约束化三角剖分方法,高效地重建三角网格的拓扑结构;基于Voronoi图优化提取轮廓线骨架.实验结果表明了该算法的高效性和鲁棒性.     

Power图的离散生成

Power图是一种特殊的加权Voronoi图，该图中每个生成元点pi都带有权值wi．给出了一种直接构造Power图的算法．以每个生成元点Pi为圆心，Power距离,√wi为半径画圆；然后将这些圆以不同颜色填充，并以相同速率向外扩展这些圆的边界，直到屏幕上所有像素点都涂上颜色为止，环绕Pi的新边界构成Power图．该算法改进了在Voronoi图基础上构造Power图的传统方法，具有较高的效率．     

三维并行约束Delaunay网格生成算法及实现

针对二维并行约束Delaunay网格生成算法直接应用于三维条件下会导致人工边界产生过短边的问题,提出并实现了基于主从模式的三维并行约束Delaunay网格生成算法.首先对求解区域进行分解,通过交换人工边界面上的数据解决子区域间网格一致性问题;其次为每个人工边界面选定主从子区域,由主子区域产生边界面网格并发送,从子区域负责接收;最后采用贪心算法平衡各个子区域的通信负载,得到算法效率的提升.实验结果表明,该算法可以大规模并行生成边界一致四面体网格,具有较好的并行效率,并能够保证最终的网格质量.     

基于边折叠和质点-弹簧模型的网格简化优化算法

通过边折叠实现网格曲面简化，提出了保持曲面特征的边折叠基本规则，引入边折叠顺序控制因子λ，给出了折叠点坐标获取方法，简化过程中网格边长度趋于均匀．在曲面简化基础上，利用质点-弹簧模型优化网格形状．将网格顶点邻域参数化到二维域上，在质点-弹簧模型中引入约束弹簧，约束调整网格顶点，并逆映射到三维原始曲面上，局部优化网格顶点的相邻网格；调整曲面上所有网格顶点，在全局上优化网格形状．在曲面简化优化过程中，建立原始模型曲面和简化优化后曲面之间的双向映射关系；曲面的网格顶点始终在原始模型表面上滑动，并以双向Hausdorff距离衡量、控制曲面间的形状误差．应用实例表明：文中算法稳定、高效，适合于任意复杂的二维流形网格．     

Efficient Generation of Conforming Voronoi Polygonal Surface Mesh

A novel construction algorithm is presented to generate a conforming Voronoi mesh for any planar straight line graph (PSLG). It is also extended to tesselate multiple-intersected PSLGs. All the algorithms are guaranteed to converge. Examples are given to illustrate its efficiency.     

Guaranteed-quality anisotropic mesh generation for domains with curved boundaries

Anisotropic mesh generation is important for interpolation and numerical modeling. Recently, Labelle and Shewchuk proposed a two-dimensional guaranteed-quality anisotropic mesh generation algorithm called a Voronoi refinement algorithm. This algorithm treats only domains with straight lines as inputs. In many applications, however, input domains have many curves and the exact representation of curves is required for efficient numerical modeling. In this paper, we extend the Voronoi refinement algorithm and propose it as a guaranteed-quality anisotropic mesh generation algorithm for domains with curved boundaries. Some experimental results are also shown.     

Hexahedral Mesh Generation using the Embedded Voronoi Graph

This work presents a new approach for automatic hexahedral meshing, based on the embedded Voronoi graph. The embedded Voronoi graph contains the full symbolic information of the Voronoi diagram and the medial axis of the object, and a geometric approximation to the real geometry. The embedded Voronoi graph is used for decomposing the object, with the guiding principle that resulting sub-volumes are sweepable. Sub-volumes are meshed independently, and the resulting meshes are easily combined and smoothed to yield the final mesh. The approach presented here is general and automatic. It handles any volume, even if its medial axis is degenerate. The embedded Voronoi graph provides complete information regarding proximity and adjacency relationships between the entities of the volume. Hence, decomposition faces are determined unambiguously, without any further geometric computations. The sub-volumes computed by the algorithm are guaranteed to be well-defined and disjoint. The size of the decomposition is relatively small, since every sub-volume contains a different Voronoi face. Mesh quality seems high since the decomposition avoids generation of sharp angles, and sweep and other basic methods are used to mesh the sub-volumes.     

On the normal vector estimation for point cloud data from smooth surfaces

Reliable estimation of the normal vector at a discrete data point in a scanned cloud data set is essential to the correct implementation of modern CAD/CAM technologies when the continuous CAD model representation is not available. A new method based on fitted directional tangent vectors at the data point has been developed to determine its normal vector. A local Voronoi mesh, based on the 3D Voronoi diagram and the proposed mesh growing heuristic rules, is first created to identify the neighboring points that characterize the local geometry. These local Voronoi mesh neighbors are used to fit a group of quadric curves through which the directional tangent vectors are obtained. The normal vector is then determined by minimizing the variance of the dot products between a normal vector candidate and the associated directional tangent vectors. Implementation results from extensive simulated and practical point cloud data sets have demonstrated that the present method is robust and estimates normal vectors with reliable consistency in comparison with the existing plane fitting, quadric surface fitting, triangle-based area weighted average, and triangle-based angle weighted average methods.     

一种Voronoi划分减量构造算法

减量构造Voronoi划分(DCVT)是利用已有的Voronoi划分,局部重构删除节点后的Voronoi划分。详细分析删除一个节点对其他节点的Voronoi区域的影响,将DCVT的主要工作简化为求解一个简单的有界Voronoi划分;最后,提出一种有界Voronoi划分的求解策略,在此基础上给出DCVT的算法描述。理论分析与实验表明,算法平均时间复杂度为O(1)。     

Decentralized spatial partitioning algorithms for multi-vehicle systems based on the minimum control effort metric

We consider the problem of characterizing a spatial partition of the position space of a team of vehicles with linear time-varying kinematics. The generalized metric that determines the proximity relations between the vehicles and an arbitrary target point in the partition space is the minimum control effort required for each vehicle to reach the latter point with zero miss distance and exactly zero velocity at a prescribed final time. We show that the solution to the generalized Voronoi partitioning problem can be associated with a special class of spatial partitions known as affine diagrams. Because the combinatorial complexity of the affine diagrams is comparable to the one of the standard Voronoi diagrams, their computation does not pose a significant challenge in applications of multi-vehicle systems. Subsequently, we propose an algorithm for the computation of the spatial partition, which is decentralized in the sense that each vehicle can compute an approximation of its own cell independently from the other vehicles from the same team without utilizing a common spatial mesh. Numerical simulations that illustrate the theoretical developments are also presented.     

无线传感网络覆盖中概率Voronoi模型及算法研究

覆盖是无线传感网络中最重要的问题之一,随机覆盖是目前研究的主流。基于Voronoi图的随机覆盖算法是无线传感网络领域的研究热点。目前研究中采用的Voronoi图,主要采用基于距离的Voronoi边赋权值模型,存在两个主要问题,即模型粗糙和监测节点不全。以实测的分段概率传感模型为基础,从多传感协同监测的角度构造一种概率Voronoi模型,试图解决以上问题。并且用基于概率Voronoi模型的最大突破路径算法验证了模型有效性。就掌握的文献来看,该模型是首次提出,具有较好的实用推广价值。