TD 1 - Planar point location

Localisation dans une triangulation planaire

Maintenant on va se familiariser avec des objets géométriques plus structurés, tels que les maillages. En particulier, le but de cette partie est de vous illustrer le fonctionnement de la classe Polyhedron_3, permettant de représenter des maillages surfaciques (orientables).

Du point de vue combinatoire, une surface combinatoire de genre 0 correspond à un graphe planaire: c'est aussi pour cette raison que la classe Polyhedron_3 est une classe générique, paramétrée par le type de point qu'on veut associer au sommet du maillage, ce qui en java se traduit par:

Polyhedron_3<X extends Point_>

Localisation par marche aléatoire

Ici on vous demande d'implanter l'algorithme de localisation dans une triangulation planaire basé sur une marche aléatoire (voici un transparent d'explication). On part d'un point q choisi au hasard dans la triangulation et on trace le segment (pq), où p est le point qui doit etre localisé.

But: écrire un programme qui permet de localiser p dans la triangulation
Sortie de la méthode de localisation: une demi-arête appartenant à la face qui contient p.

Encore une fois on met à votre disposition le squelette de la classe PointLocation_RandomWalk dans le fichier qui contient les signatures des méthodes à compléter, ainsi qu'une fonction main qui permet de tester votre code (une fois écrit).

Fichiers à télécharger et documentation pour cet exercice:

Voici des slides avec une présentation succincte des structures de données utilisées pour représenter des maillages,
Des données pour tester votre programme: une triangulation de Delaunay au format OFF (une autre). Remarque: n'oubliez pas de les placer dans le bon répertoire ( /data, à la racine du projet TD1)
Le squelette à compléter: PointLocation_RandomWalk.java.

Tester le code et la librairie:

Exécutez la fonction main de la classe PointLocation_RandomWalk: vous devriez voir s'ouvrir une fenêtre qui affiche une triangulation, et un message à la console comme ci-dessous:

...
...
Checking Polyhedron...ok
Closed mesh: no boundaries
The mesh is pure triangle
n: 103  e: 303  f: 202 - genus: 0
Checking Polyhedron...ok
Mesh with boundaries
The mesh is pure triangle
n: 103  e: 303  f: 201 - genus: 0
Exception in thread "main" java.lang.Error: a completer
	at PointLocation_RandomWalk.getRandomPoint(PointLocation_RandomWalk.java:30)
	at PointLocation_RandomWalk.main(PointLocation_RandomWalk.java:99)

Conseil: voici quelques unes des classes et méthodes dont vous aurez besoin dans cet exercice:

Point_2 (dans le package Jcg.geometry): implémente les fonctions necessaires à manipuler des points en 2D (à coordonnées réelles, double)
Fenetre: pour visualiser un ensemble de points et segments
GeometricOperations_2 (dans Jcg.geometry): qui fournit un certain nombre de predicat géométriques (par exemple un prédicat pour tester l'orientation d'un triangle)

Dans le fichier PointLocation_RandomWalk.java, vous avez aussi une méthode permettant de charger en mémoire une triangulation planaire pour tester votre code.

Conseil: vous pouvez procéder à la solution de cet exercice en complétant, étape par étape, les différentes fonctions fournies dans le fichier .java ci-dessus.
Comme expliqué par exemple par:

    /**
     * Compute and return the barycenter point of a given face
     */    
    public static Point_2 createCenterVertex(Face<Point_2> f){
    	//throw new Error("a completer: etape 1");
    }