An algorithm for partitioning arbitrary simple polygons into a number of convex parts was presented. The concave vertices were determined first, and then they were moved by using the method connecting the concave vert...An algorithm for partitioning arbitrary simple polygons into a number of convex parts was presented. The concave vertices were determined first, and then they were moved by using the method connecting the concave vertices with the vertices of falling into its region B,so that the primary polygon could be partitioned into two subpolygons. Finally, this method was applied recursively to the subpolygons until all the concave vertices were removed. This algorithm partitions the polygon into O(l) convex parts, its time complexity is max(O(n),O(l 2)) multiplications, where n is the number of vertices of the polygon and l is the number of the concave vertices.展开更多
A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. I...A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.展开更多
In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties...In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.展开更多
文摘An algorithm for partitioning arbitrary simple polygons into a number of convex parts was presented. The concave vertices were determined first, and then they were moved by using the method connecting the concave vertices with the vertices of falling into its region B,so that the primary polygon could be partitioned into two subpolygons. Finally, this method was applied recursively to the subpolygons until all the concave vertices were removed. This algorithm partitions the polygon into O(l) convex parts, its time complexity is max(O(n),O(l 2)) multiplications, where n is the number of vertices of the polygon and l is the number of the concave vertices.
文摘A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.
文摘In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.
