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, on a vu en amphi qu'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, parametré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 (vu en amphi).
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-arete appartenant à la face qui contient p.

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

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");
    }