Because of the wide application of offset curves and the difficulty in directly incorporating such entities in geometric modeling systems, due to their potential analytic and algebraic complexity, a number of researchers have developed approximation algorithms for these types of geometries in terms of piecewise polynomial or rational polynomial functions. A literature survey on approximation of planar offset curves is compiled in [313,250]. A paper by Elber et al. [88] presented qualitative as well as quantitative comparisons for several plane offset curve approximation methods, namely the control polygon-based methods by Cobb [62], Tiller and Hanson [421], Coquillart [65], and Elber and Cohen [86], the interpolation methods by Klass [203], and Pham [312], the least square methods by Hoschek [174], the nonlinear optimization technique by Hoschek and Wissel [176], and the circle approximation method by Lee et al. [230]. They counted the number of control points of the approximated offset as a measure for efficiency, while the approximation error was within a prescribed tolerance. They found in general that the least square methods perform very well. However, when the progenitor curve is quadratic they showed that the simple method due to Tiller and Hanson [421], which translates each edge of the control polygon into the edge normal direction by an offset distance, outperforms the other methods. Therefore as an example we summarize the algorithm by Tiller and Hanson [421] with an illustration in Fig. 11.13:
Sederberg and Buehler [375] approximate an offset of a Bézier curve using Hermite interpolation of any even degree not less than the degree of the initial Bézier curve. The representation of the offset is a special interval Bézier curve of even degree with only the middle control point as a rectangular interval. The size of the rectangular interval indicates the tightness of the approximation.
Most of the existing offset approximation schemes generate the approximate offset curve in terms of Bézier /B-spline format in an iterative manner based on a subdivision technique to improve the accuracy of the offset curve. If local and global self-intersections exist, they must be eliminated after the approximation. Elber and Cohen [85] identify the local loops by using the fact that a pair of cusps always exist within the local self-intersection loop of the offset curve. The tangent vector of the offset flips its direction at the cusps, and thus , where is the tangent vector of the input curve, becomes negative at the regions bounded by the cusps. Consequently, the local loops can be identified by finding the zero set of . Once a local loop is identified the curve is split into three parts, the region before the first cusp, the region between the cusps and the region after the second cusp. The offset of the curve before the first cusp and the offset of the curve after the second cusp are intersected to find the self-intersection point. The region bounded by the parameters corresponding to the self-intersection point are trimmed off.
Lee et al. [230] eliminate the local and global self-intersections by approximating the input curve by discrete points and the connecting polygon. Then the offset curve is generated by offsetting these discrete points. The local redundant polygon edges can be detected by checking the dot product between the line segment and its corresponding offset line segment. If the dot product is negative, the offset segment is eliminated. The global self-intersections are detected by a plane sweep algorithm among the offset line segments. Once a valid boundary topology on the offset polygon is computed, the valid parameter intervals of the input curve are extracted. The intersection points of polygonal approximations may not provide accurate parameter values for the intersection points of the offset curve and hence they need to be refined using, for example Newton's method.
The method introduced by Kimmel and Bruckstein [201] generates offsets via wavefront propagation methods in fluid dynamics. The algorithm works on a square grid with a resolution chosen according to the desired accuracy. Finally the contour lines (offsets) are generated based on grid values. Gurbuz and Zeid [138] employ a different approach to avoid self-intersections. Instead of offsetting analytically, the offsetting process is carried out by filling the closed balls of radius for each point on the object. The union of the closed balls is subtracted from the object to construct the offset. An offset of a point in space is considered as a sphere. They simplified the implementation by assuming that the shape of a point is a cube and its offset is also a cube. First the object to be offset and its enclosing space are divided into small cubic cells. Therefore the accuracy is governed by the size of the cell. The cells that are on the object are referred to as boundary cells. The boundary cells separate the original set of cells into two subspaces, in and out of the object. Offset operation is carried out for each boundary cell. Chiang et al. [55] also compute offsets without self-intersections using a technique developed in image processing. First the domain is discretized into a two-dimensional grid and the progenitor curve is assigned to the nearest grid point. For each grid point, the distance to the discretized curve is evaluated. By extracting the grid points whose distances are equal to the offset distance, an offset without self-intersection can be constructed. This approach also obviously involves a trade-off between accuracy achieved and memory required.