线段加权的Voronoi图

本文将点上加权的Ｖｏｒｏｎｏｉ图推广到线段上加权的Ｖｏｒｏｎｏｉ图，证明了该图的两线段间的Ｖｏｒｏｎｏｉ边是二次曲线，给出了所有情形下两线段间的Ｖｏｒｏｎｏｉ边的具体形状和画法及线段加权的Ｖｏｒｏｎｏｉ图Ｖｎ的画法。     

Voronoi图算法及其在混合电路的衬底耦合研究中？…

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行２,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图。在 计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题。算法时间复杂度为Ｏ（ｎｌｏｇｎ）空间复杂度为Ｏ（ｎ）。     

Voronoi图算法及其在混合电路的衬底耦合研究中的应用

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行处理,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图．在计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题．算法时间复杂度为Ｏ（ｎｌｏｇｎ）,空间复杂度为Ｏ（ｎ）．     

面条目标Voronoi图生成的动态距离变换策略

利用Ｖｅｃｔｏｒ－ｂａｓｅｄ方法生成的矢量Ｖｏｒｏｎｏｉ图用于ＧＩＳ有局限性,那么自然而然就会想到能否在栅格空间中生成栅格Ｖｏｒｏｎｏｉ图,与之对应的生成算法被称作Ｒａｓｔｉｒ－ｂａｓｉｄ方法。本文首先介绍了与Ｒａｓｔｅｒ－ｂａｓｅｄ方法有关的研究工作,在此基础上提出用传统的距离变换建立栅格Ｖｏｒｏｎｏｉ图,而后又指出这种方法建立Ｖｏｕｏｎｏｉ图引起的误差与距离成线性正比关系,为减小误差,作者提出     

基于改进的Voronoi图划分的边界元衬底耦合参数提取技术

提出了一种快速而准确的数模混合集成电路衬底耦合参数提取方法。采用边界元法求解衬底耦合电阻,与有限差分法相比,计算速度提高了一个数量级以上,且可以保持精度,结合改进的Ｖｏｒｏｎｏｉ图来划分版图,生成的衬底ＲＣ网络数目远小于同样采用Ｖｏｒｏｎｏｉ图的文献「４」,而且解决了文献「４」中由于解析公式计算衬底电阻导致精度不高的问题。     

平面形状和布置的一种统一的定性表示方法

基于广义Ｖｏｒｏｎｏｉ图式，提出了Ｖｏｒｏｎｏｉ骨架边的跨度和势的概念，给出了保持连通性的层次骨架的建构算法。     

一种基于图的平面点集Delaunay三角剖分算法

本文提出了一种基于图的平面点集Ｄｅｌａｕｎａｙ三角剖分算法。该算法首先求出平面点集的欧几里得最小生成树，然后逐次加入一边构造三角形网格，最后按最小内角最大的三角化准则，通过局部变换，得到平面点集的Ｄｅｌａｕｎａｙ三角剖分。本文同时阐述了它的对偶图；平面点集的Ｖｏｒｏｎｏｉ图的概念和性质。     

面条模型中空间关系动态推断方法研究

首先提出了面条模型概念的基础上指出基于面条模型的图形处理系统不具备动态生成空间关系的能力,将会退化为单纯的地理数据库。为此提出了面条模型中动态推断空间关系的基于Ｖｏｒｏｎｏｉ图的四邻近数字模型（简记为：４ａｄ）,并给出了唯一、完备的推断规则同时给出了其优点和需改进之处。     

基于C~∞基函数的自然邻点插值(NNI)方法在科学计算可视化上的应用

插值方法及插值基函数的选择是可视化技术的一个关键问题。该文首先根据平面域上分布的数据点集,将平面域剖分为 Ｖｏｒｏｎｏｉ ｃｅｌｌｓ进而得到相应的 Ｄｅｌａｕｎａｒ三角化网格。然后基于 Ｖｏｒｏｎｏｉ ｃｅｌｌｓ的几何性质,应用自然邻点插值（ＮＮＩ）方法,介绍了一种具有无穷次连续可微的 Ｃ∞插值基函数及其数学性质。将基于 Ｃ”基函数的 ＮＮＩ方法用于把复杂数据场重构成一个具有规则网格的经验模型。最后再根据规则网格,生成三维立体图、等值线图、矢量分布图等。文章通过实例表明了基于Ｃ∞基函数的ＮＮＩ方法能够很好地应用于处理极不规则分布数据场的可视化。     

CATIA 2.5轴型腔铣削方法

型腔铣削(Pocketing)是2.5轴铣削加工的重要加工类型,它与平面铣削一样,主要用于直壁平面零件的加工,可以加工零件中大部分区域,已经可以应用于不同的加工阶段,包括粗加工、半精加工和精加工。1.加工操作设置对于如图1所示的直壁零件,可以用型腔铣削功能进行加工。本文以该零件为例,介绍型腔铣削的加工方法。     

Pocket extraction on proteins via the Voronoi diagram of spheres

Proteins consist of atoms. Given a protein, the automatic recognition of depressed regions, called pockets, on the surface of proteins is important for protein-ligand docking and facilitates fast development of new drugs. Recently, computational approaches have emerged for recognizing pockets from the geometrical point of view. Presented in this paper is a geometric method for the pocket recognition which is based on the Voronoi diagram for atoms. Given a Voronoi diagram, the proposed algorithm transforms the atomic structure to meshes which contain the information of the proximity among atoms, and then recognizes depressions on the surface of a protein using the meshes.     

Voronoi diagram-based tool path compensations for removing uncut material in 2½D pocket machining

This paper solves the problem of uncut areas, which can arise when 2½D pockets are machined with radial widths of cut greater than half the cutter diameter. Using the Voronoi diagram approach, three types of uncut areas are defined i.e., corner, centre and neck uncut regions. The corner uncut area is further subdivided into five different types, the centre uncut area into four and the neck uncut area into two. Techniques for detecting each type as well as algorithms for generating the tool paths for removing them are developed based on a singularity-free Voronoi diagram approach. These efficient and robust algorithms ensure that no uncut material is left behind even for complex-shaped pockets containing islands. The proposed algorithms even permit the radial width of cut to be increased to its limiting value of tool diameter. Three examples are included to illustrate the procedures for detection and removal of the different types of uncut areas.     

基于近似Voronoi图的移动机器人实时路径规划

运用Voronoi图理论及人工势场理论,研究了一种基于近似Voronoi图的移动机器人实时路径规划的方法,用来实现未知室内环境中移动机器人的自主导航。该方法朝向预先定义的目标点位置来探测室内环境,生成近似Voronoi图,同时利用人工势场法进行避障,生成一条能达到目标点的安全、光滑路径。仿真结果表明,该方法简单且易于实现,同时能够减少规划时间。     

分区加权Voronoi图的性质及其面积计算

分区加权Voronoi图是Voronoi图和加权Voronoi图的推广,可以用来模拟移动通信中基站发射天线分扇区以不同功率向周围发射时所覆盖区域的形状。首先,给出了分区加权Voronoi图的性质、定理及相关证明;其次,分析了分区加权Voronoi图中的各种区域,并给出了一种计算相应区域面积的算法;最后,利用分区加权Voronoi图模拟石家庄市部分城区中的基站建设情况,并对模拟产生的重复覆盖、服务区和盲区面积进行了计算。     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

Region-expansion for the Voronoi diagram of 3D spheres

Given a set of spheres in 3D, constructing its Voronoi diagram in Euclidean distance metric is not easy at all even though many mathematical properties of its structure are known. This Voronoi diagram has been known for many important applications from science and engineering. In this paper, we characterize the Voronoi diagram of spheres in three-dimensional Euclidean space, which is also known as an additively weighted Voronoi diagram, and propose an algorithm to construct the diagram. Starting with the ordinary Voronoi diagram of the centers of the spheres, the proposed region-expansion algorithm constructs the desired diagram by expanding the Voronoi region of each sphere, one after another. We also show that the whole Voronoi diagram of n spheres can be constructed in O(n³) time in the worst case.     

Recognition of docking sites on a protein using β-shape based on Voronoi diagram of atoms

A protein consists of atoms. Given a protein, the automatic recognition of depressed regions on the surface of the protein, often called docking sites or pockets, is important for the analysis of interaction between a protein and a ligand and facilitates fast development of new drugs.Presented in this paper is a geometric approach for the detection of docking sites using β-shape which is based on the Voronoi diagram for atoms in Euclidean distance metric. We first propose a geometric construct called a β-shape which represents the proximity among atoms on the surface of a protein. Then, using the β-shape, which takes the size differences among different atoms into account, we present an algorithm to extract the pockets for the possible docking site on the surface of a protein.     

加权Voronoi图的离散生成

加权Voronoi图是Voronoi图的一种扩展,有着广泛的应用.给出了一种新的构建加权Voronoi图的离散生成法.此方法无需复杂的计算,容易实现.