Tracé d’une courbe de Bézier par l’algorithme de Casteljau

Gérard GRANCHER

Laboratoire de Mathématiques Raphaël Salem CNRS - Université de Rouen

Propriétés Théorème 1 Soit (P_{i})_{0≤i≤n} la suite des n + 1 points de définition de (C), une courbe de Bézier. Soit, pour tout t, la suite (doublement indicée pour 0 ≤ k ≤ n et 0 ≤ j ≤ n − k) des points P_{j}^{(k)}(t) définis par P_{j}^{(0)}(t) = P_{j} et

\overrightarrow{OP_{j}^{(k)}}(t) = (1 − t)\overrightarrow{OP_{j}^{(k−1)}}(t) + t\overrightarrow{OP_{j+1}^{(k−1)}}(t) Alors on a pour tout t tel que t ∈ [0, 1] P_{0}^{(n)}(t) = M(t) où M(t) est le point courant de (C). L’algorithme de Casteljau est fondé sur le théorème cidessus.

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.1

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2

Démonstration du théorème

On a

\overrightarrow{OM}(t) = ∑_{i=0}^{n} B_{n}^{i}(t)\overrightarrow{OP_{i}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + [∑_{i=1}^{n−1} \binom{n}{i}(1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}}] + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n}\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} [\binom{n − 1}{i} + \binom{n − 1}{i − 1}] (1 − t)^{n−i}t^{i}\overrightarrow{OP_{i}^{(0)}} + t^{n}\overrightarrow{OP_{n}^{(0)}}

= (1 − t)^{n−1}(1 − t)\overrightarrow{OP_{0}^{(0)}} + ∑_{i=1}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}}

+ ∑_{i=1}^{n−1} \binom{n − 1}{i − 1}(1 − t)^{n−i}t^{i−1}t\overrightarrow{OP_{i}^{(0)}} + t^{n−1}t\overrightarrow{OP_{n}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}(1 − t)\overrightarrow{OP_{i}^{(0)}} + ∑_{i=1}^{n} \binom{n − 1}{i − 1}(1 − t)^{n−1−(i−1)}t^{i−1}t\overrightarrow{OP_{i}^{(0)}}

= ∑_{i=0}^{n−1} \binom{n − 1}{i}(1 − t)^{n−1−i}t^{i}((1 − t)\overrightarrow{OP_{i}^{(0)}} + t\overrightarrow{OP_{i+1}^{(0)}})

= ∑_{i=0}^{n−1} B_{n−1}^{i}(t)\overrightarrow{OP_{i}^{(1)}}

Ainsi, après n itérations, on obtient : \overrightarrow{OM}(t) = \overrightarrow{OP_{0}^{(n)}}(t).

Tracé d’une courbe de Bézierpar l’algorithme de Casteljau – p.2