TECHNIQUES FOR REDUCING PEN PLOTTING TIME

The amount of time used by a pen plotter in drawing a set of line segments depends on the order and directions in which the segments are drawn, and can generally be reduced by reordering and redirecting the segments. This paper presents practical techniques for reducing plotting time. A method is proposed in which a buffer of segments is maintained, and the criterion used in choosing a segment from the buffer to draw is that of closeness to the current pen position. By storing the segment endpoints in a quadtree data structure, it is possible to find the closest endpoint in an amount of time which is essentially independent of the buffer size. We give algorithms for inserting, deleting, and finding closest points in the quadtree. The performance of the plotting time reduction program in a sample of real-world applications is given. Test cases from data plotting, computer-aided design and VLSI design are used. © 1983 ACM.