An integer arithmetic path expansion algorithm
T. A. Weber, Daniel G. Schweikert · Design Automation Conference · 1974
Graphical display systems are often built around a minicomputer with limited word size, core, and instruction repertoire. Thus, plotting algorithms which do not need floating point software or hardware are particularly valuable. Since the usual (CRT) graphical display has limited resolution, the typical floating point evaluations of square roots and transcendental functions are often unnecessarily accurate.Extending the integer arithmetic functional plotting concepts, integer algorithms are presented for the calculation of Euclidean distance, plotting of lines perpendicular and parallel to a given line segment, and the calculations of the intersection of two (slant) lines, all to an accuracy of one screen unit. These algorithms are combined into an algorithm to plot the outline of a path expanded from a centerline of straight-line segments, with unrestricted orientations.The algorithms have been implemented on a PDP-8 minicomputer with a Tektronics 611 storage scope. They are routinely used to display integrated circuit mask descriptions.