The crossing function and its application to zig-zag tool paths

✍ Scribed by S.E. Sarma

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 490 KB
• Volume: 31
• Category: Article
• ISSN: 0010-4485
• DOI: 10.1016/s0010-4485(99)00075-5

✦ Synopsis

In zig-zag paths, which are used to sweep planar areas in applications such as machining and surveillance, the number of switch-backs in the path is a major contributor to cutting time. We develop algorithms to pick the direction in which a zig-zag path on a polygon will have the minimum number of switch-backs. We introduce the concept of a crossing function of a two-dimensional contour, which is a measure of how many times a finely pitched set of parallel raster-lines at some angle intersects with the contour. We show that minimizing the crossingfunction minimizes the number of switch-backs. We then show that for polygons, the crossing-function is minimized at a finite set of orientations parallel to the edges of the polygon. We show that the problem of minimizing the crossing function can be reduced to minimizing the width of an equivalent convex polygon, and develop an algorithm that takes n logn time for an n-sided polygon. Finally, we discuss how these algorithms are useful in machining.