Mohammed AIRAJ

ENSAF/GSEII1
2023-2024

C++ : Mini-Projets
Projet : Class Complex et Class Point
Complément du cours:
Un opérateur de conversion peut être défini pour convertir des objets de classes dans un type fondamental ou dans un autre objet
de classe défini par l’utilisateur. Les prototypes suivants :

MyClass::operator int() const;

MyClass::operator OtherClass() const;

déclarent un opérateur de conversion, qui peut convertir un objet de MyClass en entier (Le premier prototype), ou en un objet de
OtherClass (le deuxième prototype).

1. Ecrire une classe Complex. La tester.

2. Se définir l’opérateur de conversion de la classe Complex → classe Point et réciproquement de la classe Point → classe
Complex et vérifier les deux conversions dans un programme principal Test.cpp.

3. Surdéfinir la méthode operator + dans la classe Complex et vérifier que les deux cas suivants marchent :

• Complex z3 = z1 + z2;
• Complex z4 = z1 + 1.f ;

(a) Pourquoi le dernier cas fonctionne ?

(b) Peut-on écrire Complex z5 = 1.f + z1 ?
(c) Quelle solution peut-on proposer ?

4. Allons plus loin, écrire un point comme la somme d’un complexe et d’un point et réciproquement un complex comme la
somme d’un complexe et d’un point.

5. Ecrire maintenant un point comme somme de deux points. Proposer une solution raisonnable pour les deux composants
Point et Complex.

6. Surdéfinir les méthodes operator - * /

7. Surdéfinir les operators de flux entrant et sortant, afin d’afficher et lire des complex.

8. Créer un tableau de Complex * dynamiquement, de dimension 3 et initialiser ce tableau et chaque sous-tableau (selon votre
imagination) de dimension 3.

Projet : Polynôme
 Introduction et notions de base

I.I. Introduction et notions de base

Notations On notera E 3 , l’espace affine euclidien tridimensionnel associé

à l’espace vectoriel euclidien tridimensionnel R3 .
Un élément de E 3 est appelé un point, un élément de R3 est appelé un vecteur
: a ∈ E 3 et b ∈ E 3 , b − a ∈ R3 .
E 3 est muni d’un repère orthonormé noté (O, i, j, k); (i, j, k) est une base or-
thonormée de R3 .
R3 est muni d’un produit scalaire noté ”.”, application de R3 × R3 dans R :

u(x, y, z) ∈ R3 et u! (x! , y ! , z ! ) ∈ R3 , u.v = xx! + yy ! + zz !

On associe à ce produit scalaire, une norme notée :

!
$u(x, y, z)$ = x2 + y 2 + z 2 .

La distance entre deux points a,b de E 3 est définie par $b − a$.

On notera:

• C k l’espace des fonctions k fois continûment dérivables.

• Pk l’espace des polynômes de degreé ≤ k de R dans R.
• Pk [a, b] l’espace des polynômes de degré ≤ k de [a, b] dans R.

Espace vectoriel des polynômes de degré ≤ k sur

R
On notera Pk espace vectoriel des polynômes de degré ≤ k, définis sur R et à
valeurs dans R.
k
"
p ∈ Pk ⇔ p(t) = a i ti , t ∈ R, {ai }i=k
i=0 ∈ R
k+1

i=0

Dimension Pk = k + 1.
Les applications f :
t ∈ R −→ ti , i ∈ [0, k]
constituent une base de Pk et est appelée base canonique de Pk ou base des
monômes.

1
*Règle de Hörner Soit
p(t) ∈ Pk , p(t) = a0 + a1 t + · · · + ai ti + · · · + ak tk .

On évalue p(t̄), t̄ valeur fixée de t, par l’algorithme suivant :

p(t̄) = t̄(t̄(· · · (t̄(ak t̄ + ak−1 ) + ak−2 ) · · ·) + a1 ) + a0

Soit, on initialise la valeur p = ak et on itère :

Pour i variant de k − 1 à 0 par pas de -1
p = pt̄ + ai
Coût du calcul : k multiplications et additions et k+1 affectations.

Interpolation polynomiale Dans ce paragraphe, on va s’intéresser

au problème suivant : Déterminer un polynôme interpolant passant un ensemble
de points donnés, c’est à dire :
Soient {ti }i=k i=k
i=0 une suite de réels distincts et {pi }i=0 une suite de réels quelcon-
ques. trouver le polynôme de degré k qui vérifie :

p(ti ) = pi , i = 0, · · · , k

Matrice de Vandermonde
Ce polynôme est unique et vérifie le système linéaire suivant :
k
"
aj tji = pi i = 0, · · · , k
j=0

La matrice associée à ce problème

 
1 t0 t20 · · · tk0
 1 t1 t21 · · · tk1 
 

[M ] =  · · · · · · · · · ··· ··· 

 ··· ··· ··· ··· ··· 
1 tk t2k · · · tkk

est appelée matrice de Vandermonde, son déterminant ∆ est égal à .

) )
) 1 t0 t20 · · · tk0 ))
)
) 1 t1 t21 · · · tk1 )) k−1 k
) * *
det[M ] = )) ··· ··· ··· · · · · · · )) = (tj − ti )
) ··· ··· ··· · · · · · · )) i=0 j=i+1
)
) 1 tk t2k · · · tkk )

2
et est donc différent de zéro si les valeurs ti sont distinctes.

Exemples:

k=1 ) )
) 1 t0 )
det[M ] = ) ) = t1 − t0
) 1 t1 )
k=2 ) )
) 1 t0 t20 )
) )
det[M ] = ) 1 t1 t21 ) = (t2 − t0 )(t2 − t1 )(t1 − t0 )
) )
) 1 t2 t22 )

Raisonnement intuitif : Si ti = tj les lignes i et j de la matrice [M] sont

identiques donc le déterminant est nul. Par conséquent

det[M ] = (ti − tj ) × · · ·

Si on balaye tous les couples (ti , tj ) de {ti }i=k

i=0 , on établit la formule.

Démonstration: D’abord, faisons des rappels sur le calcul des déterminants

de matrices carrées:
Soit [A] une matrice carrée n × n.

det[A]T = det[A]

1.
det[A]−1 =
det[A]

Posons
) )
) a1,1 a1,2 · · · a1,n )
) )
) a2,1 a2,2 · · · a2,n )
) )
det[A] = )) ··· ··· ··· ··· ) = ∆(a1 , a2 , · · · , ai , · · · , an )
)
) ··· ··· ··· ··· )
) )
) an,1 an,2 · · · an,n )

On a les relations suivantes :

∆(a1 , a2 , · · · , λai , · · · , an ) = λ∆(a1 , a2 , · · · , ai , · · · , an )

" n
∆(a1 , a2 , · · · , ai , · · · , an ) = ∆(a1 , a2 , · · · , ai + αj aj , · · · , an )
j=0,j#=i

3
Par conséquent, de la colonne j de la matrice [M] retranchons la colonne j-1
multipliée par t0 pour j variant de n à 2 et on obtient :
) )
) 1 0 0 ··· 0 )
) )
) 1 t1 − t0 (t1 − t0 )t1 · · · (t1 − t0 )tk−1 )
) 1 )
det[M ] = ∆(t0 , · · · , tk ) = )) · · · ··· ··· ··· ··· )
)
) ··· · · · · · · · · · · · · )
) )
) 1 tk − t0 (tk − t0 )tk · · · (tk − t0 )tk−1 )
k

Donc

k
* k−1
* k
*
det[M ] = ∆(t0 , · · · , tk ) = ∆(t1 , · · · , tk ) (ti − t0 ) = (tj − ti )
i=1 i=0 j=i+1

Remarque: Si on veut interpoler des points pi (xi , yi , zi ) de E 3 , on a trois

systèmes linéaire à résoudre
k
"
αj tji = xi , i = 0, · · · , k
j=0
k
"
βj tji = yi , i = 0, · · · , k
j=0
k
"
γj tji = zi , i = 0, · · · , k
j=0

On décomposera la matrice sous la forme LU (décomposition de Gauss) et

on aura trois systèmes triangulaires inférieurs et trois systèmes triangulaires
supérieurs à résoudre.

I. Ecrire la classe Polynome

Avec les attributs suivants:
• int degree ;
• int ordre ; // ordre = degree + 1
• double * A; // Coefficients du polynome, tableau, de dimension
ordre.
Et avec les méthodes suvantes:
• Le constructeur usuel de la classe Polynome dont le prototype est:
Polynome( int = 0 , double * = NULL )
• Le destructeur: ˜Polynome()
• Le constructeur par recopie:
Polynome(const Polynome &)

4
• L’opérateur d’affectation = :
Polynome & operator = ( const Polynome &)
• L’opérateur () qui renvoie la valeur du polynôme de la variable x
en utilisant la règle de Hörner:
double operator () ( double )
• L’opérateur + qui effectue la somme de deux polynômes.
Polynome operator + ( const Polynome & ) ;
• L’opérateur * qui effectue le produit de deux polynômes.
Polynome operator * ( const Polynome & ) ;
• Le constructeur d’interpolation qui calcule les coéfficients A[i] à
partir d’un tableau de double T, T[i] i=1,ordre , valeurs distinctes
et d’un tableau double B.On utilisera la classe Matrice, définie
dans le TP
Polynome( double * T, double * B) ;

5
 Projet sur les courbes de Bézier
Base de Bernstein

Définition 1. Considérons Pk[0, 1] l’espace des polynômes de degré ≤ k définis sur [0,1] et à
valeurs dans R.
Les fonctions définies par :

! " ! "  k!
k i k 0≤i≤k
Bik(t) = t (1 − t)k −i oú = i!(k − i)!
i i 
0 sinon

forment une base de Pk[0, 1].

1
Proposition 2. En posant

B00(t) ≡ 1 et B jk(t) ≡ 0, j [0.k].

Les fonctions Bik(t) satisfont à la relation de récurrence suivante :

Bik(t) = (1 − t)Bik−1(t) + t Bi−1

k−1
(t)

Démonstration:
Pour k = 1

B01(t) = 1 − t donc B01(t) = (1 − t)B00(t)

B11(t) = t donc B11(t) = t B00(t)

Montrons que c’ est vrai pour k quelconque.

! " ! " ! "
k k−1 k −1
= +
i i i−1

! "
k
Bik(t) = ti(1 − t)k −i
i
! " ! "
k −1 k−1
= i
t (1 − t)k−i
+ ti(1 − t)k −i
i i−1
! " ! "
k −1 k −1
= (1 − t) ti(1 − t)k −i−1 + t ti−1(1 − t)k−i
i i−1
Bik(t) = (1 − t)Bik−1(t) + t Bi−1 k−1
(t)

Proposition 3.

1. Bik(t) ≥ 0, ∀t ∈ [0, 1].

2. Les polynômes de Bernstein forment une partition de l’unité

k
&
Bik(t) = 1, ∀t![0, 1].
i=0

i
3. La fonction Bik(t) atteint son maximum en t =
k
d Bik(t) k −1
4. = k(Bi−1 (t) − Bik−1(t))
dt
5. Les polynômes de Bernstein sont symétriques en t et 1-t

k
Bik(t) = Bk−i (1 − t)

Démonstration:

1. Evident avec la relation de récurrence établie en proposition 1.

2. On utilise la formule du binôme de Newton.

k !
& " k
&
k
1 = (1 + t − t)k = ti(1 − t)k−1 = Bik(t)
i
i=0 i=0

2
 3. Dérivons Bik(t) :
! " ! "
d Bik(t) k i−1 k−i k
= i t (1 − t) − (k − i) ti(1 − t)k−1−i
dt i i
! "
d Bik(t) k
= ti−1(1 − t)k−1−i(i(1 − t) − (k − 1)t)
dt i
! "
d Bik(t) k
= ti−1(1 − t)k−1−i(i − t k)
dt i

d Bik(t) i
s’annule pour t = 0, t = 1 et t =
dt k
i
Bik(t) s’annule également pour t = 0, t = 1 et est positive, donc la valeur t = est bien un
k
maximum

4. Dérivons Bik(t) :
! " ! "
d Bik(t) k k
= i ti−1(1 − t)k−i − (k − i) ti(1 − t)k−1−i
dt i i
d Bik(t) k! k!
= ti−1(1 − t)k−i − ti(1 − t)k−1−i
dt (i − 1)!(k − i)! i!(k − i − 1)!
d Bik(t) k−1
= k(Bi−1 (t) − Bik−1(t))
dt

Courbes de Bézier

Définition 4. On appelle courbe de Bézier, associée au polygone de E 3: {Pi }i=k

i=0 ,
la courbe paramétrée définie par :


 &k



 x(t) = Bik(t)xi



 i=0
k
&  &k
γ(t) = Bik(t)Pi M (x(t), y(t), z(t)) ∈ γ(t) y(t) = Bik(t)yi


i=0 
 i=0

 &k



 z(t) = Bik(t)zi

i=0

avec Pi(xi , yi , zi) pour i = 0, k

Ces points Pi sont appelés points de contrôle ou pôles de la courbe γ(t).

Algorithme de De Casteljau

Exemple: Cas de la parabole

2
&
γ(t) = Bi2(t)Pi , P0, P1, P2 points de contrôle
i=0

P11(t) = (1 − t)P0 + t P1
P21(t) = (1 − t)P1 + t P2
P22(t) = (1 − t)P11(t) + t P21(t)
P22(t) = (1 − t)2P0 + 2(1 − t)t P1 + t2P2 = γ(t)

3
Algorithme général

Pi0(t) = Pi , i = 0, , k
Pir+1 = (1 − t)Pi−1
r
(t) + t Pir(t), i = r + 1, ,k r = 0, ,k −1

Pkk(t) est le point sur la courbe γ(t)

Démonstration: Montrons par un raisonnement par récurrence sur le degré r que:

r
&
Pir(t) = B jr(t)Pi−r+ j
j =0

Supposons que c’est vrai pour r et montrons que c’est également vrai pour r+1

Pir+1(t) = (1 − t)P r
(i−1 (t) + t Pir(t) ) ( r )
&r &
r+1 r r
Pi (t) = (1 − t) B j (t)Pi−1−r+ j + t B j (t)Pi−r+j
j =0 j =0
( r
) ( r+1 )
& &
Pir+1(t) = (1 − t) B jr(t)Pi−1−r+ j +t r
B j −1(t)Pi−r+ j −1
j =0
( r+1 ) ( jr+1
=1
)
r+1
& &
r r
Pi (t) = (1 − t) B j (t)Pi−1−r+ j + t B j −1(t)Pi−r+ j −1
j =0 j =0
r+1
&
Pir+1(t) = ((1 − t)B jr(t) + t B jr −1(t))Pi−r −1+ j
j =0
r+1
&
Pir+1(t) = B jr+1(t)Pi−r −1+ j
j =0

Propriétés

Remarque
k
&
Bik(t) ≥ 0 et Bik(t) = 1
i=0

par conséquent, chaque point de la courbe de Bézier, γ(t), est combinaison convexe des points
de contrôle Pi, affectés des poids Bik(t).

Proposition 5. Les courbes de Bézier possèdent les propriétés suivantes :

1. La courbe γ se trouve dans l’enveloppe convexe des points de contrôle Pi.

2. Invariance affine
φ application affine
k
& k
&
φ( Bik(t)Pi) = Bik(t)φ(Pi)
i=0 i=0

3. Invariance par transformation affine du paramètre

k
& k
& u−a
Bik(t)Pi = Bik( )Pi t ∈ [0, 1], u ∈ [a, b]
b−a
i=0 i=0

4
 4. Symétrie
k
&
γ(t) = Bik(t)Pi
i=0
k
&
k
γ(t) = Bk−i (1 − t)Pi
i=0
k
&
γ(t) = Bik(1 − t)Pk−i
i=0
s(t) = 1 − t
t(s) = 1 − s
γ " = γo t
&k
γ "(s) = Bik(s)Pk −i
i=0

Les courbes γ(t) et γ (s) sont identiques mais leur sens de parcours est différent.
"

γ(0) = P0
γ(1) = Pk
γ "(0) = Pk
γ "(1) = P0

Dérivation d’une courbe de Bézier

Dérivée première

k−1
& k−1
d γ(t)
Proposition 6. =k Bi (t)(Pi+1 − Pi)
dt
i=0

Démonstration:

d Bik(t) k −1
= k(Bi−1 (t) − Bik−1(t))
dt
&k
d γ(t) d Bik(t)
= Pi
dt dt
i=0
k
& k −1
= k(Bi−1 (t) − Bik −1(t))Pi
(
i=0
k k
)
& k −1
&
= k Bi−1 (t)Pi − Bik −1(t)Pi
( i=0 i=0 )
k
& k−1
&
k −1
= k Bi−1 (t)Pi − Bik−1(t)Pi
( i=1 i=0 )
k−1
& k
& −1
= k Bik −1(t)Pi+1 − Bik−1(t)Pi
i=0 i=0
k
& −1
= k Bik−1(t)(Pi+1 − Pi)
i=0

Dérivée d’ordre supérieur Définissons l’opérateur de différence avant :

∆Pi = Pi+1 − Pi
∆rPi = ∆(∆r −1Pi) = ∆r −1Pi+1 − ∆r −1Pi

5
Exemples

∆0Pi = Pi
∆1Pi = Pi+1 − Pi
∆2Pi = Pi+2 − 2Pi+1 + Pi
∆3Pi = Pi+3 − 3Pi+2 + 3Pi+1 − Pi

Soit
r
& ! "
r
∆rPi = ( − 1)r − j Pi+j
j
j =0

Proposition 7. La dérivée r-ième d’une courbe de Bézier s’écrit : En particulier pour t = 0 et

k
& −r
drγ(t) k!
= B jk −r(t)∆rP j
dt r (k − r)!
j =0
t = 1, on obtient :

drγ(0) k!
= ∆rP0
dt r (k − r)!
drγ(1) k!
= ∆rPk −r
dt r (k − r)!
d γ(0)
= k(P1 − P0)
dt
d γ(1)
= k(Pk − Pk−1)
dt

Algorithme d’élévation du degré

Soit une courbe de Bézier γ(t), exprimée dans la base de Bernstein de degré k (Bik(t), i = 0, , k)
on aimerait l’exprimer dans la base (Bik+1, i = 0, , k + 1), autrement dit, élever son degré de k à
k + 1.
k
& k+1
&
γ(t) = Bik(t)Pi = Bik+1(t)P̂i
i=0 i=0

Par conséquent, trouvons une relation entre les points Pi , i = 0, , k et P̂i , i = 0, ,k+1

k !
& " & ! k+1 "
k+1
k i k−i
t (1 − t) Pi = ti(1 − t)k+1−iP̂i
i i
i=0 i=0

Multiplions le terme de gauche par t + (1 − t)

k !
& "
k
(ti+1(1 − t)k−i + ti(1 − t)k+1−i)Pi
i
i=0

On obtient si on identifie les coefficients de ti(1 − t)k+1−i

! " ! " ! "

 k+1 k k

 P̂ i = P i + Pi−1, i = 1, ,k
i i i−1

 P̂0 = P0


P̂k+1 = Pk

k + 1! k! k!
P̂i = Pi + Pi−1
i!(k + 1 − i)! i!(k − i)! i − 1!(k − i − 1)!

6


 i i

 P̂i = Pi−1 + (1 − )Pi , i = 1, ,k
k+1 k+1

 P̂0 = P0

 P̂
k+1 = Pk

Problème d’interpolation
i=k
On se donne une suite de points {Qi }i=0 , on veut définir la courbe de Bézier qui passe par ces
points.
Il faut se définir une paramétrisation {ti }i=k
i=0 de la courbe à partir des points donnés et le prob-
lème à résoudre est le suivant:
k
&
Bik(t j )Pi = Qj pour j = 0, ,k
i=0

On a le choix pour définir la suite {ti }i=k

i=0

Par exemple on choisit t0 = 0 et ti+1=ti+distance(Qi+1, Qi).

Soit M la matrice de Bernstein de coefficient Mij=Bik(t j ) le problème revient à résoudre les trois
systèmes linéaires suivants:
MP = Q , systèmes linéaires en x,y,z

Problème des moindres carrés.

Le nombre de points doit être égal à degré +1 et on peut pas augmenter indéfiniment le degré
de la base de Bernstein.
Si le nombre de points n+1 > degré k + 1, on a trois systèmes à n+1 équations pour k + 1
inconnues.
Pour un grand nombre de points le problème d’interpolation est à remplacer par le problème de
minimisation suivant:
Etant donnés n+1 points Q j , trouver les points Pi pour i = 0, , k qui minimisent:
* k
n *&
*2
& *
* *
* Bik(t j )Pi − Qj*
* *
j =0 i=0

Ce problème est équivalent à résoudre les trois systèmes linéaires suivants:

MMP =t MQ en x,y,z et on a trois systèmes en x, y et z à k+1 équation
t

pour k + 1 inconnues.

I. Ecrire la classe CourbeBezier

On utilisera les classes Vecteur et Matrice du TP2.

La classe CourbeBezier possède les attributs suivants:
int Degre ;
int Dimension;
int Ordre; // = Degre+1
Vecteur Poles[3] // Le vecteur Poles[0] contient les abscisses des points de contrôle.
// Le vecteur Poles[1] contient les ordonnées des points de contrôle.

7
 // Le vecteur Poles[2] contient les cotes des points de contrôle.

• Ecrire le construteur avec les arguments suivants:

CourbeBezier( int=0 ,int=0 , Vecteur P[ ]=NULL );

• Ecrire un deuxième construteur avec les arguments suivants:

CourbeBezier( int , int , double P[ ][3] );

• Ecrire la méthode qui applique l’algorithme de de Casteljau

void Evalue( double , double A[ ] ) const ;

• Surdéfinir l’opérateur '

friend ostream & operator ' ( ostream & , const CourbeBezier & ) ;

II. La classe ConstruitCourbe

La classe ConstruitCourbe possède les attributs suivants:

int NbPoints; // Points donnés pour construire la courbe de Bézier.
int Degre; // Le degré de la courbe à constuire.
double * Param; // Les paramètres pour définir le système à résoudre.
Matrice M; // La matrice associée au système à résoudre.
CourbeBezier aBezierCourbe; // La courbe résultante.

• Ecrire les méthodes privées suivantes:

void ConstruitParametres( Vecteur V[] ) ;

qui calcule les paramètres associés aux Nbpoints points donnés du problèmes.

double EvalBernstein(int , int , double); // int i , int k double t

qui calcule la valeur de Bik(t) en utilisant la formule de récurrence:
Bik(t) = (1 − t)Bik −1(t) + t Bi−1
k−1
(t)
void ConstruitMatriceBernstein();
qui construit la matrice M de Bernstein.
et les méthodes publiques constructeur et destructeur:
ConstruitCourbe( int , int , int , Vecteur V[] ) ; // dimension, nombre de points, degré et
points donnés.
qui résout le problème d’interpolation.
~ConstruitCourbe() ;
et enfin surdéfinir l’opérateur operator CourbeBézier();

• Ecrire les méthodes privées suivantes:

void ConstruitMoindresCarresMatrice() ;
qui construit la matrice des moindres carrés associée à la matrice de Bernstein.
Vecteur SecondMembre(Vecteur) ;
qui calcule le second membre associé au système des moindres carrés.
Il faudra adapter le constructeur pour qu’il puisse traiter les deux problèmes suivants
NbPoints > Degre +1 ou égal.