TD 1 - Mise en route (la géométrie algorithmique en Java)


Votre opinion sur le cours :
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.


0.  Installation et configuration de Jcg

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 !

1. Convex Hull 2D

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

2.a Mesh collision

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.



2.b Localisation planaire

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.




Voici une solution