The optimal zigzag direction for filling a two-dimensional region

Many engineering and scientific problems require the filling of a two-dimensional region with scan lines of finite width. The number of contiguous scan 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 desirable to select a direction that minimizes this number. In this paper we provide a method for efficiently computing such an optimal direction when the region to be filled is bounded by straight-line segments and/or circular arcs. © 2001, MCB UP Limited