Phan Thanh An
Geometric computing, shortest paths, the convex rope, convex hull algorithm, convex hull, robotics
The convex rope problem, posed by Peshkin and Sanderson in IEEE Journal of Robotics & Automation, 2, 1986 53–58, is to find the counterclockwise and clockwise convex ropes starting at the vertex a and ending at the vertex b of a simple polygon, where a is on the boundary of the convex hull of the polygon and b is visible from infinity (i.e., there exists a ray m beginning at b, which does not intersect P anywhere else). Computation of these convex ropes is required to plan reachable grasps of a simple polygon by a simple robot arm. In this paper, we present a linear-time algorithm for solving this problem without resorting to a linear-time triangulation algorithm and without resorting to a convex hull algorithm for the polygon. The counterclockwise (clockwise, respectively) convex rope consists of two polylines obtained in a basic incremental strategy described in convex hull algorithms for the polylines forming the polygon from a to b. The key idea is the use of Melkman’s lineartime convex algorithm for a polyline which loses its simplicity on the ray m, beginning at b and in the opposite direction to m (such polyline is constructed by vertices inside the last convex hull in the incremental strategy and being left or on m). Some advantages of the algorithm and numerical examples are presented.
Important Links:
Go Back
