DISTANCE CHECKING ALGORITHMS

Automatic inspection of PC-boards is one example where distance checking algorithms are needed. The expansion-contraction algorithm due to Ejiri et al. [Computer Graphics Image Processing 2, 1973, 326-329; Elect. Eng. Japan 95, 1975, 90-97] indicates as errors not only widths that are too small but every case where the boundary has a radius of curvature less than half the critical distance d. The C-algorithm, the U-algorithm and the P-algorithm are three new algorithms presented in this paper. These algorithms only indicate an error if the width (= the perpendicular distance form one boundary point to another) is less than the critical distance d. All algorithms have several possible variations but in any case the P-algorithm is advantageous in both cost and speed. An algorithm due to Wójcik is also discussed. All five algorithms as well as a number of variations are compared to each other for different topologies. © 1979.