$G^2/C^1$ Hermite interpolation of offset curves of parametric regular curves

1.   Introduction

Approximations of offset curves by polynomial or rational parametric curves are important tasks in the fields of CAGD (computer aided geometric design) and CAD/CAM. Many offset approximation methods have been developed in the last four decades. The offset approximation method by B-spline curves using the least square method has been presented ^[1,2]. A family of polynomial parametric curves, which is called the Pythagorean hodograph (PH) curve, has a rational offset ^[3] and it has many applications in CAGD and geometric modeling ^{[4,5,6,7,8,9,10]}.

Offset curves of regular plane curves can be represented by the convolution of the regular plane curves and a circular arc ^[11,12]. The convolution of a quadratic Bézier curve and a polynomial or rational curve is a rational curve. Based on these ideas, the offset approximation methods ^[11] yield rational approximation curves which are the convolution of the polynomial or rational curve and the quadratic Bézier curves interpolating the unit normal vector field of the polynomial or rational curve. The offset approximation methods by $G^2$ rational spline curves based on interpolating the unit normal vector fields by $G^2$ quadratic splines exist ^[13,14].

The notion of linear normal surfaces has been proposed to obtain their rational offsets ^[15,16]. Another advantage of linear normal surfaces is that the convolutions of linear normal surfaces and general rational surfaces are always rational ^[17,18], and many properties of linear normal surfaces and linear normal algebraic curves have been developed ^[19,20]. The offset approximation methods that yield rational offset using linear normal curves have been presented and analyzed ^{[21,22,23,24,25]}.

Recently, an offset approximation method of regular polynomial curves by $G^1$ polynomial curves based on approximating the normal vector fields of regular polynomial curves has been proposed ^[26]. In this paper we present the $G^2/C^1$ Hermite interpolation of offset curves of regular plane curves based on approximating the normal vector fields. In many applications, the $G^2/C^1$ interpolation is more important than the $G^2/G^1$ interpolation, since the latter may lead to poorly parameterized curves ^[27]. Our method is also capable of achieving circular precision ^[28,29] as it yields the exact offset curve whenever the input curve is a circular arc. Another advantage of our method is that if the regular polynomial curve is a polynomial curve of degree $n$, then it also yields a polynomial curve of degree $n+3$. We apply our offset approximation method to existing examples and illustrate that our method needs the minimum number of control points within the same tolerance.

The remainder of this paper is organized as follows. In Section 2, the preliminaries for the offset of regular plane curves and the convolution of two compatible parametric curves are introduced. In Section 3, our offset approximation method of regular plane curves is proposed and the advantages of our method are presented. We apply our method to existing examples and compare the numerical results to previous offset approximation methods in Section 4, and summarize our work in Section 5.

2.   Preliminaries

In this section we present the preliminaries and notions related to the offset curves and convolution curves of regular plane curves and their approximations ^[11,12,13]. For a regular plane curve ${{\bf x}}:[a, b]\to{{\mathbb R}}^2$,

are the unit tangent and normal vectors of ${{\bf x}}$ at the point ${{\bf x}}(t)$, respectively, where $R$ denotes the ninety degree clockwise rotation operator. The curve ${{\bf x}}+ r{{\bf N}}:[a, b]\to{{\mathbb R}}^2$ is called the offset curve of ${{\bf x}}$ with the offset distance $r\in{{\mathbb R}}$.

Two curves ${{\bf x}}_1$ and ${{\bf x}}_2$ are said to be compatible ^[12,30] if there exists a reparametrization $s = s(t)$ satisfying ${{\bf x}}_1'(t) \parallel {{\bf x}}_2'(s(t))$ and $\langle {{\bf x}}_1'(t), {{\bf x}}_2'(s(t)) \rangle > 0$. The convolution curve ${{\bf x}}_1 * {{\bf x}}_2$ for two compatible curves ${{\bf x}}_1$, ${{\bf x}}_2$ is defined by

The offset curve ${{\bf x}}+r{{\bf N}}$ of ${{\bf x}}$ with offset distance $r$ can be represented by ${{\bf x}}*r{{\bf N}}$, i.e.,

since two curves ${{\bf x}}$ and $r{{\bf N}}$ are compatible ^[11,12].

The Hausdorff distance between two curves ${{\bf x}}_1:[a, b]\to{{\mathbb R}}^3$ and ${{\bf x}}_2:[c, d]\to{{\mathbb R}}^3$ is defined by

The Hausdorff distance between a circular arc and a general plane curve is easier to be obtained than that between two general plane curves ^{[11,31,32,33]}. For the unit normal vector ${{\bf N}}$ of a plane curve ${{\bf x}}$ and its approximant ${{\bf N}}^a$, the Hausdorff distance is invariant under convolution, i.e.,

if these curves are regular ^[13].

3.   $G^2$ Hermite interpolation of offset curve of regular plane curve

In this section, we present a $G^2/C^1$ Hermite interpolation of offset curves of regular parametric plane curves based on approximating the normal vector field. Let ${{\bf x}}:[0, 1]\to{{\mathbb R}}^2$ be a regular parametric plane curve. Let ${{\bf N}}:[0, 1]\to{{\mathbb R}}^2$ be the unit normal vector field of ${{\bf x}}$ as in (2.1). We propose its approximant ${{\bf N}}^a:[0, 1]\to{{\mathbb R}}^2$ by

where $\alpha:[0, 1]\to{{\mathbb R}}$ is a cubic polynomial defined by

and $B_i^n(t) = {n\choose i} t^i(1-t)^{n-i}$, $0\le i \le n$, are the Bernstein polynomials of degree $n$. The reason why ${{\bf N}}^a$ is chosen as in Eq (3.1) is that if the derivatives of ${{\bf N}}^a$ and ${{\bf x}}$ for the same parameter are parallel, then their convolution can be directly obtained by their simple addition. This method was originally presented by Ahn and Hoffmann ^[21], and Kim et al. ^[26] used a similar equation to Eq (3.1), which is a special case of our method. In this paper, the coefficients $\alpha_0, \alpha_1, \alpha_2, \alpha_3$ in Eq (3.1) are determined such that ${{\bf N}}^a$ is a $G^2$ Hermite interpolation of ${{\bf N}}$. Accordingly, we show that the approximation ${{\bf x}}*r{{\bf N}}^a$ is a $G^2$ Hermite interpolation of the offset curve ${{\bf x}}*r{{\bf N}}$ with the offset distance $r\in{{\mathbb R}}$.

Since ${{\bf N}}^a(0) = {{\bf N}}(0)$ in (3.1), the curve ${{\bf N}}^a$ is a $G^0$ Hermite interpolation of ${{\bf N}}$ if ${{\bf N}}^a(1) = {{\bf N}}(1)$ holds. It follows from ${{\bf N}}^a(1) = {{\bf N}}(1)$ that

This is a linear equation with respect to $\alpha_1$ and $\alpha_2$, i.e., (3.2) can be represented by

where

and ${\bf v}$ denotes the right side of (3.2). The linear equation in (3.2) for $\alpha_1$ and $\alpha_2$ has a unique solution,

if ${{\bf x}}$ is convex and the length of the curve ${{\bf N}}:[0, 1]\to\ S^1$ is less than $\pi$, where $(x_1, y_1)\times(x_2, y_2) = x_1y_2-x_2y_1$, and $S^1$ is the unit circle centered at the origin in ${{\mathbb R}}^2$.

Proposition 3.1. If ${{\bf x}}$ is convex and the length of the curve ${{\bf N}}$ is less than $\pi$, then the linear equation in (3.2) for $\alpha_1$ and $\alpha_2$ has a unique solution as in (3.4).

Proof. For convenience, the notation $\arg {{\bf u}}$ for a vector ${{\bf u}} = (u_1, u_2)$ is used to the argument of the complex number $u_1 + {\rm i} u_2$, i.e., $\arg {{\bf u}} = \arg (u_1 + {\rm i} u_2)$. We may assume that ${{\bf x}}$ is turning left and $\arg {{\bf x}}'(0) = 0$, then $\arg {{\bf x}}'(t)$ is increasing and $\arg {{\bf x}}'(t) \in [0, \pi)$. Since

we have

and ${\bf v}_1$ and ${\bf v}_2$ are linearly independent. Thus, the assertion follows. □

From now on we assume that the regular parametric curve ${{\bf x}}$ satisfies the assumption of Proposition 3.1. If not, we can make ${{\bf x}}$ satisfy the assumption by subdivisions at inflection points and bisections of ${{\bf x}}$. The approximation curve ${{\bf N}}^a$ with $\alpha_1, \alpha_2$ satisfying (3.4) is a $G^0$ Hermite interpolation of ${{\bf N}}$. Now, we find the two coefficients $\alpha_0, \alpha_3$ such that ${{\bf N}}^a$ is a $G^2$ Hermite interpolation of ${{\bf N}}$. Let $\kappa_{{\bf x}}(t)$ be the signed curvature of ${{\bf x}}$ at the point ${{\bf x}}(t)$.

Proposition 3.2. The two curves ${{\bf N}}^a$ and ${{\bf N}}$ have the same signed curvature at both endpoints if and only if $|\alpha_{3i}| = |\kappa_{{{\bf x}}}(i)|$, $i = 0, 1$.

Proof. It follows from (3.1) that

for $i = 0, 1$, where $\Delta \alpha_i = \alpha_{i+1}-\alpha_i$. Thus, we have

$i = 0, 1$, and

Hence $\kappa_{{{\bf N}}^a}(i) = \kappa_{{\bf N}}(i)$, $i = 0, 1$ if and only if $\kappa_{{\bf x}}(i) = \kappa_{{\bf N}}(i)|\alpha_{3i}|$. If ${{\bf x}}$ is turning left or right, then the signed curvature of ${{\bf N}}$ is one or negative one, respectively. Therefore, $\kappa_{{\bf x}}(i) = \kappa_{{\bf N}}(i)|\alpha_{3i}|$, $i = 0, 1$ is equivalent to $|\alpha_{3i}| = |\kappa_{{{\bf x}}}(i)|$. □

We have two choices of $\alpha_{3i} = \pm \kappa_{{{\bf x}}}(i)$, $i = 0, 1$. From (2.1) it follows that

Thus, if $\alpha_{3i} = -\kappa_{{{\bf x}}}(i)$, then

which implies that ${{\bf N}}^a$ has the opposite tangent direction of ${{\bf N}}$ at both endpoints. Hence, we choose $\alpha_{3i} = \kappa_{{{\bf x}}}(i)$, $i = 0, 1$ for the $G^2$ Hermite interpolation ${{\bf N}}^a$ of ${{\bf N}}$. The approximant ${{\bf N}}^a$ is constructed by $\alpha_1, \alpha_2$, satisfying (3.4) and by

Now, we show that the curve ${{\bf x}}+r{{\bf N}}^a$ is a $C^1$ and $G^2$ Hermite interpolation of the offset curve ${{\bf x}}+r{{\bf N}}$ as follows.

Proposition 3.3. The approximant ${{\bf x}}+r{{\bf N}}^a$ is a $C^1$ and $G^2$ Hermite interpolation of the offset curve ${{\bf x}}+r{{\bf N}}$.

Proof. Since ${{\bf N}}^a(i) = {{\bf N}}(i)$, $i = 0, 1$, we have $({{\bf x}}+r{{\bf N}}^a)(i) = ({{\bf x}}+r{{\bf N}})(i)$. It follows from (3.5), (3.7) and (3.8) that

Thus, we obtain

which implies that ${{\bf x}}+r{{\bf N}}^a$ is a $C^1$ Hermite interpolation of the offset curve ${{\bf x}}+r{{\bf N}}$.

Since the curve ${{\bf N}}$ is a circular arc, we have

$i = 0, 1$. It follows from (3.6)–(3.9) and (3.11) that

By (3.9) and (3.12), we obtain

$i = 0, 1$ and (3.10) implies that ${{\bf x}}+r{{{\bf N}}^a}$ is a $G^2$ Hermite interpolation of ${{\bf x}}+r{{\bf N}}$. □

3.1.   Circular precision

In this section we show that if the regular parametric curve ${{\bf x}}$ is a circular arc, then our approximation method yields the exact offset curve.

Let ${{\bf x}}$ be a circular arc represented by

where ${{\bf c}}_0 \in {{\mathbb R}}^2$, $\gamma > 0$ and $l\in(0, \pi)$ are the center, radius, and length of the circular arc, respectively. By (3.8), we have $\alpha_0 = \alpha_3 = 1/\gamma$. The unit normal vector ${{\bf N}}$ satisfies ${{\bf N}}(t) = \frac1\gamma({{\bf x}}(t) - {{\bf c}}_0)$ and (3.3) yields

It follows from the definition of ${\bf{v}}$ and (3.2) that

Thus we obtain

Hence $\alpha_1 = \alpha_2 = 1/\gamma$, and $\alpha(t) = 1/\gamma$ for all $t\in[0, 1]$. Equation (3.1) yields

for all $t\in[0, 1]$. Therefore, our method yields the exact offset curve for the circular arc ${{\bf x}}$.

3.2.   $G^2/C^1$ Hermite interpolation of offset curve of parametric polynomial curves

An advantage of our method is that if ${{\bf x}}$ is a regular polynomial curve, then our method yields a polynomial approximant for a $G^2/C^1$ Hermite interpolation of the offset of ${{\bf x}}$. Let ${{\bf x}}:[0, 1]\to{{\mathbb R}}^2$ be the parametric polynomial curve of degree $n$ represented in Bézier form

where ${{\bf b}}_j$, $j = 0, 1, \ldots, n$, are the control points of ${{\bf x}}$. From (3.1) it follows that

which is a polynomial curve of degree $n+3$ and $G^2/C^1$ Hermite interpolation of ${{\bf N}}$. Since $({{\bf N}}^a)'(t) \parallel {{\bf x}}'(t)$, $t\in[0, 1]$, the offset curve is obtained by

which is also a polynomial curve and its degree is $n+3$.

In the rest of this section, we obtain the cubic polynomial $\alpha(t)$ in the form of control points of ${{\bf x}}$. Note that (3.8) yields

Using three formulas ^[34,35]

we have

Equation (3.2) and the definition of ${\bf v}$ yield

Thus, the coefficients $\alpha_1$ and $\alpha_2$ are obtained from (3.4) in the form of control points ${{\bf b}}_j$ of ${{\bf x}}$.

4.   Numerical examples and comparison

In this section we describe our approximation method and apply it to examples in the literature. The numerical results of our method are compared to those of previous methods.

Our approximation method yields the curvature continuous polynomial spline curve of degree $n+3$ approximating the offset of the input curve when it is a polynomial spline curve of degree $n$. In our approximation method, the input curve ${{\bf x}}$ is first subdivided such that each subdivided segment becomes a convex polynomial segment. We use the divide-and-conquer method. If the Hausdorff distance between the offset approximant and the offset of the polynomial segment is larger than the tolerance, then the segment is subdivided into two segments. The offset curves are approximated separately as shown in Figure 1. This process is repeated until the error is less than the tolerance.

The Hausdorff distance between two curves ${{\bf x}}+r{{\bf N}}$ and ${{\bf x}}+r{{\bf N}}^a$ can be measured by (2.2), because ${{\bf x}}+r{{\bf N}} = {{\bf x}}*r{{\bf N}}$ and ${{\bf x}}+r{{\bf N}}^a = {{\bf x}}*r{{\bf N}}^a$. Since ${{\bf N}}$ is a circular arc and ${{\bf N}}^a$ is a polynomial parametric curve, it is easy to calculate $d_H({{\bf N}}, {{\bf N}}^a)$, which is an advantage of the offset approximation method based on approximating the unit normal vector field ^[11,13].

Subsequently, our offset approximation method is applied to three numerical examples. The first and second examples are the offset approximations of the cubic Bézier and B-spline curves as shown in Figures 1 and 2, respectively, which were originally presented by Lee et al. ^[11]. The numerical results obtained by the previous methods can be found in Tables 1 and 2, which have been presented in ^[11,13,26], except for the data of the 'CL' method in Table 2. In this paper, our results are added to the last columns of the tables and the data of the CL method in Table 2 is newly added. It can be observed that our approximation method yields the optimal approximation, except for the 'Lst' method with respect to the number of control points within the same tolerance. The Lst method was proposed by Lee et al. ^[11] and they explained that it is an extension of Hoschek and Wissel ^[2] while adapting the global error bounding technique of the method in ^[36].

The third example is an offset approximation of boundaries of the character 'S', and its left and right boundaries are composed of seven and six Bézier curves of degree three, respectively. This example was proposed by Kim et al. ^[26] and their numerical results are presented in the fifth column of Table 3. For the example, we have added all the data that we could obtain from the previous methods in Table 3. We have also added our numerical results to the last column of Table 3 for comparison with those of the previous methods. As shown in Figure 3, the approximation curve has self-intersections. In many practical applications of planar curve offsetting, the self-intersection loops need to be removed ^[37]. Actually, the self-intersections of our approximation curve are the intersections of two Bézier segments. Many methods for finding the intersection points of two parametric curves have been presented ^[38,39,40]. The trimmed curve of our approximant can be obtained by finding the intersection points and eliminating the intersection loops as shown in Figure 4.

For all examples, the curvatures of the offset curve and our approximant are plotted in Figures 1–3, and we can see the curvature continuity of our offset approximant.

5.   Conclusions

In this paper we presented the offset approximation method for regular plane parametric curves. Our method has a few advantages. It yields the $G^2$ and $C^1$ Hermite interpolation of the offset curve. The method achieves circular precision and yields a polynomial approximant for the offset curve whenever the input curve is a polynomial curve. Our method facilitates the calculation of the error since it is based on approximating the unit normal vector field. Our method also has the smallest error from almost all previous offset approximation methods, with respect to the number of control points within the same tolerance.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This study was supported by research funds from Chosun University, 2023 and by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2021R1F1A1045830).

Conflict of interest

The authors declare no conflict of interest.