View of Stancu Curves in CAGD

Rev. Anal. Num´er. Th´eor. Approx., vol. 31 (2002) no. 1, pp. 71–87 ictp.acad.ro/jnaat

STANCU CURVES IN CAGD

ADALBERT CSABA HATVANY^∗

Abstract. Starting from the one-parameter dependent linear polynomial Stancu operator, we consider the related polynomial curve scheme with one scalar shape parameter. This scheme, called by us the Stancu curve scheme, generalizes in a suitable manner the classical Bernstein-B´ezier scheme and provides more design flexibility by means of the shape parameter.

MSC 2000. Primary 65D17, 65D05; Secondary 65D10, 68U05.

Keywords. curve scheme, de Casteljau algorithm, B´ezier curve, P´olya curve, Stancu operator.

1. INTRODUCTION

Let us begin by recalling that the (one-parameter dependent linear polyno- mial) Stancu operatorS^n;α, for the intervalI = [0,1] and a functionf :I →R,

(S^n;αf) (x) =

n

X

i=0

S_i^n;α(x)f_nⁱ, whereα is a real parameter and

S_i^n;α(x) = n i

!

i−1

Q

j=0

(x+jα)

n−i−1

Q

j=0

(1−x+jα) (1 +α)(1 + 2α). . .(1 + (n−1)α),

has been introduced and investigated by D. D. Stancu already in 1968 (see [16] where the polynomialsS^n;α_i (x) are denoted by w_n,i(x;α)).

The Stancu operator was studied further by Stancu in his subsequent papers [17], [18], as well as in several papers published by other authors (see [8], [5], [14], and [15]).

Although the Stancu operator has many properties similar to the Bernstein operator, until now only a few considerations from the point of view of CAGD (computer aided geometric design) of the Stancu polynomials S_i^n;α has been made: [9], [11], [10], [7], [19], [20], [21].

Starting with the classical P´olya’s urn model as introduced by F. Eggen- berger and G. P´olya [4], R. N. Goldman [11] studies the corresponding one- parameter dependent probability distributionsD_iⁿ(a, x) and the curve scheme related to these distributions. The distributions D_iⁿ(a, x) are exactly the

∗WMF AG, CAD/CAM Systems, D-73309 Geislingen/Steige, Germany. Mailing address:

Bahnhofstraße 18, D-73329 Kuchen/Fils, Germany, e-mail: [email protected].

Stancu polynomials S_i^n;α(x) as observed by Stancu in [17]. The curves that use the distributions D_iⁿ(a, x) as blending functions are called by Goldman P´olya curves. Ph. J. Barry and R. N. Goldman generalize this one-parameter dependent curve scheme to a curve scheme depending on 2nparameter, where n is the degree of the curves. This generalized curves are also called P´olya curves. We will use the term Stancu curves for the one-parameter case, letting the term P´olya curves denote the multi-parameter case. Thus, for us a Stancu curve is a uniform P´olya curve, where the parameter α gives the step of the progressive knot sequence (for details see [2], [3] or Sec. 4 bellow).

The aim of this paper is to study the polynomial curve scheme based on the Stancu polynomials. We begin in Section 2 by giving a brief overview of factorial powers and generalized binomial coefficients. Then, in Section 3 we formally introduce the Stancu polynomials and prove the first properties. The Stancu curve scheme is presented in Section 4. In Section 5 we establish the degree elevation formula, while Section 6 is devoted to the derivative formula for the new curve scheme. Conclusions are presented in the last section.

2. FACTORIAL POWERS AND GENERALIZED BINOMIAL COEFFICIENTS

In this brief section we recall some useful facts concerning the factorial powers and the generalized binomial coefficients and establish our notation.

Let α be a fixed real number. For each x ∈R and n∈N then^th factorial power of x (with respect toα) is defined by

(2.1) x^[0;α]:= 1, x^[n;α]:=x^[n−1;α]·(x+ (n−1)α), n= 1,2, ...

Although the factorial power depends explicitly on the value of the param- eter α, when the context is clear, we shall write simply x^[n] instead ofx^[n;α].

From this definition follows immediately that

(2.2) x^[n]=

n−1

Y

i=0

(x+iα)

for everyn∈N, where the void product is considered to be equal to 1.

For eachn∈Nwe define

(2.3) x^[−n]:= 1

x^[n] .

The following properties can be easily derived from the definition above:

x^[m+n]=x^[m]·(x+mα)^[n]=x^[n]·(x+nα)^[m], (2.4)

x^[m]

x^[n] = x+ min{m, n}^[m−n]

(2.5)

forn, m∈N.

Now it is easy to see that for eachn∈Nand for two arbitrary real numbers aand b, the binomial formula generalizes to

(2.6) (a+b)^[n]=

n

X

i=0 n

i

a^[i]b^[n−i].

To simplify some formulae we use thegeneralized binomial coefficients (with respect toα)ⁿ_iα defined by the following recurrence:

(2.7) ⁿ_0α := 1, ⁿ_iα := _1+(n−1)α^{1 n−1}_{i α}+ⁿ⁻¹_i−1

α

.

Again, if the context is clear, we shall write simply ⁿ_i instead of ⁿ_i

α. From the definition follows immediately that

(2.8) ⁿ_i= (ⁿ_i)

1^[n] .

Now, the generalized binomial formula can be written as (2.9) (a+b)^[n]= 1^[n]

n

X

i=0

_n

i

a^[i]b^[n−i].

3. STANCU POLYNOMIALS

This section formally introduces the Stancu polynomials and gives the first properties.

For x ∈R we writeu(x) =u =x and v(x) = v = 1−x. Note that v and u are the affine coordinates of the pointx ∈R w.r.t. the interval I = [0,1].

Consider n∈ N and α a fixed real number such that α ∈^h−¹_n,∞ ifn 6= 0, orα = 0 if n= 0. For x∈R,r = 0,1, . . . , n and i= 0,1, . . . , r we define the polynomials

S₀^r;α(x) :=S₀⁰(x)≡1, r = 0 (3.1)

S_i^r;α(x) := ^u+(i−1)α_1+(r−1)αS_i−1^r−1;α(x) +^{v+(r−i−1)α}_1+(r−1)α S_i^r−1;α(x), r = 1,2, . . . , n , where S_j^s;α is considered null if j /∈ {0,1, . . . , s}. Again, when the context is clear, we drop the superscript α and denote S_i^r;α simply by S_i^r. Clearly, S_i^r are univariate polynomials of degree at mostndepending on the independent variablex. In fact,S_i^rare polynomials of degree exactlyn, as we shall see later (see Remark 3.1). Now we give the formal definition of the Stancu polynomials and prove that they satisfy the recurrence relation (3.1).

Definition 3.1. Let n ∈ N and α be a fixed real number such that α ∈ h−¹_n,∞ if n6= 0, or α = 0 if n= 0. For r = 0,1, . . . , n and i = 0,1, . . . , r the polynomial

(3.2) ^r_iu^[i]v^[r−i]

(where the factorial powers and the generalized binomial coefficient are con- sidered w.r.t. the parameter α) is called the i^th Stancu polynomial of degree r over the interval [0,1] (with the parameterα).

Theorem 3.2. The polynomials S_i^r, r = 0,1, . . . , n, i= 0,1, . . . , r,are the Stancu polynomials, namely

(3.3) S_i^r=^r_iu^[i]v^[r−i].

Proof. We use induction onn. The result is certainly true forr= 0. Assume it is so for r−1. Then by the recursion formula (3.1)

S_i^r = ^u+(i−1)α_1+(r−1)αS_i−1^r−1+ ^{v+(r−i−1)α}_1+(r−1)α S_i^r−1

= ^u+(i−1)α_1+(r−1)α^r−1_i−1u^[i−1]v^[r−i−1]+^{v+(r−i−1)α}_1+(r−1)α ^r−1_i u^[i]v^[r−i−1]

= _1+(r−1)α^{1 r−1}_i−1+^r−1_i u^[i]v^[r−i]

=^r_iu^[i]v^[r−i],

where for the last equality we used (2.7).

Remark 3.1. Similar to Bernstein polynomials, the Stancu polynomials have the following properties:

(1) The polynomialsS_iⁿ are of degree n.

(2) For α= 0, the Stancu polynomials specialize to the Bernstein polynomials:

S_iⁿ=B_iⁿ= ⁿ_iuⁱvⁿ⁻ⁱ.

(3) For α=−¹_n,n6= 0, the Stancu polynomials specialize to the Lagrange polynomials for the knotsx_i= _nⁱ,i= 0,1, . . . , non the interval [0,1]:

S_iⁿ=Lⁿ_i =

n

Y

j=0 j6=i

(x−xj) , _n

Y

j=0 j6=i

(xi−xj).

(4) For α≥0, the Stancu polynomials are nonnegative over [0,1].

(5) S_iⁿ(0) =δ_i0 and S_iⁿ(1) =δ_in fori= 0,1, . . . , n.

In the next section we present the curve scheme built on the Stancu polyno- mials. For a curve scheme the affine invariance property, i.e. the independence from the coordinate system is crucial. It is well known that this property is equivalent to the partition of unity property for the blending function of the scheme. The next theorem shows that the Stancu polynomials indeed partition the unity. We omit the straightforward proof by induction on n.

Theorem3.3. Forα≥0 the Stancu polynomialsSⁿ_i, i= 0,1, . . . , n, n∈N form a partition of unity.

Figure 3.1 illustrates the Stancu polynomials of degree 3 for different shape parameter values.

0 0.25 0.5 0.75 1

0 0.25 0.5 0.75 1

Fig. 3.1. The Stancu polynomials of degree 3 with different values for the shape parameter α(solid: α= 0.1, dotted: α= 0.9).

4. STANCU CURVES

The present section contains the major results. We introduce the Stancu curve scheme which generalize the B´ezier curve scheme preserving all prop- erties which are vital for applications in curve design. Moreover, the Stancu curve scheme provides more flexibility for the designer by means of the shape parameterα. We will see later (see Section 6), that the shape parameter can be implemented in a transparent manner into a CAD system controlling the Stancu scheme.

In the rest of the paper, α is considered a nonnegative parameter. We denote by Pⁿ(R,R^m) the space of polynomials of degree at most n over R with values inR^m.

Definition 4.1. Let F ∈ Pⁿ(R,R^m) an arbitrary polynomial. The repre- sentation

(4.1) F =

n

X

i=0

P_iS_iⁿ,

where Pi ∈R^m, i= 0, . . . , n is called theStancu representation of the polyno- mialF on [0,1]. IfF admits such a representation, we say that the restriction of F to [0,1] defines a Stancu curve on [0,1] with the shape parameter α.

The points Pi, i= 0, . . . , nare the (Stancu) control pointsand they define the (Stancu) control polygon.

As with B´ezier curves, we have the following evaluation algorithm for Stancu curves.

Theorem4.2. (De Casteljau Algorithm)Consider the pointsP_j ∈R^m, j= 0, . . . , n, where n ∈ N, n6= 0. Define the points P_ij^k ∈R^m, i+j+k =n so that

(4.2) P_ij⁰ :=P_j, P_ij^k+1(x) := _1+(i+j)α^v+iα P_i+1,j^k (x) +_1+(i+j)α^u+jα P_i,j+1^k

fork= 0, . . . , n−1andx∈R. ThenP₀₀ⁿ(x)is a Stancu curve with the control points Pj, j= 0, . . . , n.

Proof. To show that P₀₀ⁿ is a Stancu curve, we must derive the represen- tation (4.1). We will show a bit more. We prove that the sums s_k(x) = P

i+j+k=nP_ij^k(x)S_j^n−k(x) do not depend onk= 0, . . . , n. Then we have s0(x) = ^X

i+j=n

P_ij⁰(x)Sⁿ_j(x) =

n

X

j=0

PjS_jⁿ(x), and s_n(x) = ^X

i+j=0

P_ijⁿ(x)S_j⁰(x) =P₀₀ⁿ(x).

The equality s0(x) =sn(x) gives the required representation.

To prove that the sumss_k(x) are all the same for anyk= 0, . . . , n, we start with

s_k(x) = ^X

i+j+k=n

P_ij^k(x)S_j^n−k(x)

= ^X

i+j+k=n

P_ij^k(x)^hv+(n−k−1−j)α

1+(n−k−1)α S_j^n−k−1(x) +_{1+(n−k−1)α}^u+(j−1)α S_j−1^n−k−1(x)ⁱ=

= ^X

i+j+k=n

P_ij^k(x)_{1+(i+j−1)α}^v+(i−1)α S_j^n−k−1(x) + ^X

i+j+k=n

P_ij^k(x)_{1+(i+j−1)α}^u+(j−1)α S_j−1^n−k−1(x).

Re-indexing the last sum we obtain s_k(x) = ^X

i+j+k=n−1

P_i+1,j^k (x)_1+(i+j)α^v+iα S_j^n−k−1(x)

+ ^X

i+j+k=n−1

P_i,j+1^k (x)_1+(i+j)α^u+jα S_j^n−k−1(x)

= ^X

i+j+k=n−1

h v+iα

1+(i+j)αP_i+1,j^k (x) +_1+(i+j)α^u+jα P^k(x)ⁱS_j^n−k−1(x).

Using (4.2) we have

s_k(x) = ^X

i+j+k+1=n

P_ij^k+1(x)S_j^n−(k+1)(x) =s_k+1(x).

The de Casteljau algorithm is conveniently represented as a triangle array of computations, as illustrated in Figure 4.1. The functions along the edges of this graph are the coefficients on the right-hand side of the formula (4.2).

Notice that if two arrows point into the same node, their labels sum to one. We can reverse the arrows in the triangle, place 1 at the apex of the triangle, run the computation downward and read the Stancu polynomials off the base of the triangle. This means that reversing the arrows, the triangle array represents the recursive computation formula (3.1) for the Stancu polynomials.

Forα= 0 both the recursive computation algorithm (3.1) for Stancu poly- nomials and the de Casteljau algorithm (4.2) for Stancu curves specialize to the Bernstein-B´ezier case.

t

t

t

t

t

t

t

t

t

t

A A A A A A K A A A A A A K A A A A A A K

A A A A A A K A A A A A A K

A A A A A A K

P₃₀⁰ =P0

P₂₀¹

P₁₀²

P₀₀³

P₂₁⁰ =P1

P₁₁¹

P₀₁²

P₁₂⁰ =P2

P₀₂¹

P₀₃⁰ =P3 v+2α

1+2α

v+α 1+α

v

v+α 1+2α

v 1+α

v 1+2α

u+2α 1+2α u+α

1+α

u

u+α 1+2α u

1+α

u 1+2α

Fig. 4.1. The de Casteljau algorithm for a cubic Stancu curve.

Other important properties for Stancu curve are listed by the following corollary and follow easily from the properties of the Stancu polynomials.

Corollary 4.3. (1) LetI_ij^k+1be the interval[−iα,1+jα], i+j+k=n.

In thek^th step, k= 0,1, . . . , n, of the de Casteljau algorithm the point P_ij^k+1 divides the interval J_ij^k+1 = [P_i+1,j^k (x), P_i,j+1^k (x)] exactly in the same ratio as the pointx divides the interval I_ij^k+1.

(2) Stancu curves are affine invariant.

(3) Stancu curves interpolate the end points of the control polygon, i.e.

P₀₀ⁿ(0) =P0 andP₀₀ⁿ(1) =Pn.

(4) Stancu curves are included in the convex hull of their control polygon.

If the blending functions for a curve scheme form a basis of the whole space Pⁿ(R,R^m) then any polynomial curve of degree at mostncan be represented as a curve belonging to the scheme. We will show now that the Stancu polyno- mials form indeed a basis for the space of polynomials of degree at mostn.

We recall from [3] the definition of P´olya polynomials, but see also [11], [1], and [2].

Definition 4.4. Let t₁, . . . , t_n be 2n real numbers such that t_i+n 6=t_j for 1 ≤ i ≤ j ≤ n (i.e. t₁, . . . , t_n is a progressive sequence). The n^th degree polynomials

(4.3) pⁿ_i(x) =

n+i

Y

j=i+1

(t_j−x), i= 0,1, . . . , n

are called the P´olya polynomials of degree n over the knot sequence ¯t :=

{t₁, . . . , t_n}.

The Stancu polynomials are special P´olya polynomials. More precisely, we have the following result.

Proposition 4.5. Denotet¯={t_j, j= 1, . . . ,2n}the knot sequence defined by

(4.4) t_j =

−(n−j)α, 1≤j ≤n 1 + (j−n−1)α, n+ 1≤j≤2n

Up to coefficients, the Stancu polynomials are the P´olya polynomials over the knot sequence ¯t, i.e.

(4.5) pⁿ_n−i= (−1)ⁱ

_n

i

S_iⁿ, i= 0,1, . . . , n.

Proof. We have successively S_iⁿ(x) =ⁿ_iu^[i]v^[n−i]=ⁿ_i

n−i−1

Q

j=0

(1 +jα−x)

i−1

Q

j=0

(jα+x)

= (−1)ⁱⁿ_i ^2n−iQ

k=n+1

(1 + (k−n−1)α−x)

n−i+1

Q

j=n

(−(n−j)α−x)

= (−1)ⁱⁿ_i ^2n−iQ

k=n+1

(t_k−x) ^Q

k=n−i+1

n(t_k−x)

= (−1)ⁱⁿ_i

2n−i

Q

k=n−i+1

(t_k−x) = (−1)ⁱⁿ_ipⁿ_n−i(x).

The P´olya polynomialspⁿ_n−i, i= 0,1, . . . , n form a basis forPⁿ(R,R^m) [2], [3]. Hence the following theorem holds.

Theorem 4.6. Every polynomial F ∈ Pⁿ(R,R^m) admits a Stancu repre- sentation F = ^Pn_i=0PiS_iⁿ, where Pi ∈ R^m, i = 0,1, . . . , n are the control points of the Stancu curve defined by F. Starting from the control points P_i, i= 0,1, . . . , n the de Casteljau algorithm (4.2) evaluates the Stancu curve defined by F at any point x∈[0,1].

5. DEGREE ELEVATION OF STANCU CURVES

The B´ezier curves admit a simple two-term degree elevation formula. Let B = ^Pn_i=0PiB_iⁿ, Pi ∈ R^m be a B´ezier curve of degree n, where B_iⁿ, i = 0,1, . . . , ndenotes the Bernstein polynomials of degree nover [0,1].

It is well known [6], [13] that the points ¯P_i, i= 0,1, . . . , n in the represen- tation B = ^Pn+1_i=0 P¯_iB_iⁿ⁺¹ of B as a B´ezier curve of degree n+ 1 are given by

(5.1) P¯i = _n+1ⁱ Pi−1+ 1−_n+1ⁱ Pi, i= 0,1, . . . , n+ 1.

In other words, holding the end control points fixed : ¯P₀ =P₀,P¯_n+1=P_n+1 and substituting then−1 inner control pointsPi, i= 1, . . . , n−1 bynpoints P¯i, i= 1, . . . , n with affine coordinates (_n+1ⁱ ,1−_n+1ⁱ ), i= 1, . . . , n, we obtain the control points of the same B´ezier curve considered now as an (n+ 1)^st degree curve. Note that the control points ¯Pi, i= 0,1, . . . , n+ 1 depend only on the order they appear in the sequenceP₀, . . . , P_n+1, i.e. only on the index i.

Despite of their greater flexibility provided by the shape parameter, the Stancu curves have, surprisingly, the very same two-term degree elevation for- mula as the B´ezier curves. The explanation consists in the fact that the Stancu polynomials have similar degree elevation formulae to those of Bernstein poly- nomials. One easily see that

u+(n−i)α

1+nα Sⁿ_i = _n+1ⁱ⁺¹ S_i+1ⁿ⁺¹, (5.2)

v+iα

1+nαSⁿ_i = ⁿ⁺¹⁻ⁱ_n+1 S_iⁿ⁺¹ (5.3)

and hence

(5.4) S_iⁿ= ⁿ⁺¹⁻ⁱ_n+1 Sⁿ⁺¹_i +_n+1ⁱ⁺¹ S_i+1ⁿ⁺¹

for i = 0,1, . . . , n. For α = 0 these formulae specialize to the well known degree elevation formulae for Bernstein polynomials:

u B_iⁿ= _n+1ⁱ⁺¹ B_i+1ⁿ⁺¹, (5.5)

v B_iⁿ= ⁿ⁺¹⁻ⁱ_n+1 S_iⁿ⁺¹, and respectively (5.6)

B_iⁿ= ⁿ⁺¹⁻ⁱ_n+1 B_iⁿ⁺¹+_n+1ⁱ⁺¹ B_i+1ⁿ⁺¹ (5.7)

fori= 0,1, . . . , n.

To establish the degree elevation formula for Stancu curves, consider the n^th degree Stancu curve S = ^Pn_i=0P_iS_iⁿ. Expressing S as a (n+ 1)^st degree curve we have ^Pn_i=0P_iS_iⁿ=^Pn+1_i=0 P¯_iS_iⁿ⁺¹.Observe that _1+nα^v+iα + ^u+(n−i)α_1+nα = 1 and use (5.4) to get

n

X

i=0

PiS_iⁿ=

n

X

i=0

PiSⁿ_i ^v+iα_i+nα+

n

X

i=0

PiS_i^nv+(n−i)α_1+nα

=

n

X

i=0

P_iⁿ⁺¹⁻ⁱ_n+1 S_iⁿ⁺¹+

n

X

i=0

P_in+1ⁱ⁺¹S_i+1ⁿ⁺¹

=

n

X

i=0

Pin+1−i

n+1 S_iⁿ⁺¹+

n+1

X

i=1

Pi−1 i n+1S_iⁿ⁺¹

=P₀S₀ⁿ⁺¹+

n

X

i=1

h i

n+1Pi−1+ 1− _n+1ⁱ P_iⁱS_iⁿ⁺¹+P_n+1S_n+1ⁿ⁺¹. The last equality yields

Theorem5.1. Let ^Pn+1_i=0 P¯iS_iⁿ⁺¹ be the expression of then^th degree Stancu curve S = ^Pn_i=0PiS_iⁿ as an (n+ 1)^st degree Stancu curve. Then P¯0 = P0, P¯n+1 =Pn+1 and

(5.8) P¯i = _n+1ⁱ Pi−1+ 1−_n+1ⁱ Pi, i= 1,2, . . . , n.

6. CHANGE OF BASIS AND THE DERIVATIVE OF STANCU CURVES

The B´ezier curves have a very simple derivative formula. Consider the B´ezier curveB =^Pn_i=0P_iBⁿ_i with the control points P_i ∈R^m, i= 0,1, . . . , n.

It is known [6], [13] that the derivative of the curveB is given by

(6.1) _dx^d B=n

n−1

X

i=0

(P_i+1−P_i)B_iⁿ⁻¹.

From here follows that at the point B(0) = P₀ the curve is tangent to the vectorP1−P0, and at the point B(1) =Pn the curve is tangent to the vector Pn−Pn−1.

Unfortunately there is no simple derivative formula for Stancu curves. The tangent vector at the first (last) control point depends not only on the first (last) two control points as in the case of B´ezier curves, but rather on all control points. To establish the formula for the tangent vectors at the end points of a Stancu curve we will first transform the Stancu curve into a B´ezier curve to obtain a relationship between the Stancu and the B´ezier control points. This relationships leads us then to the formula for the tangent vectors.

But first we start with the following result about the Stancu polynomials.

Theorem 6.1. Let S_iⁿ=ⁿ_iu^[i]v^[n−i], i= 0,1, . . . , n be the i^th Stancu poly- nomial of degree n and let α be positive. Then for any x∈[0,1]we have (6.2) _dx^dS_iⁿ(x) = _1+(n−1)αⁿ

ⁱ⁻¹ X

j=0

u+(i−1)α

i(u+jα) S_i−1ⁿ⁻¹(x)−

n−i−1

X

j=0

v+(n−i−1)α (n−i)(v+jα)S_iⁿ(x)

.

Proof. Clearly,

d

dxSⁿ_i(x) =ⁿ_iv^{[n−i] d}_dxu^[i]+u^{[i] d}_dxv^[n−i]. One can easily verify that

d dx

u^[i]=

i−1

P

j=0

u+(i−1)α u+jα u^[i−1]

and

d dx

v^[n−i]=−^i−1P

j=0

v+(n−i−1)α

v+jα v^[n−i−1], and hence

d

dxS_iⁿ(x) =ⁿ_i

Pi−1 j=0

u+(i−1)α

u+jα u^[i−1]v^[n−i]−

i−1

X

j=0

v+(n−i−1)α

v+jα v^[n−i−1]u^[i]

= n

i

n−1 i−1

i−1

X

j=0

u+(i−1)α

u+jα S_i−1ⁿ⁻¹(x)− n

i

n−1 i

i−1

X

j=0

v+(n−i−1)α

v+jα S_iⁿ⁻¹(x).

Simplifying and re-ordering the right-hand side of the last equality we obtain (6.2):

d

dxS_iⁿ(x) = i(1+(n−1)α)ⁿ i−1

X

j=0

u+(i−1)α

u+jα S_i−1ⁿ⁻¹(x)

−(n−i)(1+(n−1)α)ⁿ n−i−1

X

j=0

v+(n−i−1)α

v+jα S_iⁿ⁻¹(x)

= _1+(n−1)α^{n i−1}

X

j=0

u+(i−1)α

i(u+jα) S_i−1ⁿ⁻¹(x)−

n−i−1

X

j=0

v+(n−i−1)α

(n−i)(v+jα)S_iⁿ⁻¹(x)

.

For α= 0 the derivative formula for Stancu polynomials specializes to the derivative formula

d

dxBⁿ_i(x) =n^hB_i−1ⁿ⁻¹(x)−B_iⁿ⁻¹(x)ⁱ for Bernstein polynomials.

We now turn our attention to the topic of transforming the Bernstein basis B_iⁿ, i= 0,1, . . . , ninto the Stancu basisS_iⁿ, i= 0,1, . . . , n. Our aim is to find

a recurrence relation for the (n+ 1)×(n+ 1) matrixMⁿ=^hM_jiⁿⁱ such that

(6.3) S_iⁿ=

n

X

j=0

M_jiⁿB_jⁿ.

The following theorem re-establishes a known result [10] using only the definition of the matrixM and the recurrence formula (3.1) for Stancu curves.

Theorem 6.2. The transformation matrix Mⁿ from the B´ezier basis into the Stancu basis satisfies the following recurrence:

M_jiⁿ⁺¹= _n+1^{j h1+(i−1)α}_1+nα M_j−i,i−1ⁿ +^(n−i)α_1+nα M_j−1,i^{n i} (6.4)

+^n−j+1_n+1 ^h(i−1)α_1+nαM_j,i−1ⁿ +^1+(n−i)α_1+nα M_j,iⁿⁱ, where the entries M_klⁿ with k, l /∈ {0,1, . . . , n} are considered null.

Proof. By definition S_iⁿ⁺¹ =

n+1

X

j=0

M_jiⁿ⁺¹B_jⁿ⁺¹, i= 0,1, . . . , n+ 1.

Applying the recurrence formula (3.1) for Stancu polynomials to the right- hand side and using the definition of Mⁿ we get

Sⁿ⁺¹_i = ^u+(i−1)α_1+nα S_i−1ⁿ +^v+(n−i)α_1+nα S_iⁿ

= ^u+(i−1)α_1+nα

n

X

j=0

M_j,i−1ⁿ B_jⁿ+^v+(n−i)α_1+nα

n

X

j=0

M_j,iⁿB_j^b

=

n

X

j=0

h_u+(i−1)α

1+nα M_j,i−1ⁿ + ^v+(n−i)α_1+nα M_j,iⁿⁱB_jⁿ.

Using (5.5), (5.6) and (5.7) in the left-hand side of the last equality and re- grouping we have

S_iⁿ⁺¹=

n

X

j=0 j+1 n+1

h_1+(i−1)α

1+nα M_j,i−1ⁿ +^(n−iα_1+nαM_jiⁿⁱBⁿ⁺¹_j+1 +

n

X

j=0 n−j+1

n+1

h_(i−1)α

1+nαM_j,i−1ⁿ +^1+(n−i)α_1+nα M_jiⁿⁱB_jⁿ⁺¹.

Now changing the summation indexj toj+ 1 in the first sum, separating the term corresponding to j=n+ 1 in the first sum and the term corresponding toj= 0 in the second sum, and collecting all other term under the a common

sum symbol, we get the recurrence relation.

A very important property of the matrix Mⁿ is given by the next theorem.

We recall that a matrix [Aij]_n×nisstochasticprovided its elements are nonneg- ative and its rows form partitions of unity, i.e. ^Pn_j=0Aij = 1, i= 0,1, . . . , n.

Theorem6.3. (see also Example 6 in [10]) The transformation matrixMⁿ from the Bernstein basis into the Stancu basis is a stochastic matrix.

Proof. Forn= 0 the assertion is true. SupposeMⁿis stochastic. Using the recurrence of the matrixMⁿ we get successively

n+1

X

i=0

M_jiⁿ⁺¹ = _n+1^j

n+1

X

i=0

1+(i−1)α

1+nα M_j−1,i−1ⁿ + _n+1^j

n+1

X

i=0 (n−1)α

2+nα M_j−1,iⁿ +^n−j−1_n+1

n+1

X

i=0 (i−1)α

1+nα M_j−1,iⁿ +^n−j−1_n+1

n+1

X

i=0

1+(n−i)α 1+nα M_j,iⁿ, where the entries M_k,lⁿ with k, l /∈ {0,1, . . . , n} are considered null. Hence

n+1

X

i=0

M_jiⁿ⁺¹= _n+1^j

n+1

X

i=1

1+(i−1)α

1+nα M_j−1,i−1ⁿ +_n+1^j

n

X

i=0 (n−1)α

1+nα M_j−1,i−1ⁿ +^n−j−1_n+1

n+1

X

i=1 (i−1)α

1+nα M_j,i−1ⁿ +^n−j−1_n+1

n+1

X

i=1 (i−1)α

1+nα M_j,i−1ⁿ +^n−j−1_n+1

n

X

i=0

1+(n−i)α 1+nα M_j,iⁿ. Re-indexing we get

n+1

X

i=0

M_jiⁿ⁺¹ = _n+1^j

n

X

i=0

M_j−1,iⁿ +^n−j+1_n+1

n

X

i=0

M_jiⁿ = _n+1^j + ^n−j+1_n+1 = 1.

Now we are able to establish a derivative formula for Stancu curves.

Consider the Stancu curveS =^Pn_i=0P_iS_iⁿ and express the Stancu polyno- mials in the Bernstein basis using (6.3). Then

S =

n

X

i=0

P_i

n

X

j=0

M_jiⁿBⁿ_j =

n

X

j=0 n

X

i=0

M_jiⁿP_i

! B_jⁿ.

By the previous theorem the sum ^Pn_i=0M_jiⁿP_i is an affine combination of the Stancu control points Pi, i = 0,1, . . . , n, i.e. it defines a point Qj = Pn

i=0M_jiⁿP_i, j = 0,1, . . . , n in R^m. Clearly, Q_j, j = 0,1, . . . , n are the B´ezier control points for the Stancu curve S. We apply (6.1) to get a derivative formula:

d dxS=n

n−1

X

j=0

(Qj+1−Qj)Bⁿ⁻¹_j =n

n−1

X

j=0 n

X

i=0

M_j+1,iⁿ Pi−

n

X

i=0

M_jiⁿPi

! B_jⁿ⁻¹. This formula expresses the derivative of the Stancu curve S in terms of the Bernstein basis. One can convert the Bernstein polynomials back into the Stancu polynomials using the inverse of the matrix Mⁿ to obtain the derivative of the curveSin terms of Stancu polynomials. We will not perform

this transformation. Instead we turn to find an expression for the tangent vectors to the Stancu curveS at the end control pointsP₀ and P_n.

To this end, observe that P0 = Q0 and Pn = Qn by the interpolatory property of the Stancu and B´ezier curves. For the transformation matrix M_n this means that the first row is the vectorM_0,•ⁿ = (1,0, . . . ,0) and the last row is the vectorM_n,•ⁿ = (0, . . . ,0,1). Calculating the derivative of the curveS for x= 0 and x= 1 we obtain

d dxS

x=0=n

n

X

i=0

M_1iⁿP_i−P₀

!

and similarly

d dxS

x=1=n

n

X

i=0

M_n−1,iⁿ Pi−Pn

!

respectively.

We collect this result into the next theorem.

Theorem 6.4. Consider the Stancu curveS =^PnPiS_iⁿ and letMⁿ be the transformation matrix from the Bernstein basis {B_iⁿ, i= 0,1, . . . , n} into the Stancu basis{S_iⁿ, i= 0,1, . . . , n}. At the point corresponding to the parameter valuex= 0 the curveS is tangent to the vectorH₁−P₀, whereH₁ is the point having the affine coordinates (M₁₀ⁿ, . . . , M_1nⁿ) relative to the control points. At the point corresponding to the parameter valuex= 1 the curveS is tangent to the vector Hn−1−P_n, where Hn−1 is the point having the affine coordinates (M_n−1,0ⁿ , . . . , M_n−1,nⁿ ) relative to the control points.

Note that for a given set of control points the points H₁ and Hn−1 depend only on the shape parameter α. Hence, these points can be used ashandles to model the curve. Acting on this points the designer is able to modify (implicitly and transparently) the value of the shape parameter α, modifying thus the shape of the curve.

We illustrate this for a Stancu curve of degree 3. For the transformation matrix the recurrence formula (6.4) gives

M¹=

1 0 0 1

, M² =







1 0 0

α 2(1+α)

1 1+α

α 2(1+α)

0 0 1







and

M³ =













1 0 0 0

3α+4α² 3(1+2α)(1+α)

1 1+2α

α (1+2α)(1+α)

2α² 3(1+2α)(1+α) 2α²

3(1+2α)(1+α)

α (1+2α)(1+α)

1 1+2α

3α+4α² 3(1+2α)(1+α)

0 0 0 1











 .

For the cubic Stancu curve with fixed control pointsP0,P1,P2, andP3 the handle points H₁ and H₂ are then given by

H1 = 3(1+2α)(1+α)^3α+4α2 P0+_1+2α¹ P1+(1+2α)(1+α)^α P2+3(1+2α)(1+α)^2α2 P3

and respectively

H2 = 3(1+2α)(1+α)^2α2 P0+(1+2α)(1+α)^α P1+_1+2α¹ P2+ 3(1+2α)(1+α)^3α+4α2 P3. Figure 6.1 shows a cubic Stancu curve for different values of the shape parameterα.

P₀

H₁(0) =P₁ P₂

P₃ H1(0.3)

H₁(0.9)

Fig. 6.1. A Stancu cubic for different values of the shape parameterα

7. CONCLUDING REMARKS AND FUTURE WORK

We have considered a class of polynomial curves based on the Stancu polyno- mial operator, the Stancu curves. These curves have a simple explicit formula and simple recurrence formula for the blending functions. Additionally, the Stancu curves have a shape parameter which may allow a designer to manipu- late the shape of the curve without moving the control points, and to introduce such important effects as bias and tautness. These curves may be interesting for CAGD application. In some ways the Stancu curves are more flexible than the B´ezier curves and the author used successfully these curves in ornamental design applications.