Voronoi diagram is founded by using computational geometry based on originaldistribution of the waypoints, and then the elements from Voronoi diagram are metamorphosed by usingthe rule for airsppce partition, and the ...Voronoi diagram is founded by using computational geometry based on originaldistribution of the waypoints, and then the elements from Voronoi diagram are metamorphosed by usingthe rule for airsppce partition, and the controller's workload is accounted in each element that ismade up of Metamorphic Voronoi polygon. Then in accordance with the rule about balance ofcontroller's workload, Simulated Annealing algorithm (SA) is used to achieve the optimization ofcombination of those elements , and the new resolution has satisfied the restriction of two rulesfor airspace partition. Therefore, the boundaries of the aggregates of these elements are theoptimal borderlines of sectors. The result of actual airspace design example validates therationality of the sector optimization method presented in this paper.展开更多
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 min...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.展开更多
在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中, h, n 和s 分别是P的边界、边和凸顶点的数目...在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中, h, n 和s 分别是P的边界、边和凸顶点的数目; t 和r 分别是位于P的凸包上的顶点和边数同时。展开更多
文摘Voronoi diagram is founded by using computational geometry based on originaldistribution of the waypoints, and then the elements from Voronoi diagram are metamorphosed by usingthe rule for airsppce partition, and the controller's workload is accounted in each element that ismade up of Metamorphic Voronoi polygon. Then in accordance with the rule about balance ofcontroller's workload, Simulated Annealing algorithm (SA) is used to achieve the optimization ofcombination of those elements , and the new resolution has satisfied the restriction of two rulesfor airspace partition. Therefore, the boundaries of the aggregates of these elements are theoptimal borderlines of sectors. The result of actual airspace design example validates therationality of the sector optimization method presented in this paper.
基金Project supported by the National Nature Science Foundation of China (Nos. 60473103 and 60473127) and the Natural Science Foundation of Shandong Province (No. Y2005G03), China
文摘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.
文摘在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中, h, n 和s 分别是P的边界、边和凸顶点的数目; t 和r 分别是位于P的凸包上的顶点和边数同时。
