Shortest Traversal Path of n Circles in Layered Manufacturing Applications

Layered manufacturing in rapid prototyping is to fabricate prototype by using a laser beam to trace the cross-sectional contours of a product layer by layer. Such cross-sections of geometrical objects differ by layers and generally have more than one continuous contour in each layer. In an attempt to facilitate an efficient approach for path planning, the problem is simplified by approximating each of the continuous contours with its minimum circumscribed circle. The tool path planning for traversing all the contours in the same cross-section can then be simplified as the path planning of circles. With combing the algorithm of traveling salesman problem (TSP) and the shortest traversal path function of three circles, an odd-even circle adjusting algorithm is proposed in this paper for deriving the shortest traversal path of n circles. When the traversing order of the n circles is obtained by the preprocessing TSP algorithm, the shortest traversal path of n circles can be derived in linear time. It is superior to that of the random selection method. Experiments are carried out for arbitrary n circles to demonstrate the computational advantage of the proposed method.