TOOL PATH PLANNING USING VORONOI DIAGRAM AND THREE STACKS

Based on the object oriented data structure of Voronoi diagram, the algorithm of the trimmed offset generating and the optimal too l path planning of the pocket machining for multiply connected polygonal domains are studied. The intersection state transition rule is improved in this algorithm. The intersection is between the trimmed offsets and Voronoi polygon. On this basis, the trimmed offset generating and the optimal tool path planning are mad e with three stacks(I stack, C stack and P stack)in different monotonous pouches of Voronoi diagram. At the same time, a merging method of Voronoi diagram an d offsets generating for multiply connected polygonal domains is also presented. The above algorithms have been implemented in NC machining successfully, and the efficiency is fully verified.

Directional nearest neighbor query method for specified geographical direction space based on Voronoi diagram

The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward.This work studies two cases,i.e.the query point is static and the query point moves with a constant velocity.Under the static condition,the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor(pruning_SDNN algorithm)are proposed by combining the plane right-angle coordinate system with the north-west direction,and then according to the smallest external rectangle of Voronoi polygon,the specific query is made and the direction nearest neighbor query based on Voronoi rectangle(VR-DNN) algorithm is given.In the case of moving with a constant velocity,first of all,the combination of plane right angle coordinate system,geographical direction and circle are used,the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle(pruning_DDNN algorithm) are put forward.Then,according to the different position of motion trajectory and Voronoi diagram,a specific query through the nature of Voronoi diagram is given.At last,the direction nearest neighbor query based on Voronoi diagram and motion trajectory(VM-DNN) algorithm is put forward.The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space.

A new heuristics model of simulating pedestrian dynamics based on Voronoi diagram

A new heuristics model based on the Voronoi diagram is presented to simulate pedestrian dynamics with the noncrowded state, in which these mechanisms of preference demand evading and surpassing, microscopic anti-deadlock, and site-fine-tuning are considered. The preference demand describes the willingness determination of detouring or following other pedestrians. In the evading and surpassing mechanisms, in order to achieve a balance between avoiding conflicts and minimizing detour distances, a new pair of concepts: "allow-areas and denial-areas" are introduced to divide the feasible region for pedestrians detour behaviors, in which the direction and magnitude of detour velocity are determined.A microscopic anti-deadlock mechanism is inserted to avoid deadlock problem of the counter-directional pedestrian. A site-fine-tuning mechanism is introduced to describe the behavior of avoiding getting too close to the neighbors in pedestrian movement. The presented model is verified through multiple scenarios, including the uni-or bi-direction pedestrian flow in the corridor without obstacles, the uni-direction pedestrian flow in the corridor with obstacles, and the pedestrian evacuation from a room with single-exit. The simulation results show that the velocity–density relationship is consistent with empirical data. Some self-organizing phenomena, such as lanes formation and arching are observed in the simulation.When pedestrians detour an obstacle, the avoiding area before the obstacle and the unoccupied area after the obstacle can be observed. When pedestrians evacuate through a bottleneck without panic, the fan-shaped crowd can be found, which is consistent with the actual observation. It is also found that the behavior of following others in an orderly manner is more conducive to the improvement of the overall movement efficiency when the crowd moves in a limited space.

Effcient UAV-Based MEC Using GPU-Based PSO and Voronoi Diagrams

Mobile-Edge Computing(MEC)displaces cloud services as closely as possible to the end user.This enables the edge servers to execute the offloaded tasks that are requested by the users,which in turn decreases the energy consumption and the turnaround time delay.However,as a result of a hostile environment or in catastrophic zones with no network,it could be difficult to deploy such edge servers.Unmanned Aerial Vehicles(UAVs)can be employed in such scenarios.The edge servers mounted on these UAVs assist with task offloading.For the majority of IoT applications,the execution times of tasks are often crucial.Therefore,UAVs tend to have a limited energy supply.This study presents an approach to offload IoT user applications based on the usage of Voronoi diagrams to determine task delays and cluster IoT devices dynamically as a first step.Second,the UAV flies over each cluster to perform the offloading process.In addition,we propose a Graphics Processing Unit(GPU)-based parallelization of particle swarm optimization to balance the cluster sizes and identify the shortest path along these clusters while minimizing the UAV flying time and energy consumption.Some evaluation results are given to demonstrate the effectiveness of the presented offloading strategy.

A Study on Selecting the Shortest Routes by Voronoi Diagram in Route Networks of GIS

The problems of fast determining shortest paths through a polygonal subdivision planar with n vertices are considered in GIS. Distances are measured according to an Euclidean metric. A geographical information system (GIS) has a collection of nearest neighborhood operations and this collection serves as a useful toolbox for spatial analysis. These operations are undertaken through the Voronoi diagrams. This paper presents a novel algorithm that constructs a' shortest route set' with respect to a given source point and a target point by Voronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g., Djkstra algorithm, on selecting the shortest routes. Moreover, the novel algorithm can check the connectivity in a complex network between the source point and target one.

Modeling rock fragmentation by coupling Voronoi diagram and discretized virtual internal bond

The rock fragmentation involves the inter-block and the intra-block fracture.A simulation method for rock fragmentation is developed by coupling Voronoi diagram(VD)and discretized virtual internal bond(DVIB).The DVIB is a lattice model that consists of bonds.The VD is used to generate the potential block structure in the DVIB mesh.Each potential block may contain any number of bond cells.To characterize the inter-block fracture,a hyperelastic bond potential is employed for the bond cells that are cut by the VD edges.While to characterize the intra-block fracture,an elastobrittle bond potential is adopted for the bonds in a block.By this method,both the inter-block and intra-block fracture can be well simulated.The simulation results suggest that this method is a simple and efficient approach to rock fragmentation simulation with block smash.

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.

Finding Optimal Allocation of Constrained Cloud Capacity Using Hyperbolic Voronoi Diagrams on the Sphere

We consider a network of computer data centers on the earth surface delivering computing as a service to a big number of users. The problem is to assign users to data centers to minimize the total communication distance between compu-ting resources and their users in the face of capacity constrained datacenters. In this paper, we extend the classical pla-nar Voronoi Diagram to a hyperbolic Voronoi Diagram on the sphere. We show that a solution to the distance minimi-zation problem under capacity constraints is given by a hyperbolic spherical Voronoi Diagram of data centers. We also present numerical algorithms, computer implementation and results of simulations illustrating our solution. We note applicability of our solution to other important assignment problems, including the assignment of population to regional trauma centers, location of airbases, the distribution of the telecommunication centers for mobile telephones in global telephone companies, and others.

A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram

Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.

Path planning of the robot assembly based on Voronoi diagram

Based on the concepts of Voronoi diagram that describes geometry information of the robot assembly in C space, the position vector path parameter equation of the assembly movement between the step shaft and two-sided bearing bracket was given. And the path planning strategy of the component initiative assembly was put forward as well. Theoretical analysis proves that using the Voronoi diagram to do the geometry reasoning on the assembly space can evaluate the feasibility of the component assembly, and can present the reference position vector path of the component movement from the initial configuration to the objective configuration, therefore improves the flexibility of the robot initiative assembly.

Optimal Siting of Electric Vehicle Charging Stations Based on Voronoi Diagram and FAHP Method

The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combination with the actual situation of site selection of electric vehicle charging station, the comprehensive benefits index system is established. There are numerous factors influencing the site selection, among which there are uncertainty and fuzziness. The comprehensive evaluation method based on the fuzzy analysis and Analytical Hierarchy Process (AHP) is used to evaluate the comprehensive benefits in the site selection of electric vehicle charging stations, with the consultation of experts. This paper contributes to the best selection of comprehensive benefits and provides the reference for the decision-making of building the electric vehicle charging station. Actual examples show that the method proposed is effective.

An efficient algorithm for approximate Voronoi diagram construction on triangulated surfaces

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics.Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric.However,exact geodesic computation is time-consuming and has high memory usage,limiting wider application of geodesic Voronoi diagrams(GVDs).In order to overcome this issue,instead of using exact methods,we reformulate a graph method based on Steiner point insertion,as an effective way to obtain geodesic distances.Further,since a bisector comprises hyperbolic and line segments,we utilize Apollonius diagrams to encode complicated structures,enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples.Based on these strategies,we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces.We also suggest a measure for evaluating similarity of our results to the exact GVD.Although our GVD results are constructed using approximate geodesic distances,we can get GVD results similar to exact results by inserting Steiner points on triangle edges.Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.

A Voronoi diagram approach for detecting defects in 3D printed fiber-reinforced polymers from microscope images

Fiber-reinforced polymer(FRP)composites are increasingly popular due to their superior strength to weight ratio.In contrast to significant recent advances in automating the FRP manufacturing process via 3D printing,quality inspection and defect detection remain largely manual and inefficient.In this paper,we propose a new approach to automatically detect,from microscope images,one of the major defects in 3D printed FRP parts:fiber-deficient areas(or equivalently,resin-rich areas).From cross-sectional microscope images,we detect the locations and sizes of fibers,construct their Voronoi diagram,and employ-shape theory to determine fiber-deficient areas.Our Voronoi diagram and-shape construction algorithms are specialized to exploit typical characteristics of 3D printed FRP parts,giving significant efficiency gains.Our algorithms robustly handle real-world inputs containing hundreds of thousands of fiber cross-sections,whether in general or non-general position.

基于Voronoi图的空间点事件统计聚类方法

挖掘地理空间数据中点事件聚集模式对于揭示流行疾病、犯罪分布热点区域及城市基础设施空间分布格局等具有重要意义。针对不同形状、密度和大小的显著空间点聚集模式的识别,目前以空间扫描统计为代表的方法虽然可以对空间点聚类的显著性进行统计推断,减少虚假聚类结果,但其主要用于识别球形或椭圆形状的聚簇,对于沿着街道或河道分布的任意形状、不同密度的显著空间点聚簇识别还存在局限。因此,本研究提出一种基于Voronoi图的空间点聚集模式统计挖掘方法。首先,采用Voronoi图来度量空间点分布的聚集性,将空间点聚类问题转化为热点区域探测问题;其次,结合局部Gi*统计量探测统计上显著的空间点聚簇;最后,通过模拟数据和真实犯罪事件数据进行实验与对比分析。结果表明:本方法能够有效探测任意形状的空间点聚类,并对空间点簇的显著性进行统计判别,识别显著的空间点簇,减少随机噪声点的干扰;聚类识别结果优于现有代表性方法,如DBSCAN算法、空间扫描统计方法等。

改进骨架提取的Voronoi图导航中骨架重构算法研究

基于Voronoi图的路径规划算法在复杂环境导航过程中会因环境改变和Voronoi图结构的不变性,使全局路径规划器陷入最短路径搜索“陷阱”,导致导航失败。针对这一问题,提出一种改进骨架提取的Voronoi图导航骨架重构算法。对栅格地图进行预处理,生成全局初始骨架;结合激光雷达观测模型更新代价地图,通过改变代价地图的更新方式辅助骨架重构,实现机器人正确导航。对比实验结果表明,所提算法使骨架重构具有“记忆性”,在保证导航实时性的同时,提升了骨架算法的导航鲁棒性。

基于Voronoi图与条件随机场的自然场景文本检测方法

在自然场景中准确有效地检测文本是一项艰巨的任务,故提出一种基于条件随机场(CRF)框架的场景文本检测方法。通过利用贝叶斯推断估计文本极大值区域的置信度作为一元成本项,通过使用维诺图(Voronoi图)来构建CRF空间邻域信息,从而构建图模型,通过最大流算法最小化成本函数区分文本与非文本标记;利用字符的几何特性通过聚类方法聚合成行。实验结果表明,该算法比传统基于最大稳定极值区域(MSER)算法性能有所提高,自然场景文本检测正确率能达到87%。

基于加权Voronoi图的农村居民点用地适宜性评价及分区管控

随着经济社会的快速发展和城镇化的加快推进,农村人口向城镇集中,造成大量农村宅基地闲置或低效利用,加之宅基地布局散乱、基础设施配套不全,严重影响农村土地利用效率提升和人民生活水平的提高。本文以景泰县为例,在测算农村居民点整治潜力的基础上,应用加权Voronoi图进行农村建设用地适宜性评价和空间热点分析,探究农村居民点布局优化方向与发展的路径策略。结果表明,景泰县农村居民点整治潜力为876.16 hm2,整治潜力较大;农村建设用地适宜性整体较好,但各区域的差异较大,划分为适宜性好、较好、一般、较差、差5个等级;在此基础上将研究区划分为5种农村居民点发展模式区,并针对性地提出管控策略,为更好地开展国土空间规划编制、提高农村土地利用效率,助推乡村振兴提供参考和借鉴。

Connolly Surface on an Atomic Structure via Voronoi Diagram of Atoms

One of the most important geometric structures of a protein is the Connolly surface of protein since a Connolly surface plays an important role in protein folding, docking, interactions between proteins, amongst other things. This paper presents an algorithm for precisely and efficiently computing the Connolly surface of a protein using a proposed geometric construct called β-shape based on the Voronoi diagram of atoms in the protein. Given the Voronoi diagram of atoms based on the Euclidean distance from the atom surfaces, the proposed algorithm first computes a β-shape with an appropriate probe. Then, the Connolly surface is computed by employing the blending operation on the atomic complex of the protein by the given probe.

VGQ-Vor： extending virtual grid quadtree with Voronoi diagram for mobile k nearest neighbor queries over mobile objects

Performing mobile k nearest neighbor （MkNN） queries whilst also being mobile is a challenging problem. All the mobile objects issuing queries and/or being queried are mobile. The performance of this kind of query relies heav- ily on the maintenance of the current locations of the objects. The index used for mobile objects must support efficient up- date operations and efficient query handling. This study aims to improve the performance of the MkNN queries while re- ducing update costs. Our approach is based on an observa- tion that the frequency of one region changing between being occupied or not by mobile objects is much lower than the frequency of the position changes reported by the mobile ob- jects. We first propose an virtual grid quadtree with Voronoi diagram （VGQ-Vor）, which is a two-layer index structure that indexes regions occupied by mobile objects in a quadtree and builds a Voronoi diagram of the regions. Then we propose a moving k nearest neighbor （kNN） query algorithm on the VGQ-Vor and prove the correctness of the algorithm. The ex- perimental results show that the VGQ-Vor outperforms the existing techniques （Bx-tree, Bdual-tree） by one to three or- ders of magnitude in most cases.