The optimal zigzag direction for filling a two-dimensional region

Many engineering and scientific problems require the filling of a two-dimen sional region with scan lines of finite width. The number of contiguous sca n line segments required for the filling depends on the direction used for scanning. When the cost of the filling operation increases with the number of scan line segments, as is the case in numerically controlled machining, layered fabrication and computer graphics applications, then it is desirabl e to select a direction that minimizes this number. In this paper we provid e a method for efficiently computing such an optimal direction when the reg ion to be filled is bounded by straight-line segments and/or circular arcs.