Numerical Fitting of Planar Photographic Images with Spherical Voronoi Diagrams

There are many phenomena that generate polygonal tessellations on surfaces of 3D objects. One interesting example is the jackfruit, a multiple fruit found in the tropics. A recent study found the best-fit spherical Voronoi diagram from a photo of jackfruit skin, but the optimization was relative to the radius of the sphere and the height of the spikes. In this study, we propose a method for adjusting the position of the center of the sphere in addition to these parameters. Experiments were conducted using both ideal and real data. However, convergence with real data has not been confirmed due to relaxation of the convergence condition.     

面向群组机器人自组装的Voronoi图边界求交细分路径规划方法

自组装是群组机器人实现各种目标配置的有效途径,群组路径规划是群组机器人自组装实现的关键问题所在.本文在CVT算法基础上提出了一种基于Voronoi图边界求交细分的VBIT算法.首先根据群组机器人成员位置绘制相应Voronoi图,然后利用匈牙利算法为机器人与目标地分配对应关系,通过将机器人与目标地连线和机器人所在单元的交点作为下一次机器人移动起始点,多次迭代后达到目标配置.实验结果证明在自组装的精度、耗时、适用性方面比现有算法更优.     

Segmenting dot patterns by voronoi diagram concavity

This correspondence defines a signed distance, called ``internal concavity,' on paths of the Voronoi diagram of a dot pattern. An algorithm using internal concavity to segment dot patterns is described. The segmentation algorithm produces subsets of the Dirichlet tessellation (Delaunay triangulation) of the dot pattern.     

A dimensionality paradigm for surface interrogations

We propose a paradigm for analyzing problems involving complex curved surfaces in a manner suitable for practical implementation. Rather than deriving closed-form expressions for certain surfaces and problems, we reformulate the problem in a higher-dimensional space with more variables but simpler equations, thus avoiding complex symbolic manipulation and numerically delicate operations. In particular, we consider the formation of offsets, spherical blends of fixed or variable radius, and Voronoi surfaces.     

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

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

A solution to the Path Planning problem using angle preprocessing

The Path Planning problem is a common topic for Robotics and Computational Geometry. Many important results have been found to this classic problem, some of them based on plane or space tessellation. The new approach we propose in this paper computes a partition of the plane called the Polar Diagram, using angle properties as criterion of construction. Compared to some other plane partitions as Voronoi Diagrams, this tessellation can be computed much more efficiently for different geometric objects.The polar diagram used as preprocessing can be applied to many geometric problems where the solution can be given by angle processing, such as Visibility or Path Planning problems.     

GIS中投影加权Voronoi图及竞争三角形生成算法研究

在GIS空间分析中，为了定位和分析空间区域中含权对象的竞争区域，提出了加权Voronoi图的新形式——投影加权Voronoi图，该图是从常规Voronoi图和一般加权Voronoi图的平面剖分模型出发，首先引入了能够产生空间竞争区域的空间投影剖分模型，然后由此形成空间中的三角形空隙，即竞争三角形，同时归纳了形成竞争三角形的3种加权方式，并分析了其生成算法和特性，计算机的模拟结果显示，将竞争三角形作为空间的竞争区域是可行的，最后论述了它在GIS空间分析中广泛的应用前景。     

Robust Computation of 3D Apollonius Diagrams

Apollonius diagrams, also known as additively weighted Voronoi diagrams, are an extension of Voronoi diagrams, where the weighted distance is defined by the Euclidean distance minus the weight. The bisectors of Apollonius diagrams have a hyperbolic form, which is fundamentally different from traditional Voronoi diagrams and power diagrams. Though robust solvers are available for computing 2D Apollonius diagrams, there is no practical approach for the 3D counterpart. In this paper, we systematically analyze the structural features of 3D Apollonius diagrams, and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D. Our algorithm consists of vertex location, edge tracing and face extraction, among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex. Finally, we use centroidal Voronoi tessellation (CVT) to discretize the curved bisectors with well-tessellated triangle meshes. We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments. We also demonstrate an application on computing centroidal Apollonius diagram.     

Active Learning with Local Models

In this contribution, we deal with active learning, which gives the learner the power to select training samples. We propose a novel query algorithm for local learning models, a class of learners that has not been considered in the context of active learning until now. Our query algorithm is based on the idea of selecting a query on the borderline of the actual classification. This is done by drawing on the geometrical properties of local models that typically induce a Voronoi tessellation on the input space, so that the Voronoi vertices of this tessellation offer themselves as prospective query points. The performance of the new query algorithm is tested on the two-spirals problem with promising results.     

Computing multidimensional Delaunay tessellations

We recall some properties of Voronoi and Delaunay tessellations in any numbers of dimensions. We then propose a solution to the following problem: Given the Delaunay tessellation of n d-dimensional data points X₁,…, X_n, the proble is to insert a new data point X and to update the tessellation accordingly. The solution proposed achieves minimum space-complexity.     

结合广义重心坐标与Voronoi 剖分的函数分片逼近

结合广义重心坐标理论,提出了一个新方法,以解决在平面区域上的函数逼近问题。 该方法通过构建基于广义重心坐标的最优分片函数来逼近目标函数。采用Voronoi 图来划分区域, 并提出一个度量逼近误差的能量函数。推导出该函数的导数后,采用一种高效的Voronoi 节点更 新方法来获得区域的最优剖分,并通过最优剖分构建最优分片函数。由于该方法对不连续函数具 有良好地逼近能力,因此将其应用在图像逼近问题中。分别在解析函数和彩色图像上对该方法进 行实验,均获得了很好的逼近效果。     

结合几何划分技术和最大期望值/最大边缘概率算法的彩色图像分割

本文针对基于区域和统计的彩色图像分割方法进行研究,提出了一种结合Voronoi划分技术、最大期望值(Expectation Maximization, EM)和最大边缘概率(Maximization of the Posterior Marginal, MPM)算法的彩色图像分割方法。首先利用Voronoi几何划分将图像域划分成不同的子区域,并假设每个子区域内的像素强度满足独立同一的概率分布,在此基础上建立彩色图像模型;利用上述模型,在贝叶斯理论架构下建模图像分割问题,然后结合EM/MPM算法进行图像分割。该方法将基于像素的MRF模型扩展到基于区域的MRF,并且能同时有效的获取模型参数估计和基于区域的彩色图像最优分割。采用本文算法,分别对真实彩色图像和合成彩色图像进行了分割实验,定性和定量的测试结果验证了本文方法的有效性、可靠性和准确性。     

Euclidean Voronoi diagram of 3D balls and its computation via tracing edges

Despite its important applications in various disciplines in science and engineering, the Euclidean Voronoi diagram for spheres, also known as an additively weighted Voronoi diagram, in 3D space has not been studied as much as it deserves. In this paper, we present an algorithm to compute the Euclidean Voronoi diagram for 3D spheres with different radii. The presented algorithm follows Voronoi edges one by one until the construction is completed in O(mn) time in the worst-case, where m is the number of edges in the Voronoi diagram and n is the number of spherical balls. As building blocks, we show that Voronoi edges are conics that can be precisely represented as rational quadratic Bézier curves. We also discuss how to conveniently represent and process Voronoi faces which are hyperboloids of two sheets.     

Two-Part Texture Mappings

Most published techniques for mapping two-dimensional texture patterns onto three-dimensional curved surfaces assume that either the texture pattern has been predistorted to compensate for the distortion of the mapping or the curved surfaces are represented parametrically. We address the problem of mapping undistorted planar textures onto arbitrarily represented surfaces. Our mapping technique is done in two parts. First the texture pattern is embedded in 3-space on an intermediate surface. Then the pattern is projected onto the target surface in a way that depends only on the geometry of the target object (not on its parameterization). Both steps have relatively low distortion, so the original texture need not be predistorted. We also discuss interactive techniques that make two-part mapping practical.     

Dual‐space ray casting for height field rendering

This paper presents a realistic ray casting model on a curved surface. Guided by the model, we derive an analytical solution for spherical surfaces and propose a mathematical model by solving one problem in two spaces. By using the solution, we introduce a novel framework for spherical height field rendering. We have successfully implemented a spherical height field rendering framework on the graphics processing unit and obtained real‐time rendering rates with screen error below 1 pixel. Copyright © 2013 John Wiley & Sons, Ltd.     

一种Voronoi划分减量构造算法

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

A list-processing approach to compute Voronoi diagrams and theEuclidean distance transform

We propose an efficient Voronoi transform algorithm for constructing Voronoi diagrams using segment lists of rows. A significant feature of the algorithm is that it takes segments rather than pixels as the basic units to represent and propagate the nearest neighbor information. The segment lists are dynamically updated as they are scanned. A distance map can then be easily computed from the segment list representation of the Voronoi diagram. Experimental results have demonstrated its high efficiency. Extension of the algorithm to higher dimensions is also discussed     

Centroidal Voronoi tessellation in universal covering space of manifold surfaces

The centroidal Voronoi tessellation (CVT) has found versatile applications in geometric modeling, computer graphics, and visualization, etc. In this paper, we first extend the concept of CVT from Euclidean space to spherical space and hyperbolic space, and then combine all of them into a unified framework - the CVT in universal covering space. The novel spherical and hyperbolic CVT energy functions are defined, and the relationship between minimizing the energy and the CVT is proved. We also show by our experimental results that both spherical and hyperbolic CVTs have the similar property as their Euclidean counterpart where the sites are uniformly distributed with respect to given density values. As an example of the application, we utilize the CVT in universal covering space to compute uniform partitions and high-quality remeshing results for genus-0, genus-1, and high-genus (genus > 1) surfaces.     

Dynamical geometry for multiscale dissipative particle dynamics

In this paper, we review the computational aspects of a multiscale dissipative particle dynamics model for complex fluid simulations based on the feature-rich geometry of the Voronoi tessellation. The geometrical features of the model are critical since the mesh is directly connected to the physics by the interpretation of the Voronoi volumes of the tessellation as coarse-grained fluid clusters. The Voronoi tessellation is maintained dynamically in time to model the fluid in the Lagrangian frame of reference, including imposition of periodic boundary conditions. Several algorithms to construct and maintain the periodic Voronoi tessellation are reviewed in two and three spatial dimensions and their parallel performance discussed. The insertion of polymers and colloidal particles in the fluctuating hydrodynamic solvent is described using surface boundaries.     

基于Voronoi图的棋盘格角点匹配算法

现有的角点检测方法多针对倾斜的平面投影情况,而对于投影在扭曲平面上的棋盘格则不能实现匹配。针对该问题,提出一种基于Voronoi图的匹配方法。实验结果证明,与一般方法相比,利用距离分类的方法能更快更好地实现角点匹配与几何矫正效果,且有易于存储、计算简便等优点。