TD 1 - Mise en route (la géométrie algorithmique en Java)
Le but de ce premier TD est de se
familiariser avec la librairie Jcg, et ses structures de données
et primitives géométriques.
Avant de
commencer, il faut installer et configurer la librairie Jcg, comme
expliqué ci-dessous.
On rappelle que la documentation de la bibliothèque Jcg
se
trouve ici. N'hésitez
pas à vous y référer
régulièrement !
Dans cet exercice on vous demande d'implémenter l'algorithme de balayage vu en cours pour le calcul des enveloppes convexes dans le plan. Une fois terminé, vous pourrez aussi implémenter l'algorithme du paquet-cadeau.
Voici une solution
Cet exercice introduit une
structure de données fondamentale en géométrie algorithmique,
connue sous le nom de
Half-edge,
qui permet de représenter des surfaces combinatoires orientables,
triangulées ainsi que polygonales. En particulier, on se servira
des opérations élémentaires de navigation dans un maillage afin
d'implémenter un algorithme simple pour calculer l'ensemble des faces d'un maillage triangulaire
qui sont intersectées par un hyperplan choisi de manière aléatoire.
Dans cet exetrcice on se servira
des opérations élémentaires de navigation fournies par
Half-edge
afin d'implémenter un algorithme simple de localisation d'un point dans
un maillage planaire.
Voici deux exemples d'éxécution de l'algorithme de localisation
dans une triangulation basé sur une marche aléatoire.
