Multi-degree reduction of disk Bézier curves with $G^{0}$- and $G^{1}$-continuity

Abstract

In this paper, we propose methods to find a $G^{k}$-multi-degree reduction of disk Bézier curves for $k=0,1$. The methods are based on degree reducing the center and radius curves using $G^{k}$-continuity and minimizing the corresponding errors. Some examples and comparisons are given to illustrate the efficiency and simplicity of the proposed methods. The examples show that by using our proposed methods, we get $G^{0}$-, and $G^{1}$-degree reductions, while having less errors than existing methods, which are without any continuity conditions.

1 Introduction and preliminaries

Lack of robustness is a fundamental issue in computer aided design and solid modeling. Taking disks in the plane as control points of Bézier curves is an appropriate approach toward solving this issue because it gives a Bézier curve with tolerance; see [1]. The degree reduction of curves is an important issue; in $G^{k}$-degree reduction, we approximate a disk Bézier curve of degree n by a disk Bézier curve of degree m, $m< n$, under the satisfaction of boundary conditions and minimum error requirement. The issue of degree reduction of Bézier curves has been tackled by many researchers; see [2–9]. Unlikely, degree reduction of disk Bézier curves has not been tackled by many researchers.

We end this section by addressing related preliminaries like defining the disk Bézier curves, the Gram matrix, and the delta operator.

Let $\mathbb{R}$ be the set of real numbers and $\mathbb{R}^{+}$ be the set of non-negative real numbers. A disk centered at $p=(x_{0},y_{0})\in\mathbb{R}^{2}$ with radius $r_{0}\in \mathbb{R}^{+}$ is given by

$$ (p):=(x_{0},y_{0})_{r_{0}}:=\bigl\{ (x,y) \in\mathbb {R}^{2}:(x-x_{0})^{2}+(y-y_{0})^{2} \leq r_{0}^{2}\bigr\} . $$

(1)

For any two disks $(p)=(x_{0},y_{0})_{r_{0}}$ and $(q)=(x_{1},y_{1})_{r_{1}}$, addition and scalar multiplication are defined as follows:

$$ \begin{aligned} &(p)+(q)=(x_{0}+x_{1},y_{0}+y_{1})_{(r_{0}+r_{1})}, \\ &s(p)=(sx_{0},sy_{0})_{|s|r_{0}}, \quad s\in \mathbb{R}, \end{aligned} $$

(2)

where $|s|$ is the absolute value of s.

For constants $s_{i}$ and disks $(x_{i},y_{i})_{r_{i}}$, the last definition can be generalized as

$$ \sum_{i=0}^{n}s_{i}(x_{i},y_{i})_{r_{i}}= \Biggl(\sum_{i=0}^{n}s_{i}x_{i}, \sum_{i=0}^{n}s_{i}y_{i} \Biggr)_{\sum_{i=0}^{n}|s_{i}|r_{i}}. $$

(3)

A disk Bézier curve is defined as follows.

Definition 1

(Disk Bézier curves)

A disk Bézier curve of degree n corresponding to $n+1$ disks $(p_{i})=(x_{i},y_{i})_{r_{i}}$, $i=0,1,\ldots,n$, is defined as follows:

$$ (P_{n}) (t):=\sum_{i=0}^{n}(p_{i})B_{i}^{n}(t), \quad 0\leq{t}\leq{1}, $$

(4)

where

$$ B^{n}_{i}(t) = {n \choose i}(1-t)^{n-i}t^{i} , \quad i=0,1,\ldots,n, $$

are the Bernstein polynomials of degree n.

See Figure 1 for an example of a cubic disk Bézier curve. For more on Bernstein polynomials and Bézier curves, see [10–12].

Figure 1

A cubic disk Bézier curve.

The disk Bézier curve $(P_{n})(t)$ can also be written as $(P_{n})(t):=(p(t))_{r(t)}$, where

$$ p(t):=\sum_{i=0}^{n}p_{i}B_{i}^{n}(t)= \sum_{i=0}^{n}(x_{i},y_{i})B_{i}^{n}(t) \quad \mbox{and} \quad r(t)=\sum_{i=0}^{n}r_{i}B_{i}^{n}(t) $$

(5)

are the center and the radius curves of $(P_{n})(t)$ with control points $p_{i}=(x_{i},y_{i})$, $i=0,1,\ldots,n$, and $r_{i}$, $i=0,1,\ldots ,n$, respectively.

The Gram matrix $G_{m,n}$ is the $(m + 1) \times(n + 1)$-matrix, whose elements are

$$ g_{ij} = \int_{0}^{1} B^{m}_{i}(t) B^{n}_{j}(t) \, dt = \frac{{m \choose i}{n \choose j}}{(m+n+1) {m+n \choose i+j}} , \quad i=0,\ldots,m, j=0, \ldots, n. $$

For $n=m$, the matrix $G_{m,m}$ is real, symmetric, and positive definite [13].

In the sections on $G^{0}$-, and $G^{1}$-continuity, the submatrices of the Gram matrix $G_{m,n}$ are defined. Each section uses the same notation for these submatrices, but with different dimensions. It should be clear that the form used within a section is the one defined within that section.

The delta operator Δ on the disks $(p_{i})$ is defined as follows: $\Delta^{0} (p_{i}) = (p_{i})$, $\Delta^{k} (p_{i}) = \Delta^{k-1}(p_{i+1}) - \Delta^{k-1}(p_{i})$, $k \geq1$, $i=0,1 , \ldots,n-k$.

For more on the disk and interval Bézier curves, see [14–20].

2 Geometric continuity of disk Bézier curves

Geometric continuity of two disk Bézier curves is independent of their parametrization and denoted by $G^{k}$; it produces additional free parameters; see [21–23]. The definition of $G^{k}$-continuity of Bézier curves is generalized to the case of disk Bézier curves. Thus, the disk Bézier curves $(P_{n})(t)$ and $(Q_{m})(t)$ are said to be $G^{k}$-continuous at $t=0,1$ if there exists a strictly increasing parametrization $s(t): [0,1] \rightarrow[0,1]$ with $s(0)=0$, $s(1)=1$, and

$$ (Q_{m})^{(i)}(t)=(P_{n})^{(i)} \bigl(s(t)\bigr),\quad t=0,1, i=0,1, \ldots, k. $$

(6)

$G^{k}$-continuity furnishes the shape of the approximating curve with additional design parameters that are used in $G^{k}$-degree reduction as additional parameters to reduce the error.

3 Degree reduction of disk Bézier curves

Given a disk Bézier curve $(P_{n})(t)$ of degree n, a disk Bézier curve $(Q_{m})(t)$ of degree m, $m< n$, has to be found such that $(Q_{m})(t)$ bounds $(P_{n})(t)$ as tight as possible. Chen and Yang proposed in [15] an algorithm to degree reduce disk Bézier curves; they consider two cases, constrained degree reduction and non-constrained degree reduction. Hu and Wang presented in [16] a method of degree reduction without any boundary conditions based on quadratic programming. Jiang and Tan considered in [17] degree reduction methods of disk Said-Ball curves with and without interpolation of the endpoints. In this paper, geometric continuity conditions between the adjacent disk Bézier curves are considered; this means that $(Q_{m})(t)$ has to satisfy the following three conditions:

• (1) $(P_{n})(t)$ and $(Q_{m})(t)$ are $G^{k}$-continuous at the end disks, $t=0,1$, for $k=0,1$,

• (2) the $L_{2}$-error between $(P_{n})(t)$ and $(Q_{m})(t)$ is minimum, and

• (3) $(P_{n})(t) \subseteq(Q_{m} )(t)$, $0 \leq t \leq1$.

The curves $(P_{n})(t)$ and $(Q_{m})(t)$ can be written in matrix form as

$$ (P_{n}) (t) = \sum^{n}_{i=0} (p_{i}) B^{n}_{i}(t) =: B_{n} (P_{n}) , \qquad (Q_{m}) (t) = \sum ^{m}_{i=0} (q_{i}) B^{m}_{i}(t) =: B_{m} (Q_{m}), $$

(7)

where $B_{n}=(B^{n}_{0}(t),B^{n}_{1}(t),\ldots, B^{n}_{n}(t))$ and $(P_{n})=((p_{0}),\ldots,(p_{n}))^{t}$ are a row vector formed by Bernstein polynomials and a column vector formed by the Bézier disks, respectively. Similarly, $B_{m}$ and $(Q_{m})$ are defined. We have to note the mixed use of the notations. For example $(Q_{m})$ denotes a disk, a disk Bézier curve, or a column vector, as should be clear from the context.

We degree reduce the disk Bézier curve by first applying geometric continuity conditions at the end disks, i.e. under the satisfaction of one of the conditions: $G^{0}$-continuity or $G^{1}$-continuity at the boundaries. To minimize

$$ \varepsilon = \int_{0}^{1} \bigl\Vert B_{n} (P_{n})- B_{m} (Q_{m})\bigr\Vert ^{2} \, dt, $$

(8)

we use the $L_{2}$-norm to measure and minimize the distances between the center Bézier curves p and q, and the radius Bézier curves r and r̃. To ensure that $(P_{n})(t) \subseteq(Q_{m} )(t)$, we can add terms like $d_{1}(t) = \| p(t)-q(t)\|_{2}$ and $d_{2}(t) = | \tilde{r}(t)- r(t)|_{2}$ or both to the radius curve of $(Q_{m} )(t)$ if needed.

In the following sections, we investigate, in particular, the cases of $G^{0}$-, and $G^{1}$-continuity with degree reduction of disk Bézier curves.

4 $G^{0}$-Degree reduction

$G^{0}$-continuity of $(Q_{m})(t)$ and $(P_{n})(t)$ at the disks corresponding to $t=0,1$, requires the satisfaction of the following two conditions:

$$ (Q_{m}) (i)=(P_{n}) \bigl(s(i)\bigr),\quad i=0,1. $$

(9)

This means that the two curves have to have common end disks, i.e.

$$ (q_{0})=(p_{0}),\qquad (q_{m})= (p_{n}). $$

The disks $(q_{0})$ and $(q_{m})$ are determined by $G^{0}$-continuity conditions at the boundaries. The elements of $(Q_{m})$ are decomposed into two parts. The part of constrained control disks $(Q_{m})^{c}= [ (q_{0}),(q_{m}) ]^{t}$ and the part of free control disks $(Q_{m})^{f}= (Q_{m}) \backslash(Q_{m})^{c}= [ (q_{1}), \ldots ,(q_{m-1})]^{t}$. Similarly, $B_{m}$ is decomposed. Accordingly, the error term between $(Q_{m})(t)$ and $(P_{n})(t)$ becomes

$$\begin{aligned} \varepsilon&= \int_{0}^{1} \bigl\Vert B_{n} (P_{n})- B_{m} (Q_{m})\bigr\Vert ^{2} \, dt \\ &= \int_{0}^{1} \bigl\Vert B_{n} (P_{n})- B_{m}^{c} (Q_{m})^{c}- B_{m}^{f} (Q_{m})^{f}\bigr\Vert ^{2}\, dt. \end{aligned}$$

(10)

In the last equation, the vector $(Q_{m})^{f}$ is unknown and thus ε attains its minimum when the partial derivatives of ε are zeros. Differentiating with respect to the unknown control disks $(Q_{m})^{f}$, we get

$$ \frac{ \partial\varepsilon}{\partial(Q_{m})^{f}} = 2\int_{0}^{1} \bigl(B_{m}^{f}\bigr)^{t} \bigl( B_{n} (P_{n})- B_{m}^{c} (Q_{m})^{c}- B_{m}^{f} (Q_{m})^{f} \bigr)\, dt. $$

Evaluating the integrals and equating to zero gives

$$ \frac{ \partial\varepsilon}{\partial(Q_{m})^{f}} = 2 \bigl( G_{m,n}^{p} (P_{n}) - G_{m,m}^{c} (Q_{m})^{c} - G_{m,m}^{f} (Q_{m})^{f} \bigr) = 0, $$

(11)

where

$$\begin{aligned}& G_{m,n}^{p} := G_{m,n}(1, \ldots, m-1; 0, 1, \ldots, n) , \\& G_{m,m}^{c} := G_{m,m}(1, \ldots, m-1; 0, m) , \\& G_{m,m}^{f} := G_{m,m}(1, \ldots, m-1; 1, \ldots, m-1) , \end{aligned}$$

and $G_{m,n}( \ldots; \ldots)$ is the sub-matrix of $G_{m,n}$ formed by the indicated rows and columns.

The system in (11) consists of both points and univariate variables. The center curve of the disk Bézier curve is expanded into x and y components together with their radius curve. Therefore, our system of equations has $\tilde{x}_{k}$, $\tilde {y}_{k}$, $\tilde{r}_{k}$ as variables for $k=1, \ldots, m-1$. The following vectors are defined to express the linear system in explicit form:

$$\begin{aligned}& P_{n} = [ x_{0}, \ldots,x_{n},y_{0}, \ldots,y_{n},r_{0}, \ldots,r_{n}]^{t} , \\& Q_{m}^{F} = [ \tilde{x}_{1}, \ldots, \tilde{x}_{m-1}, \tilde{y}_{1}, \ldots, \tilde{y}_{m-1}, \tilde{r}_{1}, \ldots, \tilde{r}_{m-1}]^{t}, \\& Q_{m}^{C} = [ \tilde{x}_{0}, \tilde{x}_{m}, \tilde{y}_{0}, \tilde{y}_{m}, \tilde{r}_{0}, \tilde{r}_{m}]^{t} . \end{aligned}$$

Let ⊕ be the direct sum and define the matrices

$$\begin{aligned}& G^{P}_{m,n} = G^{p}_{m,n} \oplus G^{p}_{m,n} \oplus G^{p}_{m,n}, \\& G^{C}_{m,m} = G^{c}_{m,m} \oplus G^{c}_{m,m} \oplus G^{c}_{m,m}, \\& G^{F}_{m,m} = G^{f}_{m,m} \oplus G^{f}_{m,m} \oplus G^{f}_{m,m}. \end{aligned}$$

(12)

The matrix $G^{F}_{m,m}$ inherits the properties of the Gram matrix $G^{f}_{m,m}$. The coordinate form of the expansion of (11) becomes

$$ G_{m,m}^{F} Q_{m}^{F}= G_{m,n}^{P}{P_{n}} - G_{m,m}^{C} Q_{m}^{C}. $$

(13)

The last step converts the system (11) that contains disks into a linear system of coordinates of the disks, namely the x, y, and radius r coordinates. Since the matrix $G^{F}_{m,m}$ is not singular; it is real, symmetric, and positive definite; therefore, the solution of the system always exists and has the form

$$ Q_{m}^{F} = \bigl(G_{m,m}^{F} \bigr)^{-1} \bigl(G_{m,n}^{P}{P_{n}} - G_{m,m}^{C} Q_{m}^{C} \bigr). $$

(14)

5 $G^{1}$-Degree reduction

$G^{1}$-continuity of $(Q_{m})(t)$ and $(P_{n})(t)$ at the disks corresponding to $t=0,1$, requires the two curves $(P_{n})(t)$ and $(Q_{m})(t)$ to be $G^{0}$-continuous and satisfy further the following conditions:

$$ (Q_{m})'(i)= s'(i) (P_{n})'\bigl(s(i)\bigr), \quad s'(i)> 0, i=0,1. $$

(15)

This means that the direction of the tangents at the two end disks of $(Q_{m})$ and $(P_{n})$ should coincide, but they need not to be of equal lengths. As in [9], $s'(i)=\delta_{i}$, $i=0,1$, are used. This substitution gives

$$ (Q_{m})'(i)= \delta_{i} (P_{n})'(i),\quad i=0,1. $$

(16)

We can solve (9) and (16) for the two control disks at either end of the curve:

$$\begin{aligned}& (q_{0}) =(p_{0}), \qquad (q_{m}) = (p_{n}), \\& (q_{1}) =(p_{0})+ \frac{n}{m} \Delta(p_{0}) \delta_{0}, \qquad (q_{m-1}) = (p_{n}) - \frac{n}{m} \Delta(p_{n-1})\delta_{1}. \end{aligned}$$

The disks $(q_{0})$, $(q_{1})$, $(q_{m-1})$, and $(q_{m})$ are determined by $G^{1}$-continuity conditions at the boundaries; accordingly, the elements of $(Q_{m})$ are decomposed into two parts. The part of constrained control disks $(Q_{m})^{c}= [ (q_{0}), (q_{1}), (q_{m-1}), (q_{m}) ]^{t}$ and the part of free control disks $(Q_{m})^{f}= (Q_{m}) \backslash(Q_{m})^{c}= [ (q_{2}), \ldots, (q_{m-2})]^{t}$. Similarly, $B_{m}$ is decomposed. Thus, the error term becomes

$$\begin{aligned} \varepsilon&= \int_{0}^{1} \bigl\Vert B_{n} (P_{n})- B_{m} (Q_{m})\bigr\Vert ^{2} \, dt \\ &= \int_{0}^{1} \bigl\Vert B_{n} (P_{n})- B_{m}^{c} (Q_{m})^{c}- B_{m}^{f} (Q_{m})^{f}\bigr\Vert ^{2} \, dt. \end{aligned}$$

(17)

The error $\varepsilon:=\varepsilon((Q_{m})^{f}, \delta_{0}, \delta_{1})$ is a function of $(Q_{m})^{f}$, $\delta_{0}$, and $\delta_{1}$. Differentiating with respect to the unknown control disks $(Q_{m})^{f}$ we get

$$ \frac{ \partial\varepsilon}{\partial(Q_{m})^{f}} = 2\int_{0}^{1} \bigl\Vert B_{n} (P_{n})- B_{m}^{c} (Q_{m})^{c}- B_{m}^{f} (Q_{m})^{f}\bigr\Vert B_{m}^{f}\, dt. $$

Evaluating the integral and equating to zero gives

$$ G_{m,n}^{p} (P_{n}) - G_{m,m}^{c} (Q_{m})^{c} - G_{m,m}^{f} (Q_{m})^{f} = 0, $$

(18)

where

$$\begin{aligned}& G_{m,n}^{p} := G_{m,n}(2, \ldots, m-2; 0, 1, \ldots, n) , \\& G_{m,m}^{c} := G_{m,m}(2, \ldots, m-2; 0, 1, m-1, m) , \\& G_{m,m}^{f} := G_{m,m}(2, \ldots, m-2; 2, \ldots, m-2) , \end{aligned}$$

and $G_{m,n}( \ldots; \ldots)$ is the sub-matrix of $G_{m,n}$ formed by the indicated rows and columns.

Differentiating (17) with respect to $\delta_{i}$, $i=0,1$ and equating to zero gives

$$\begin{aligned}& \frac{ \partial\varepsilon}{\partial\delta_{0}} = \bigl(G_{m,n}^{1}(P_{n}) - G_{m,m}^{1;c} (Q_{m})^{c} - G_{m,m}^{1;f} (Q_{m})^{f} \bigr)\cdot \Delta(p_{0}) = 0, \end{aligned}$$

(19)

$$\begin{aligned}& \frac{ \partial\varepsilon}{\partial\delta_{1}} = \bigl(G_{m,n}^{m-1} (P_{n}) - G_{m,m}^{m-1;c} (Q_{m})^{c} - G_{m,m}^{m-1;f} (Q_{m})^{f} \bigr)\cdot \Delta(p_{n-1}) = 0, \end{aligned}$$

(20)

where, for $j=1,m-1$,

$$\begin{aligned}& G_{m,n}^{j} := G_{m,n}(j; 0, 1, \ldots, n) , \\& G_{m,m}^{j;c} := G_{m,m}(j; 0, 1, m-1, m) , \\& G_{m,m}^{j;f} := G_{m,m}(j; 2, \ldots, m-2) . \end{aligned}$$

(21)

The center curve of the disk Bézier curve is expanded into x and y components together with the radius curve. Therefore, the variables of our system of equations are $\tilde {x}_{k}$, $\tilde{y}_{k}$, $\tilde{r}_{k}$, $k=2, \ldots, m-2$, $\delta_{0}$, and $\delta_{1}$. To express the system in a clear form, we have to decompose each of $q_{1}$ and $q_{m-1}$ into a constant part and a part involving $\delta_{0}$ and $\delta_{1}$, respectively. Let $v_{1}$ and ${v}_{m-1}$ be the constant parts of $q_{1}$ and $q_{m-1}$, respectively. Similarly $\tilde{r}_{1}$ and $\tilde{r}_{m-1}$ are decomposed. Let $s_{1}$ and ${s}_{m-1}$ be the constant parts of $\tilde{r}_{1}$ and $\tilde{r}_{m-1}$, respectively. Hence

$$ v_{1} = p_{0}, \qquad v_{m-1} = p_{n}, \qquad s_{1} = r_{0}, \qquad s_{m-1} = r_{n}. $$

The following vectors are defined to express the linear system in explicit form:

$$\begin{aligned}& P_{n} = [ x_{0}, \ldots,x_{n},y_{0}, \ldots,y_{n},r_{0}, \ldots,r_{n}]^{t} , \\& Q_{m}^{F} = \bigl[ \tilde{x}_{2}, \ldots, \tilde{x}_{m-2}, \tilde{y}_{2}, \ldots, \tilde{y}_{m-2}, \tilde{r}_{2}, \ldots, \tilde{r}_{m-2}, \delta _{0}^{c}, \delta_{1}^{c}, \delta_{0}^{r}, \delta_{1}^{r} \bigr]^{t}, \\& Q_{m}^{C} = \bigl[ \tilde{x}_{0}, v^{x}_{1}, v^{x}_{m-1}, \tilde{x}_{m}, \tilde{y}_{0}, v^{y}_{1}, v^{y}_{m-1}, \tilde{y}_{m},\tilde {r}_{0}, s_{1}, s_{m-1}, \tilde{r}_{m} \bigr]^{t} . \end{aligned}$$

Define the matrices A, B, $L_{m,n}^{c}$, $L_{m,m}^{cc}$, $L_{m,m}^{fc}$, $L_{m,n}^{r}$, $L_{m,m}^{cr}$, $L_{m,m}^{fr}$ as follows:

$$\begin{aligned}& A = \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} \Delta p_{0} & 0 \\ 0 & \Delta p_{n-1} \end{array}\displaystyle \right ] \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} G_{m,m}(1,1) & G_{m,m}(1,m-1) \\ G_{m,m}(m-1,1) & G_{m,m}(m-1,m-1) \end{array}\displaystyle \right ] \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} \Delta p_{0} & 0 \\ 0 & \Delta p_{n-1} \end{array}\displaystyle \right ],\qquad \\& B = \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} \Delta r_{0} & 0 \\ 0 & \Delta r_{n-1} \end{array}\displaystyle \right ] \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} G_{m,m}(1,1) & G_{m,m}(1,m-1) \\ G_{m,m}(m-1,1) & G_{m,m}(m-1,m-1) \end{array}\displaystyle \right ] \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} \Delta r_{0} & 0 \\ 0 & \Delta r_{n-1} \end{array}\displaystyle \right ], \\& L_{m,n}^{c} = \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} G^{1}_{m,n}\Delta x_{0} & G^{1}_{m,n}\Delta y_{0} \\ G^{m-1}_{m,n}\Delta x_{n-1} & G^{m-1}_{m,n}\Delta y_{n-1} \end{array}\displaystyle \right ] , \qquad L_{m,n}^{r} = \left [ \textstyle\begin{array}{@{}c@{}} G^{1}_{m,n}\Delta r_{0} \\ G^{m-1}_{m,n}\Delta r_{n-1} \end{array}\displaystyle \right ] , \\& L_{m,m}^{cc} = \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} G^{1;c}_{m,m}\Delta x_{0} & G^{1;c}_{m,m}\Delta y_{0} \\ G^{m-1;c}_{m,m}\Delta x_{n-1} & G^{m-1;c}_{m,m}\Delta y_{n-1} \end{array}\displaystyle \right ], \qquad L_{m,m}^{cr} = \left [ \textstyle\begin{array}{@{}c@{}} G^{1;c}_{m,m}\Delta r_{0} \\ G^{m-1;c}_{m,m}\Delta r_{n-1} \end{array}\displaystyle \right ], \\& L_{m,m}^{fc} = \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} G^{1;f}_{m,m}\Delta x_{0} & G^{1;f}_{m,m}\Delta y_{0} \\ G^{m-1;f}_{m,m}\Delta x_{n-1} & G^{m-1;f}_{m,m}\Delta y_{n-1} \end{array}\displaystyle \right ], \qquad L_{m,m}^{fr} = \left [ \textstyle\begin{array}{@{}c@{}} G^{1;f}_{m,m}\Delta r_{0} \\ G^{m-1;f}_{m,m}\Delta r_{n-1} \end{array}\displaystyle \right ]. \end{aligned}$$

Let ⊕ be the direct sum. Define the matrices

$$\begin{aligned}& G^{p++}_{m,n} = G^{p}_{m,n} \oplus G^{p}_{m,n} \oplus G^{p}_{m,n}, \\& G^{c++}_{m,m} = G^{c}_{m,m} \oplus G^{c}_{m,m} \oplus G^{c}_{m,m},\\& G^{f++}_{m,m} = G^{f}_{m,m} \oplus G^{f}_{m,m} \oplus G^{f}_{m,m}. \end{aligned}$$

(22)

Further define $L_{m,n}^{+}$, $L_{m,m}^{c+}$, $L_{m,m}^{f+}$ as

$$ L_{m,n}^{+} = L_{m,n}^{c} \oplus L_{m,n}^{r}, \qquad L_{m,m}^{c+} = L_{m,m}^{cc} \oplus L_{m,m}^{cr}, \qquad L_{m,m}^{f+} = L_{m,m}^{fc} \oplus L_{m,m}^{fr}. $$

(23)

After some mathematical operations the coordinate form of the expansion of (18) together with (19) and (20) becomes

$$ G_{m,m}^{F} Q_{m}^{F}= G_{m,n}^{P} P_{n} - G_{m,m}^{C} Q_{m}^{C}, $$

(24)

where

$$ G^{P}_{m,n} = \left [ \textstyle\begin{array}{@{}c@{}} G^{p++}_{m,n} \\ L_{m,n}^{+} \end{array}\displaystyle \right ] , \qquad G_{m,m}^{C}=\left [ \textstyle\begin{array}{@{}c@{}} G^{c++}_{m,m} \\ L_{m,m}^{c+} \end{array}\displaystyle \right ], \qquad G^{F}_{m,m} = \left [ \textstyle\begin{array}{@{}c@{\quad}c@{}} G^{f++}_{m,m}& \frac{n}{m} (L_{m,m}^{f+})^{t} \\ L_{m,m}^{f+} & \frac {n}{m} (A \oplus B) \end{array}\displaystyle \right ]. $$

The square matrix $G^{F}_{m,m}$ is a block matrix formed by $G^{f++}_{m,m}$, $(L_{m,m}^{f+})^{t}$, $L_{m,m}^{f+}$, and ${A \oplus B}$. The matrix $G^{f++}_{m,m}$ is positive definite, and the matrix ${A \oplus B}$, excluding the $\Delta c_{0}$ and $\Delta c_{n-1}$ parts, is also positive definite. Therefore the matrix $G^{F}_{m,m}$ is non-singular; consequently, the unknowns in (24) are given by

$$ Q_{m}^{F} = \bigl(G_{m,m}^{F} \bigr)^{-1} \bigl(G_{m,n}^{P} P_{n} - G_{m,m}^{C} Q_{m}^{C} \bigr). $$

(25)

In the following section, this method is used to illustrate some examples.

6 Examples and comparisons

In this section, we illustrate four examples to demonstrate the effectiveness of the proposed methods. The first two examples are from [15], the third example is from [17], and the last example used is from [16]. Regarding the error functions, throughout this paper different kinds of lines are used to represent the cases as follows:

• long-dashed: WB-degree reduction without any boundary condition,

• short-dashed: $G^{0}$-degree reduction,

• dotted: $G^{1}$-degree reduction.

Example 1

(see [15])

Consider the disk Bézier curve $(P_{n})(t)$ of degree nine with control disks:

$$\begin{aligned}& (\mathbf{P}_{0})=(9,10)_{2.3}, \qquad (\mathbf{P}_{1})= (10,24)_{3},\qquad (\mathbf {P}_{2})=(18,44)_{1.5}, \qquad (\mathbf{P}_{3})= (30,46)_{2}, \\& (\mathbf{P}_{4})=(30,20)_{2.4},\qquad (\mathbf{P}_{5})= (38,15)_{3},\qquad (\mathbf{P}_{6})=(54,15)_{2.5}, \qquad (\mathbf {P}_{7})= (68,35)_{2.2}, \\& (\mathbf{P}_{8})=(64,68)_{3},\qquad (\mathbf{P}_{9})= (85,80)_{2} . \end{aligned}$$

We use WB-, $G^{0}$- and $G^{1}$-degree reduction methods to reduce the degree of $(P_{n})(t)$ to degree eight disk Bézier curve. Figure 2 depicts the original curve and the $G^{1}$-degree reduced curve. The corresponding $G^{0}$- and WB-degree reduced disk Bézier curves are depicted in Figure 3. The error functions for the three methods are shown in Figure 4.

Figure 2

Illustrating Example  1 . Left: Disk Bézier curve of degree nine. Right: $G^{1}$-degree reduction.

Figure 3

Continuing illustrating Example  1 . Left: $G^{0}$-degree reduction. Right: WB-degree reduction.

Figure 4

Error functions for WB- (long-dashed); $\pmb{G^{0}}$ - (short-dashed), and $\pmb{G^{1}}$ - (dotted) degree reductions in Example  1 .

The methods in [15] of linear programming (LP1, LPM) and constrained linear programming (CLP1, CLPM) degree reductions give errors of 0.14, 0.25, 0.15, 0.18, respectively, while the proposed methods of WB-, $G^{0}$-, and $G^{1}$-degree reductions have errors of 0.04, 0.025, 0.029, respectively. This example shows that the methods proposed in this paper give better results than existing methods besides satisfying additional boundary conditions.

Example 2

(see [15])

Given the disk Bézier curve $(P_{n})(t)$ of degree six with control disks:

$$\begin{aligned}& (\mathbf{P}_{0})=(60,350)_{10}, \qquad ( \mathbf{P}_{1})= (140,140)_{4},\qquad (\mathbf {P}_{2})=(200,90)_{15}, \\& (\mathbf{P}_{3})= (250,310)_{20},\qquad (\mathbf{P}_{4})=(350,210)_{24}, \qquad ( \mathbf{P}_{5})= (400,410)_{10}, \\& (\mathbf {P}_{6})=(440,180)_{5} . \end{aligned}$$

$(P_{n})(t)$ is reduced to a disk Bézier curve $(Q_{m})(t)$ of degree five using WB-, $G^{0}$-, and $G^{1}$-degree reduction methods. The error functions for the proposed three methods are shown in Figure 5.

Figure 5

Error functions by WB- (long-dashed); $\pmb{G^{0}}$ - (short-dashed), and $\pmb{G^{1}}$ - (dotted) degree reductions in Example  2 .

The methods in [15] are based on linear programming (LP1, LPM) and constrained linear programming (CLP1, CLPM) degree reduction methods and give errors of 6.2, 6.2, 12.6, 11.6, respectively. They also approached the problem by making each control point of the degree reducing disk Bézier curve bound the original one and got an error of 70. The proposed methods in this paper with WB-, $G^{0}$-, and $G^{1}$-degree reductions have errors of 7, 5.1, 4.9, respectively.

Example 3

(see [17])

Consider the disk Bézier curve $(P_{n})(t)$ of degree seven with control disks:

$$\begin{aligned}& (\mathbf{P}_{0})=(45,360)_{10},\qquad (\mathbf{P}_{1})= (130,180)_{8}, \qquad (\mathbf {P}_{2})=(210,100)_{11}, \\& (\mathbf{P}_{3})= (280,320)_{14},\qquad (\mathbf{P}_{4})=(360,220)_{25},\qquad ( \mathbf{P}_{5})= (410,440)_{18}, \\& (\mathbf{P}_{6})= (480,350)_{11}, \qquad ( \mathbf{P}_{7})= (540,210)_{8} . \end{aligned}$$

$(P_{n})(t)$ is reduced to degree six. The methods in [17] without interpolation (WIDR) and with interpolation (IDR) degree reductions of Said-Ball curves give errors of 3, 4, respectively.

The proposed methods of WB-, $G^{0}$- and $G^{1}$-degree reductions give errors of 4, 2.6, 2.5, respectively. The error functions for the three methods are shown in Figure 6.

Figure 6

Error functions by WB- (long-dashed); $\pmb{G^{0}}$ - (short-dashed), and $\pmb{G^{1}}$ - (dotted) degree reductions in Example  3 .

Example 4

(see [16])

Consider the disk Bézier curve $(P_{n})(t)$ of degree eight with control disks:

$$\begin{aligned}& (\mathbf{P}_{0})=(61,149)_{10},\qquad (\mathbf{P}_{1})= (86,303)_{4}, \qquad (\mathbf {P}_{2})=(203,449)_{10}, \\& (\mathbf{P}_{3})= (357,430)_{15},\qquad (\mathbf{P}_{4})=(412,328)_{20}, \qquad ( \mathbf{P}_{5})= (385,115)_{18}, \\& (\mathbf{P}_{6})=(482,81)_{8},\qquad (\mathbf{P}_{7})= (661,102)_{10}, \qquad ( \mathbf{P}_{8})=(705,237)_{5} . \end{aligned}$$

We use WB-, $G^{0}$-, $G^{1}$-methods to reduce the degree of $(P_{n})(t)$ to a degree five disk Bézier curve. The error functions for the three methods are shown in Figure 7 with maximum errors of 5, 4.5, 14, respectively. Hu and Wang used in [16] a degree reduction method based on quadratic programming without any boundary condition and got an error of 9.4.

Figure 7

Error functions by WB- (long-dashed); $\pmb{G^{0}}$ - (short-dashed), and $\pmb{G^{1}}$ - (dotted) degree reductions in Example  4 .

Examples 1-4 show that the proposed WB-, $G^{0}$-, $G^{1}$-degree reduction methods in this paper give errors that are less than existing methods with and without continuity conditions; moreover, our methods are the first methods of this kind that consider geometric continuity with degree reductions.

Imposing boundary conditions consumes free parameters that can be used to minimize the error. That is, using the same method of degree reduction without boundary conditions gives less error than with boundary conditions.

Although it is not fair to compare the numerical results of a method with boundary conditions to a method without boundary conditions, our proposed methods of degree reduction give errors that are smaller than existing methods. The numerical results are summarized in Table 1.

Table 1 Comparison with other existing methods

7 Conclusions

In this paper, we presented WB-, $G^{0}$-, and $G^{1}$-multi-degree reduction methods of disk Bézier curves. The significance of our work is quite interesting, since the center curve and the radius of disk Bézier curve are degree reduced simultaneously, unlike other methods. This reduces the computational expenses. The examples show the effectiveness of the proposed methods; they tightly bound the original disk Bézier curve very effectively. Our proposed $G^{0}$- and $G^{1}$-degree reduction methods are better than the existing methods; see the examples and comparisons with examples in [15–17]. The benefits and features of the proposed methods can be summarized as follows:

• Continuity conditions are considered, while most existing methods do not consider any boundary conditions.

• Geometric conditions are considered with the method of degree reduction for the first time, which makes the methods novel and new.

• The degree reduction is done for the center Bézier curve and the radius curve simultaneously, which minimizes the computational cost of degree reducing disk Bézier curves.

• The numerical results show that our proposed methods have error less than existing methods besides the advantages mentioned above.

• Existing methods are impractical because disk Bézier curves do not exist alone; they are pieces of splines and degree reducing them without boundary conditions gives a spline that is not continuous.

It worth noting that the proposed methods in this paper are the first to consider geometric continuity with degree reductions.