An approximation method for convolution curves of regular curves and ellipses

1.   Introduction

Minkowski sum has been used in various important geometric computations, for example, for collision detection between objects ^[1,2] and computing collision-free paths in robot motion planning ^[3,4,5]. The convolution curves of two plane curves are related to the Minkowski sum boundaries in the plane. The Minkowski sum boundaries of two plane objects is a subset of the convolution curves of the boundaries of the objects ^[1,6,7].

Convolution curves and surfaces have been studied extensively in the literature. The results for classical offsets on convolutions of algebraic curves have been generalized, and a closed formula expressing the convolution degree by means of the algebraic degree and genus of the curve, has been derived ^[6]. Additionally, the class of rational hypersurfaces which have the same convolution properties as hyperspheres has been identified, and their geometric and algebraic properties have been investigated ^[7]. The Hausdorff distance between two regular plane curves has been shown to be invariant under convolution with the same regular curve provided the curves have no cusp ^[8]. Convolution curves at endpoints are characterized with respect to the tangent and bending directions ^[9].

In general, the convolution curves of two polynomial or rational curves are neither polynomial nor rational curves. Thus, it is necessary to approximate the convolution curves of two polynomial or rational curves by polynomial or rational curves. The convolution curve of a quadratic curve and other polynomial curves is rational, and using this property, one of the two polynomial curves is approximated by a quadratic curve, and so their convolution curve can be approximated by the rational curve ^[1]. This property can be applied to offset approximation ^[10,11]. If two curves have the parallel derivative, then their convolution curve is obtained easily by their simple addition ^[12]. Using this property, the convolution of two curves is approximated by cubic curves after the two curves are approximated by two cubic curves with the parallel derivatives ^[12]. The linear normal surfaces have rational offsets ^[13,14]. The convolution surface of a linear normal surface and other rational surfaces is rational ^[15,16], and the same property holds for the curve case. Using this property, the approximation of convolution curves of ellipses and general polynomial curves can be presented based on the ellipse approximation by linear normal curves ^[17].

In this paper, we present an approximation method for the convolution curve of an ellipse and a regular trajectory curve. We obtain the sufficient condition for the existence of at least a $G^0$ approximant of the convolution curve using our method. In addition, we characterize the necessary and sufficient condition for the $G^0$ approximant to be a $G^2$ approximation of the convolution curve. Moreover, we show that the $G^2$ Hermite interpolation is also a $C^1$ interpolation of the convolution curve. In our method, if the trajectory curve is the polynomial curve, then so is our approximant. We apply our method to previous examples in the literature. We implement our method and previous methods, and compare and analyze their results.

The remainder of this paper is organized as follows: In Section 2, the known properties of the convolution of two compatible parametric curves are introduced. In Section 3, our approximation method for the convolution curves of trajectory curves and ellipses is presented. We apply our method to existing examples in Section 4 and summarize our work in Section 5.

2.   Preliminaries

In this section, we present the preliminaries and notions related to convolution curves of regular plane curves ^[1,8,10]. Let ${{\bf x}}_i:[a_i, b_i]\to{{\mathbb R}}^2$, $i = 1, 2$, be two regular plane curves. They are said to be compatible ^[1,9], if there exists a reparametrization $s = s(t)$ satisfying ${{\bf x}}_1'(t) \parallel {{\bf x}}_2'(s(t))$. The convolution curve ${{\bf x}}_1 * {{\bf x}}_2$ for two compatible curves ${{\bf x}}_1$, ${{\bf x}}_2$ is defined by

The reparameterized curve ${{\bf x}}_2(s(t))$ is denoted by ${\tilde {{\bf x}}}_2(t)$, i.e., ${\tilde {{\bf x}}}_2(t) = {{\bf x}}_2(s(t))$. Let $\kappa_{{\bf x}}(t)$ be the (signed) curvature of the plane curve ${{\bf x}}$ at the point ${{\bf x}}(t)$. The curvature of ${{\bf x}}_1 * \tilde{{\bf x}}_2$ is

where we choose the $+$ sign when ${{\bf x}}_1$ and $\tilde {{\bf x}}_2$ are parallel and the $-$ sign when they are anti-parallel ^[18]. Note that if either $\kappa_{{{\bf x}}_1}$ or $\kappa_{{\tilde{{\bf x}}_2}}$ is zero, then $\kappa_{{{\bf x}}_1*\tilde{{\bf x}}_2}$ is also zero. In general, the sign of the curvature of ${{\bf x}}_1$ is the same as that of $\tilde {{\bf x}}_2$. Note that

where, likewise, the $+$ sign holds when ${{\bf x}}_1$ and $\tilde {{\bf x}}_2$ are parallel, and the $-$ sign holds when they are anti-parallel.

The Hausdorff distance is invariant under convolution, i.e., for a regular plane curve ${{\bf x}}$,

if these curves are regular ^[8].

3.   $G^2$ Hermite interpolation of convolution curve of trajectory curve and ellipse

In this section, we present an approximation method for $G^2$ and $C^1$ Hermite interpolation of convolution curves of regular plane curves and ellipses.

Let ${{\bf x}}:[0, 1]\to{{\mathbb R}}^2$ be a regular parametric plane curve. Let ${{\bf e}}:{{\mathbb R}}\to{{\mathbb R}}^2$ be an ellipse centered at the origin whose long and short radii are $a$ and $b$. The region generated by moving the ellipse along the trajectory curve ${{\bf x}}$ is the Minkowski sum of ${{\bf x}}$ and ${{\bf e}}$, and its boundary can be obtained by the convolution curve of ${{\bf x}}$ and ${{\bf e}}$. The ellipse ${{\bf e}}$ has two sided curve segments which are compatible to ${{\bf x}}$, i.e., there are reparametrizations $s_+$ and $s_-$ such that

Let two curves ${{\bf e}}_+, {{\bf e}}_-:[0, 1]\to{{\mathbb R}}^2$ be defined by the reparameterization ${{\bf e}}_\pm(t) = {{\bf e}}(s_\pm(t))$. Two convolution curves of ${{\bf x}}$ and ${{\bf e}}$ are obtained by

In general, ${{\bf e}}_\pm$ cannot be expressed by rational curves even if ${{\bf x}}$ is a polynomial curve. Thus, approximations for ${{\bf e}}_\pm$ are needed. Let ${{\bf e}}_{\pm}^a:[0, 1]\to{{\mathbb R}}^2$ be our approximants for ${{\bf e}}_{\pm}$, respectively. Our approximants are proposed as in (3.1), so that ${{{\bf e}}_{\pm}^a}'(t)$ and ${{\bf x}}'(t)$ are parallel for $t\in[0, 1]$, and then their convolution can be directly obtained by their simple addition, i.e.,

This idea was originally presented in ^[12], and later used in ^[19,20]. We propose the approximants

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$. Note that since ${{\bf e}}_-$ is equal to $-{{\bf e}}_+$, we can obtain ${{\bf e}}_-^a$ by $-{{\bf e}}_+^a$. If ${{\bf e}}_+^a$ is a $G^2$ interpolation of ${{\bf e}}_+$, then ${{\bf e}}_-^a$ is also a $G^2$ interpolation of ${{\bf e}}_-$. Thus, from now on we describe the approximation method only for ${{\bf e}}_+^a$, since ${{\bf e}}_-^a$ can be obtained directly by $-{{\bf e}}_+^a$. In this paper, the coefficients $\alpha_0, \alpha_1, \alpha_2, \alpha_3$ in (3.1) are determined such that ${{\bf e}}_{+}^a$ is a $G^2$ Hermite interpolation of ${{\bf e}}_{+}$. Accordingly, we show that the approximation ${{\bf x}}*{{\bf e}}_{\pm}^a$ is a $G^2$ Hermite interpolation of the offset curve ${{\bf x}}*{{\bf e}}_{\pm}$, respectively.

Since ${{\bf e}}_{+}^a(0) = {{\bf e}}_{+}(0)$ in (3.1), the curve ${{\bf e}}_{+}^a$ is a $G^0$ Hermite interpolation of ${{\bf e}}_{+}$ if ${{\bf e}}_{+}^a(1) = {{\bf e}}_{+}(1)$ holds. The equation ${{\bf e}}_{+}^a(1) = {{\bf e}}_{+}(1)$ is equivalent to

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 its Gauss map has a length less than $\pi$, where $(x_1, y_1)\times(x_2, y_2) = x_1y_2-x_2y_1$.

From now on we assume that the regular parametric curve ${{\bf x}}$ satisfies the sufficient condition for the existence of the solution of (3.2) uniquely: ${{\bf x}}$ is convex and its Gauss map has a length less than $\pi$. If not, we can make ${{\bf x}}$ satisfy the sufficient condition by subdividing ${{\bf x}}$ at inflection points and repetitive bisections. Thus the curvature of ${{\bf x}}$ is of constant sign in the domain interior. The approximation curve ${{\bf e}}_{+}^a$ with $\alpha_1, \alpha_2$ satisfying (3.4) is a $G^0$ Hermite interpolation of ${{\bf e}}_{+}$. Now, we find the two coefficients $\alpha_0, \alpha_3$ such that ${{\bf e}}_{+}^a$ is a $G^2$ Hermite interpolation of ${{\bf e}}_{+}$.

Proposition 3.1. The two curves ${{\bf e}}_{+}^a$ and ${{\bf e}}_{+}$ have the same curvature at both endpoints if and only if $|\alpha_{3i}| = \kappa_{{{\bf x}}}(i)/\kappa_{{{\bf e}}_{+}}(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 e}}_{+}^a}(i) = \kappa_{{{\bf e}}_{+}}(i)$, $i = 0, 1$, if and only if $\kappa_{{\bf x}}(i) = \kappa_{{{\bf e}}_{+}}(i)|\alpha_{3i}|$, and the assertion follows. □

By the proposition above, we have two choices of $\alpha_{3i} = \kappa_{{{\bf x}}}(i)/\kappa_{{{\bf e}}_{+}}(i)$ or $-\kappa_{{{\bf x}}}(i)/\kappa_{{{\bf e}}_{+}}(i)$, $i = 0, 1$. Note that, in general, the sign of $\kappa_{{{\bf x}}}$ coincides with that of $\kappa_{{{\bf e}}_{+}}$. From (2.2) it follows that

where the $+$ sign holds if ${{\bf x}}$ is turning left and the $-$ sign holds if ${{\bf x}}$ is turning right. If ${{\bf x}}$ is turning left, then it is parallel to ${{\bf e}}_+$. We choose

so that

by (3.7). Reversely, if ${{\bf x}}$ is turning right, then it is antiparallel to ${{\bf e}}_+$. We choose

so that

by (3.7). With the choice of $\alpha_{3i}$ in (3.8) and (3.10), $i = 0, 1$, we show that the curve ${{\bf x}}*{{\bf e}}_{+}^a$ is a $G^2$ and $C^1$ Hermite interpolation of the offset curve ${{\bf x}}*{{\bf e}}_+$ as follows.

Proposition 3.2. The approximant ${{\bf x}}*{{\bf e}}_{+}^a$ is a $G^2$ and $C^1$ Hermite interpolation of ${{\bf x}}*{{\bf e}}_+$.

Proof. Since ${{\bf e}}_+^a$ is at least a $G^0$ interpolation of ${{\bf e}}_+$, we have ${{\bf e}}_{+}^a(i) = {{\bf e}}_+(i)$, $i = 0, 1$, and so, we obtain $({{\bf x}}*{{\bf e}}_{+}^a)(i) = ({{\bf x}}*{{\bf e}}_+)(i)$. It follows from (3.9) and (3.11) that

and that

which implies that ${{\bf x}}*{{\bf e}}_{+}^a$ is a $C^1$ Hermite interpolation of ${{\bf x}}*{{\bf e}}_+$.

It is sufficient to show that $\kappa_{{{\bf x}}*{{\bf e}}_+^a}(i) = \kappa_{{{\bf x}}*{{\bf e}}_+}(i)$ for $i = 0, 1$. In the case of $\kappa_{{\bf x}}(i) \neq 0$, by Proposition 3.1, (3.8) and (3.10), we have $\kappa_{{{\bf e}}_+^a}(i) = \kappa_{{{\bf e}}_+}(i)$. It follows from (2.1) that

In the case of $\kappa_{{\bf x}}(i) = 0$, even if $\kappa_{e_+^a}(i) \neq \kappa_{{{\bf e}}_+}(i)$, we have

by (2.1), since the curvature of the convolution curve is zero if at least one of the two curves is of curvature zero. Hence, the curvature of ${{\bf x}}*{{\bf e}}_+^a$ is equal to that of ${{\bf x}}*{{\bf e}}_+$ at both end points, and thus ${{\bf x}}*{{\bf e}}_+^a$ is the $G^2$ Hermite interpolation of ${{\bf x}}*{{\bf e}}_+$. □

The approximant ${{\bf e}}_-^a$ can be obtained by ${{\bf e}}_-^a = - {{\bf e}}_+^a$, and it is a $G^2$ and $C^1$ Hermite interpolation of ${{\bf e}}_-$ for the same reason as in Proposition 3.2.

If ${{\bf e}}$ is represented by

where $R_\theta$ is the rotation operator by the angle $\theta$ counterclockwise, then it is interesting that

whether ${{\bf x}}$ is turning left or right, since $\kappa_{{{\bf e}}}(s_+(i)) = \kappa_{{{\bf e}}_+}(i)$ as ${{\bf x}}$ is turning left, and $\kappa_{{{\bf e}}}(s_+(i)) = -\kappa_{{{\bf e}}_+}(i)$ as ${{\bf x}}$ is turning right.

If ${{\bf x}}$ is a regular polynomial curve, then our method yields a polynomial approximant of the convolution curve of ${{\bf x}}$ and ${{\bf e}}$, which is a main merit of our method. Let ${{\bf x}}:[0, 1]\to{{\mathbb R}}^2$ be the parametric polynomial curve of degree $n$ expressed in Bernstein-Bézier form as

where ${{\bf b}}_j$, $j = 0, 1, \ldots, n$, are the control points of ${{\bf x}}$. It follows from (3.1) that ${{\bf e}}_{+}^a$ is a polynomial curve of degree $n+3$, and so is ${{\bf x}}*{{\bf e}}_{+}^a$. Equation (3.2) and the definition of ${\bf v}$ yield

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

4.   Approximation method and numerical examples

In this section, we describe our approximation method and apply it to numerical examples in the literature.

Our approximation method yields a curvature continuous polynomial spline curve of degree $n+3$ approximating the convolution curve of the trajectory and ellipse when the trajectory is a polynomial curve of degree $n$. Our approximation method consists of a preprocess and a main process. In the preprocess, the trajectory curve ${{\bf x}}$ is subdivided properly, and in the main subprocess, each convolution curve for the subdivided segment is approximated.

In the preprocess, the trajectory curve ${{\bf x}}$ should be subdivided so that each subdivided segment becomes convex and the length of its Gauss map becomes less than $\pi$. If the Gauss map has a length larger than $\pi$, ${{\bf x}}$ is subdivided into $m$ pieces, where $m$ is the smallest number such that the Gauss map of the subdivided piece is of length less than $\pi$. Then the cubic polynomial $\alpha$ exists uniquely by (3.4), (3.8), and (3.10). The Hausdorff distance between two curves, ${{\bf x}}*{{\bf e}}_{\pm}$ and ${{\bf x}}*{{\bf e}}_{\pm}^a$ is measured by

from (2.3), if these curves are regular. Thus, ${{\bf x}}$ is subdivided at the point where ${{\bf x}}*{{\bf e}}_{\pm}$ has a cusp. Note that ${{\bf x}}*{{\bf e}}_{+}$ and ${{\bf x}}*{{\bf e}}_{-}$ can have cusps at different points in general. Thus, even for the same trajectory curve ${{\bf x}}$, the subdivision points for approximating ${{\bf x}}*{{\bf e}}_+$ and ${{\bf x}}*{{\bf e}}_-$ can be different. In the preprocess, ${{\bf x}}$ is first subdivided at the inflection points and the points where ${{\bf x}}*{{\bf e}}_+$ or ${{\bf x}}*{{\bf e}}_-$ has cusps, and then ${{\bf x}}$ is subdivided into a number of segments as small as possible if its Gauss map has a length larger than $\pi$.

In the main process, each convolution curve ${{\bf x}}*{{\bf e}}_{\pm}$ of the subdivided segment and corresponding ellipse segment is approximated by the approximant ${{\bf x}}*{{\bf e}}_{\pm}^a$ using the divide-and-conquer method. If the error is larger than the given tolerance, then the segment is subdivided into two segments, and then they are approximated separately. This process is repeated until the error is less than the tolerance.

We consider two numerical examples which were presented in previous works ^[17,21]. The first example is the convolution approximation of a cubic spline and an ellipse ^[17]. The trajectory curve is a cubic spline composed of five cubic Bézier curves and is $C^2$ continuous except for one cusp, as shown in Figure 1. The ellipse is parameterized by ${{\bf e}}(s) = R_{\pi/6}(\cos s, 0.3\sin s)^T$. The cubic spline is subdivided into five Bézier curves, and none of them has an inflection point. In order to use (4.1), we find the cusp of ${{\bf x}}*{{\bf e}}_{\pm}$. Since the cubic spline ${{\bf x}}$ is turning right, the convolution curve ${{\bf x}}*{{\bf e}}_-$ does not have a cusp, and ${{\bf x}}*{{\bf e}}_+$ has four cusps, where ${{\bf x}}$ is subdivided for approximating ${{\bf x}}*{{\bf e}}_+$, as shown in Figure 1. The lengths of the Gauss map of the former four Bézier curves are less than $\pi$, but that of the last Bézier curve is larger than $\pi$, and so a subdivision is needed for approximating ${{\bf x}}*{{\bf e}}_-$. Thus, in the preprocess, ${{\bf x}}$ is subdivided into nine and six segments for approximating ${{\bf x}}*{{\bf e}}_+$ and ${{\bf x}}*{{\bf e}}_-$, respectively. Our method yields the spline approximant of degree six, since the trajectory curve is a cubic spline. For $TOL = 10^{-1}$, the minimal numbers of segments of hexic polynomial curves approximating the convolution curves ${{\bf x}}*{{\bf e}}_+$ and ${{\bf x}}*{{\bf e}}_-$ with the error less than $TOL$ are nine and seven, respectively, as shown in Figure 1. We can see that the minimum numbers of segments of hexic approximants approximating ${{\bf x}}*{{\bf e}}_+$ are larger than those approximating ${{\bf x}}*{{\bf e}}_-$, since ${{\bf x}}*{{\bf e}}_+$ has a higher number of cusps than ${{\bf x}}*{{\bf e}}_-$. For each tolerance, the minimum number of segments of hexic approximants with the error less than the tolerance can be obtained as in Table 1. We implement the approximation method presented in ^[17] and add the results from the method in Table 1. With respect to the minimum number of segments of approximants, the method in ^[17] requires smaller numbers of segments than our method. However, our method yields a polynomial approximant, and its degree is six, whereas the method in ^[17] obtains a rational approximant whose degree is eleven.

The second example is the approximation of the convolution curve of a nonic Bézier curve and an ellipse ^[21,22]. Our method yields the curvature continuous polynomial curve of degree twelve approximating the convolution curve. The nonic Bézier curve ${{\bf x}}$ has one inflection point, and its convolution curves ${{\bf x}}*{{\bf e}}_+$ and ${{\bf x}}*{{\bf e}}_-$ have two and four cusps, respectively, as shown in Figure 2. The trajectory curve is subdivided at the inflection point and at the point where the convolution curve has cusp, and is also subdivided so that its Gauss map is of length less than $\pi$ in the preprocess. Thus, ${{\bf x}}$ is subdivided into six and seven segments for approximating ${{\bf x}}*{{\bf e}}_+$ and ${{\bf x}}*{{\bf e}}_-$, respectively. In the main process each subdivided segment is approximated and subdivided repeatedly until the error is less than the given tolerance. For each tolerance, the minimum number of segments of approximants with the error less than the tolerance is listed in Table 2. We implement the approximation method presented in ^[12] and obtain the results using the method. The minimum numbers of segments achieved by our method are much smaller than those obtained by the method in ^[12], as shown in Table 2. Moreover, our method yields $G^2$ Hermite interpolation, whereas the method in ^[12] obtains only $G^1$ Hermite interpolation. However, the degree of the approximation curve obtained by the method in ^[12] is three, which is smaller than that achieved by our method. The approximant is of degree twelve, since ${{\bf x}}$ in this example is of degree nine.

As shown in Figure 1, the approximant ${{\bf x}}*{{\bf e}}_+^a$ has two self-loops, and ${{\bf x}}*{{\bf e}}_-^a$ has one self-intersection point. The trimmed curve can be obtained by removing the self-loops and the redundant segments near the self-intersection point. In order to complete the construction of the font, three closures are needed. The closures are half ellipses or a smaller part of the ellipse, which are approximated by hexic polynomial curves. Applying the approximation method of circular arcs by hexic polynomial curves ^[23], we obtained the approximants with an error less than $2.683\times10^{-7}$, as shown in Figure 1(b). As shown in Figure 2, ${{\bf x}}+{{\bf e}}_+^a$ and ${{\bf x}}+{{\bf e}}_-^a$ have one and two self-loops, respectively. The construction of the font can be completed by trimming the loops and adding two closures. The closures are half ellipses and are approximated by polynomial curves of degree twelve. After the half ellipses are approximated by Bézier curves of degree eleven using the half ellipse approximation method ^[24,25], the approximant can be expressed in Bézier form of degree twelve by the degree elevation ^[26]. The error for approximating the half ellipse is $5.963\times10^{-6}$, as shown in Figure 2(b).

5.   Conclusions

In this paper, we presented the convolution approximation method for regular plane parametric curves and ellipses. Our method yields the $G^2$ and $C^1$ Hermite interpolation of the convolution curve, and yields a polynomial approximant for the convolution curve whenever the trajectory curve is a polynomial curve. We compared the numerical results of our method with those of previous methods, and analyzed the merits of our method. Compared with previous methods, the merits of our method are that the approximant is a $G^2$ and $C^1$ Hermite interpolation, and the degree of the approximant or the required number of segments of the approximant within error tolerances is small.

Acknowledgements

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). The author is very grateful to three anonymous reviewers for their valuable comments and constructive suggestions.

Conflict of interest

The author declares no conflict of interest.