Improved perspective visibility ordering for object-order volume rendering

Finding a correct a priori back-to-front (BTF) visibility ordering for the perspective projection of the voxels of a rectangular volume poses interesting problems. The BTF ordering presented by Frieder et al. [6] and the permuted BTF presented by Westover [14] are correct for parallel projection but not for perspective projection [12]. Swan presented a constructive proof for the correctness of the perspective BTF (PBTF) ordering [12]. This was a significant improvement on the existing orderings. However, his proof assumes that voxel projections are not larger than a pixel, i.e. voxel projections do not overlap in screen space. Very often the voxel projections do overlap, e.g. with splatting algorithms. In these cases, the PBTF ordering results in highly visible and characteristic rendering artefacts. In this paper we analyse the PBTF and show why it yields these rendering artefacts. We then present an improved visibility ordering that remedies the artefacts. Our new ordering is as good as the PBTF, but it is also valid for cases where voxel projections are larger than a single pixel, i.e. when voxel projections overlap in screen space. We demonstrate why and how our ordering works at fundamental and implementation levels.     

移动点Voronoi图拓扑维护策略的研究

移动环境下基于Voronoi图的最近邻查询必须要解决随时间不断改变的移动点Voronoi图的拓扑结构的维护问题。通过一组离散的,有限的事件序列对其对偶图Delaunay图拓扑改变过程的模拟来实现对移动点Voronoi图拓扑结构的维护。把带有事件驱动机制的移动数据结构（Kinetic Data Structure,KDS）模型作为移动点的运动模型,给出了KDS模型对其对偶图Delaunay图拓扑结构改变维护的具体策略,并对移动环境下动态插入或删除移动点时Voronoi图的拓扑维护问题进行了研究。最后给出了移动环境下基于Voronoi图的近邻查询的数据库实现模型。     

广义Voronoi图求解多机器人运动规划

在拥挤环境中,由于障碍物的边界形状比较复杂,需要使用广义Voronoi图表示空间环境。且在多移动机器人的运动规划过程中,需要协调多个机器人的运动,必须得到Voronoi图通道的宽度。为此提出了一种计算拥挤障碍物环境中生成的广义Voronoi图及其通道宽度的算法。并在生成的Voronoi图上利用A*算法对多个机器人进行路径规划,并利用分布式方法协调多个机器人运动。对协调两个机器人运动的过程进行了仿真,仿真结果表明利用提出的算法生成的具有通道宽度信息的Voronoi图能够满足多移动机器人运动规划的需要。     

Solving continuous location–districting problems with Voronoi diagrams

Facility location problems are frequent in OR literature. In districting problems, on the other hand, the aim is to partition a territory into smaller units, called districts or zones, while an objective function is optimized and some constraints are satisfied, such as balance, contiguity, and compactness. Although many location and districting problems have been treated by assuming the region previously partitioned into a large number of elemental areas and further aggregating these units into districts with the aid of a mathematical programming model, continuous approximation, on the other hand, is based on the spatial density of demand, rather than on precise information on every elementary unit. Voronoi diagrams can be successfully used in association with continuous approximation models to solve location–districting problems, specially transportation and logistics applications. We discuss in the paper the context in which approximation algorithms can be used to solve this kind of problem.     

Farthest line segment Voronoi diagrams

The farthest line segment Voronoi diagram shows properties different from both the closest-segment Voronoi diagram and the farthest-point Voronoi diagram. Surprisingly, this structure did not receive attention in the computational geometry literature. We analyze its combinatorial and topological properties and outline an O(nlogn) time construction algorithm that is easy to implement. No restrictions are placed upon the n input line segments; they are allowed to touch or cross.     

A parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping

This paper presents a parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping. The binary tree splitting method is used to adaptively group the point set in the plane and construct sub‐Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in each group consumes the majority of time and that construction within one group does not affect that in other groups, the use of a parallel algorithm is suitable. After constructing the sub‐Voronoi diagrams, we extracted the boundary points of the four sides of each sub‐group and used to construct boundary site Voronoi diagrams. Finally, the sub‐Voronoi diagrams containing each boundary point are merged with the corresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experiments demonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function of the size of the point set, the number of processors, the average number of points in each block, and the number of boundary points. Copyright © 2013 John Wiley & Sons, Ltd.     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。     

Voronoi diagrams of polygons: A framework for shape representation

This paper describes an efficient shape representation framework for planar shapes using Voronoi skeletons.This paper makes the following significant contributions. First a new algorithm for the construction of the Voronoi diagram of a polygon with holes is described. The main features of this algorithm are its robustness in handling the standard degenerate cases (colinearity of more than two points; co-circularity of more than three points), and its ease of implementation. It also features a robust numerical scheme to compute non-linear parabolic edges that avoids having to solve equations of degree greater than two. The algorithm has been fully implemented and tested in a variety of test inputs.Second, the Voronoi diagram of a polygon is used to derive accurate and robust skeletons for planar shapes. The shape representation scheme using Voronoi skeletons possesses the important properties of connectivity as well as Euclidean metrics. Redundant skeletal edges are deleted in a pruning step which guarantees that connectivity of the skeleton will be preserved. The resultant representation is stable with respect to being invariant to perturbations along the boundary of the shape. A number of examples of shapes with and without holes are presented to demonstrate the features of this approach.     

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

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

3D hyperbolic Voronoi diagrams

Voronoi diagrams have useful applications in various fields and are one of the most fundamental concepts in computational geometry. Although Voronoi diagrams in the plane have been studied extensively, using different notions of sites and metrics, little is known for other geometric spaces. In this paper, we are interested in the Voronoi diagram of a set of sites in the 3D hyperbolic upper half-space. We first present some introductory results in 3D hyperbolic upper half-space and then give an incremental algorithm to construct Voronoi diagram. Finally, we consider five models of 3D hyperbolic manifolds that are equivalent under isometries. By these isometries we can transform the Voronoi diagram of each model to others.     

Voronoi diagrams with barriers and on polyhedra for minimal path planning

Two generalizations of the Voronoi diagram in two dimensions (E²) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.This material is based upon work supported by the National Science Foundation under grants ECS-8021504 and ECS-8351942. The second author is also supported in part by a Fulbright scholarship     

Data structures and algorithms to support interactive spatial analysis using dynamic Voronoi diagrams

To support the need for interactive spatial analysis, it is often necessary to rethink the data structures and algorithms underpinning applications. This paper describes the development of an interactive environment in which a number of different Voronoi models of space can be manipulated together in real time to: (1) study their behaviour; (2) select appropriate models for specific analysis tasks; and (3) to examine how choice of one model over another will affect the interpretation of data. The paper studies six specific Voronoi diagram variants: the Ordinary Voronoi Diagram, the Farthest-point Voronoi Diagram, the Order-k Voronoi Diagram, the Ordered Order-k Voronoi Diagram, the kth Nearest-point Voronoi Diagram and the Multiplicatively Weighted Voronoi Diagram, and develops algorithms and data structures to store, rebuild and query these variants. From this, a generalised Voronoi data structure is proposed, from which specific Voronoi variants can be reconstructed dynamically as required. Algorithms for diagram reconstruction and for querying neighbourhood (topology or adjacency relations) of generator points and Voronoi regions are presented. An application program, developed on these ideas, is used to generate example results as proof of concept. It may be downloaded from a supporting website.     

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations

The combinatorial complexities of (1) the Voronoi diagram of moving points in 2D and (2) the Voronoi diagram of lines in 3D, both under the Euclidean metric, continues to challenge geometers because of the open gap between the Ω(n²) lower bound and the O(n3+?) upper bound. Each of these two combinatorial problems has a closely related problem involving Minkowski sums: (1′) the complexity of a Minkowski sum of a planar disk with a set of lines in 3D and (2′) the complexity of a Minkowski sum of a sphere with a set of lines in 3D. These Minkowski sums can be considered “cross-sections” of the corresponding Voronoi diagrams. Of the four complexity problems mentioned, problems (1′) and (2′) have recently been shown to have a nearly tight bound: both complexities are O(n2+?) with lower bound Ω(n²).In this paper, we determine the combinatorial complexities of these four problems for some very simple input configurations. In particular, we study point configurations with just two degrees of freedom (DOFs), exploring both the Voronoi diagrams and the corresponding Minkowski sums. We consider the traditional versions of these problems to have 4 DOFs. We show that even for these simple configurations the combinatorial complexities have upper bounds of either O(n²) or O(n2+?) and lower bounds of Ω(n²).     

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.     

基于Voronoi多边形的移动目标跟踪算法

分析讨论了Voronoi多边形的特性以及在目标监测与跟踪中的应用,提出了一种基于Voronoi多边形的移动目标跟踪算法。仿真实验结果分析表明,算法的计算和通信开销小,有效地节省监测节点的能量消耗,提高移动目标的监测效能。     

一种平面点集Voronoi 图的细分算法

Voronoi 图是计算几何中的重要概念之一,在计算机图形学、计算几何、 计算机辅助几何设计、有限元网格划分、机器人轨迹控制、模式识别、气象学和地质学研究 中得到广泛应用。借助于四叉树和区间算术,提出了一种新的构造平面点集Voronoi 图的细 分算法, 并且和经典的增量算法、栅格扩张法进行了比较, 结果显示新细分算法更为有效。 最重要的是细分算法原理简单,很容易编程实现。     

Polygon offsetting using a Voronoi diagram and two stacks

The generation of the trimmed offset of a simple polygon is a conceptually simple but important and computationally non-trivial geometric problem for many applications. This article presents a linear time algorithm to compute a trimmed offset of a simple polygon consisting of arcs as well as line segments in a plane. Assuming that a Voronoi diagram of the polygon is available, the algorithm uses two stacks: T-stack and C-stack. The T-stack contains intersections between an offset and Voronoi edges, and the C-stack contains an offset chain which is a part of the trimmed offset. The contents of both stacks are pushed into and popped from the stacks in a synchronized fashion depending on the events that occur during the offsetting process.     

Randomized incremental construction of Delaunay and Voronoi diagrams

In this paper we give a new randomized incremental algorithm for the construction of planar Voronoi diagrams and Delaunay triangulations. The new algorithm is more on-line than earlier similar methods, takes expected timeO(ngn) and spaceO(n), and is eminently practical to implement. The analysis of the algorithm is also interesting in its own right and can serve as a model for many similar questions in both two and three dimensions. Finally we demonstrate how this approach for constructing Voronoi diagrams obviates the need for building a separate point-location structure for nearest-neighbor queries.Leonidas Guibas and Micha Sharir wish to acknowledge the generous support of the DEC Systems Research Center in Palo Alto, California, where some of this work was carried out. Donald Knuth has been supported by NSF Grant CCR-86-10181. Micha Sharir has been supported by NSF Grant CCR-89-01484, ONR Grant N00014-K-87-0129, the U.S.-Israeli Binational Science Foundation, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Higher-order Voronoi diagrams on triangulated surfaces

We study the complexity of higher-order Voronoi diagrams on triangulated surfaces under the geodesic distance, when the sites may be polygonal domains of constant complexity. More precisely, we show that on a surface defined by n triangles the sum of the combinatorial complexities of the order-j Voronoi diagrams of m sites, for j=1,…,k, is O(k²n²+k²m+knm), which is asymptotically tight in the worst case.     

基于Voronoi图的组最近邻查询

组最近邻查询由于涉及多个查询点,因此比传统的最近邻查询更为复杂.充分考虑查询点的分布特征以及它们构成的几何图形的性质和特点,给出组最近邻所应满足的条件及判断组最近邻的理论方法.提出基于Voronoi图的组最近邻查询的VGNN算法,可以精确求解查询点集的最近邻.对于查询点不共线的情况,该算法的查询方式是以一点为中心、向外扩张式的;对于查询点共线的情况,该算法给出搜索范围,限定了参与计算的数据点的个数.给出基于Voronoi图的VTree索引.实验结果表明,基于VTree索引的VGNN算法具有较好的性能,并且当查询点不共线时,其性能具有较高的稳定性.