Computation of the tangent graph of polygonal obstacles by moving-line processing

摘要

The tangent graph is a powerful graphic data structure for the path-planning of a mobile robot among obstacles because it has fewer edges than the widely used visibility graph. This paper proposes an efficient algorithm for computing the tangent graph of a set of polygonal obstacles, The algorithm at first detects common tangents of obstacle boundaries by moving-line processing that cooperatively moves a straight segment on the boundaries, and then checks for intersections among detected tangents and the obstacles both by a sequential approach and a sweep-line technique. It is proved that the moving-line processing takes O(MN) and O([M+R]N) computation time in the best and worst cases, respectively, where N expresses the number of obstacle vertices, and M denotes the number of convex segment chains of the obstacle boundaries, and R is a parameter representing the complexity of the boundaries.