Rapport de Projet - Plantation et Gestion
d'Arbres avec Triangulation de Delaunay
JEREMY BEZIE L2 SNIO Page 1
Introduction
Portée du projet
L’objectif principal du projet est de développer un logiciel en
langage C permettant de gérer la plantation d’arbres sur un sol
représenté par un plan 2D. Ce projet s’appuie sur l’utilisation
des listes doublement chaînées pour stocker dynamiquement
les positions des arbres et des triangles obtenus à partir de ces
points. Le programme doit répondre aux besoins suivants :
● Positionner des arbres sur un plan interactif.
● Construire une triangulation respectant les règles de
Delaunay.
● Planter dynamiquement des arbres dans les zones
disponibles.
● Supprimer les arbres situés dans des zones trop denses.
● Mettre à jour dynamiquement la triangulation à chaque
modification (ajout ou suppression).
Ce programme est conçu pour fonctionner de manière
interactive jusqu’à ce que le sol soit saturé.
JEREMY BEZIE L2 SNIO Page 2
Analyse du projet
Objectifs spécifiques
● Positionner dynamiquement des arbres en utilisant une
interface interactive sur une zone donnée en générant une
liste de points représentant leurs positions.
● Construire une triangulation de Delaunay à partir de cette
liste pour relier les arbres et identifier les zones
disponibles.
● Planter dynamiquement de nouveaux arbres dans les
triangles les plus grands où de l’espace est disponible.
● Permettre la suppression d’arbres en détectant ceux qui
sont « trop serrés ».
Contraintes
- Le logiciel doit utiliser des listes doublement chaînées
pour stocker les données dynamiques (points et triangles).
- Le programme doit afficher les résultats dans une
interface console sous forme graphique simple en
représentant les arbres par des symboles *.
- Les triangles doivent respecter les règles géométriques
de la triangulation de Delaunay aucun point ne doit être à
l’intérieur du cercle circonscrit d’un triangle.
Simplifications possibles
- Affichage console : La représentation graphique utilise
uniquement du texte. Une interface graphique pourrait
rendre le projet plus visuel.
JEREMY BEZIE L2 SNIO Page 3
- Itérations limitées : Le processus de plantation d’arbres
s’arrête lorsque le sol est saturé ou qu’aucune nouvelle
plantation n’est possible.
Conception
Découpage fonctionnel
-Positionnement des arbres
○ L’utilisateur positionne des arbres en saisissant des
commandes.
○ Les positions des arbres sont stockées dans une liste
doublement chaînée de points.
○ Un affichage visuel en console représente les arbres
sous forme de *.
-Construction de la triangulation de Delaunay
○ À partir de la liste des positions des arbres, des
triangles sont générés dynamiquement.
○ La triangulation de Delaunay garantit que :
○ Chaque triangle respecte la condition du cercle
circonscrit (aucun point ne se trouve dans le cercle
des triangles voisins).
○ Les triangles sont également stockés dans une liste
doublement chaînée. Un algorithme vérifie que les
arbres respectent une distance minimale pour éviter
les plantations trop proches.
-Plantation d’arbres dans les triangles
JEREMY BEZIE L2 SNIO Page 4
○ Les triangles ayant une surface suffisante pour
accueillir de nouveaux arbres sont identifiés.
○ Un nouvel arbre est ajouté au barycentre (centre
géométrique) du triangle le plus grand. La formule du
y 1+ y 2+ y 3
barycentre est : B(x,y)= ¿, 3 )
○ Après chaque plantation, la triangulation est mise à
jour pour inclure le nouvel arbre.
○ Ce processus est itératif jusqu’à saturation du sol.
-Suppression des arbres trop serrés
○ Les arbres situés dans des zones où ils sont trop
proches les uns des autres sont identifiés.
○ Ces arbres sont supprimés dynamiquement de la liste
des points.
○ La triangulation est recalculée après chaque
suppression pour garantir la cohérence géométrique.
Principes de fonctionnement
Interaction utilisateur :
○ L’utilisateur interagit avec le programme via des
commandes textuelles pour générer, ajouter ou
supprimer des arbres.
Traitement des données :
JEREMY BEZIE L2 SNIO Page 5
○ Les arbres sont représentés par des points dans une
liste chaînée.
○ Les triangles sont construits à partir de ces points
selon les règles de la triangulation de Delaunay.
Mise à jour dynamique :
○ Chaque ajout ou suppression d’arbre déclenche un
recalcul de la triangulation pour s’assurer de la
validité des triangles.
Tests
Tests unitaires
○ Génération des points : Vérifier que les arbres
respectent la distance minimale.
○ Triangulation : Valider que chaque triangle respecte
la condition du cercle circonscrit.
○ Ajout d’arbres : Tester l’ajout d’un arbre au
barycentre du plus grand triangle.
Tests d’intégration
1. Génération + Triangulation :
○ Vérifier que la triangulation est correcte après la
génération des arbres.
2. Ajout/Suppression d’arbres :
○ Contrôler que les opérations d’ajout et de
suppression mettent correctement à jour la
triangulation.
JEREMY BEZIE L2 SNIO Page 6
Résultats
1. Positionnement des arbres :
○ Les arbres sont positionnés dynamiquement sur un
sol représenté dans la console.
2. Triangulation de Delaunay :
○ Les triangles sont construits avec succès en
respectant les règles géométriques.
○ Les plus grands triangles sont identifiés pour
accueillir de nouveaux arbres.
3. Plantation d’arbres :
○ Des arbres supplémentaires sont ajoutés au
barycentre des triangles les plus grands.
○ Le programme itère jusqu’à saturation du sol.
4. Suppression d’arbres :
○ Les arbres situés dans des zones trop denses sont
identifiés et supprimés.
○ Le recalcul de la triangulation est effectué après
chaque suppression.
Perspectives
Limites du projet
● L’affichage en console reste rudimentaire et ne permet
pas une représentation graphique détaillée.
● La performance du programme peut être impactée pour
un grand nombre d’arbres en raison des calculs fréquents
de la triangulation.
JEREMY BEZIE L2 SNIO Page 7
Améliorations possibles
1. Utilisation d’une interface graphique pour améliorer la
représentation visuelle des points et triangles.
2. Optimisation des algorithmes pour améliorer les
performances du recalcul de la triangulation.
3. Ajout d’interactions utilisateur avancées comme
l’utilisation de la souris pour sélectionner et gérer les
arbres.
Conclusion
Ce projet aboutit à la réalisation d’un logiciel interactif en
langage C capable de gérer dynamiquement la plantation et la
suppression d’arbres sur un plan 2D, en s’appuyant sur la
triangulation de Delaunay et l’utilisation des listes doublement
chaînées.
Le programme remplit ses objectifs en permettant :
● Une gestion optimisée des positions des arbres.
● La construction et la mise à jour dynamique d’une
triangulation garantissant une représentation
géométrique cohérente.
● L’ajout automatique d’arbres dans les zones disponibles
tout en respectant des contraintes spatiales.
● La suppression des arbres trop serrés, assurant ainsi un
équilibre entre densité et espace libre.
JEREMY BEZIE L2 SNIO Page 8
Malgré un affichage en mode console simplifié, ce projet
constitue une base fonctionnelle solide qui démontre l’intérêt
des structures de données dynamiques pour résoudre des
problèmes géométriques complexes.
Références
1. Études sur la triangulation de Delaunay et la géométrie.
2. Documentation sur les listes doublement chaînées en
langage C.
3. Cours sur l’algorithmique et les structures de données
dynamiques.
JEREMY BEZIE L2 SNIO Page 9
