Projet Informatique
Contents
1. if tt tk null Point ck tt tk retourneCentre g drawLine int c x int c y int ck x int ck y if tt ti null dessinerVoronoi tt ti g if tt tj null dessinerVoronoi tt tj g if tt tk null dessinerVoronoi tt tk g public void dessinerCercles Triangle tt Graphics g if tt null tt estDessine true return g setColor Color RED tt estDessine true if I tt i 0 tt j 0O tt k O tt i 1 tt j 1 tt k 1 tt j 2 tt j 2 tt k 2 j Point c tt retourneCentre Point a tt points tt i double r Math sqrt a x c x a x c x a y c y a y c y g drawOval int c x r int c y r int 2 r int 2 r dessinerCercles tt ti g dessinerCercles tt tj g dessinerCercles tt tk g public void dessinerTriangles Triangle tt Graphics g I if tt null tt estDessine true return g setColor Color BLACK tt estDessine true if I tt i 0 tt j 0O tt k O tt i 1 tt j 1 tt k 1 tt j 2 tt j 2 tt k 2 Point a tt points tt i Point b tt points tt j Point c tt points tt k g drawLine int a x int a y int b x int b y g drawLine int b x int b y int c x int c y g drawLine int c x int c y int a x int a y dessinerTriangles tt ti g dessinerTriangles tt tj 22. Ad N K AA pr die TR ZIE Deuxi me m thode La seconde est d utiliser l interface graphique qui permet de saisir les points la souris Pour l utiliser il suffit de taper gt java Delaunay Les dimensions de la fen tre sont alors celles par d faut Pour les pr ciser on tape gt java Delaunay 600 800 pour avoir une fen tre de hauteur 600 et de largeur 800 En voici une illustration en image Fichier Dessin Nombre Effacer les triangles Effacer Voronoi Afficher les cercles circonscrits Effacer arbre couvrant minimal Vous pouvez constater la pr sence de menus Le menu Dessin gt permet de choisir les objets afficher triangles cercles circonscrits diagramme de Voronoi et arbre couvrant minimal Quant au menu Fichier il permet de recommencer au d but l insertion de points de sauvegarder en postscript la triangulation et de fermer le programme En bas de la fen tre le champ texte permet de choisir le nombre total de point que l on souhaite pouvoir ins rer Celui ci doit tre connu au d but de la triangulation et ne peut tre modifi sous peine d effacer la triangulation Quelques raccourcis clavier gt lq permet de quitter le programme gt ln permet d effacer la triangulation IA Annexe 2 Listing du code La classe Point class Point double x double y public Point double x double y this
3. liste ListeSegment ajouter liste s void supprimer int i liste supprimerAux liste i static ListeSegment supprimerAux ListeSegment IL int i if null return null IR else if Ul val a i U val b i return supprimerAux ll suite i else return new ListeSegment ll val supprimerAux ll suite i Segment retourneMinimum renvoie le segment de longueur minimum dont celui a ajouter if liste null throw new Error Queue vide impossible de retourner un minimum return liste val La classe ListeSegment class ListeSegment liste croissante de segments Segment val ListeSegment suite ListeSegment Segment val this val val ListeSegment Segment val ListeSegment suite this val val this suite suite j public static ListeSegment ajouter ListeSegment ll Segment s cette m ethode permet d ajouter en maintenant le liste tri ee if ll null return new ListeSegment s if s longueur lt ll val longueur return new ListeSegment s 0 else return new ListeSegment ll val ajouter ll suite s La classe Segment class Segment int a int b double longueur 20 Segment int aa int bb double dy a aa b bb longueur d j void print System out println a b de longueur longueur La classe ListeEntier class ListeEntier int val ListeEntier suite Li
4. N il f EX A EN VZ AAA Ir p j Y x N EF VA I Da SSI jf a Sn B On pose a l angle tel que T soit l ensemble des points tels que AMB a si M est dans le m me demi plan que C ou tel que AMB n a si M est dans le m me demi plan que D On pose a langle tel que ACB a Le cercle circonscrit ACB est l ensemble des points tels que AMB a si M est dans le m me demi plan que C ou tels que AMB t a si M est dans le m me demi plan que D C tant ext rieur T on a lt a On a alors ADB lt T a lt T a et donc D est ext rieur au cercle circonscrit ACB Par 1 on en d duit que C est ext rieur au cercle circonscrit ABD D monstration du lemme 3 Le sens indirect r sulte de la d finition de la triangulation de Delaunay Sens direct consid rons une ar te AB telle qu il existe un cercle passant par ses extr mit s en ne contenant pas de points de S Supposons qu elle ne soit pas de Delaunay Par convexit de la triangulation elle coupe un segment CD tel que ACD appartienne la triangulation Du lemme 4 on d duit que ABC et ABD poss dent la propri t de Delaunay Or ACD est un triangle de la triangulation Il poss de donc lui aussi cette propri t ce qui contredit le lemme 5 L ar te AB est donc de Delaunay D o le lemme 3 D monstration du lemme 2 Soit AB la plus courte ar te d un point de 1 un point de S
5. aux suivant 2 return c1 j public void print for Cavite cs this cs null cs cs suivant System out print cs a cs b if cs tExt null System out print triangle exterieur cs tExt print else System out println triangle exterieur null j La classe Graphe class Graphe Point coords ListeEntier voisins boolean estDejaAjoute permet d eviter d ajouter plusieurs fois la m me ar te Graphe Point points int nb voisins new ListeEntier nb coords new Point nb int n coords length for inti 0 i lt n i coords i points i 3 estDejaAjoute new boolean nb nb j public void ajouter int i int j if i gt 2 amp amp j gt 2 amp amp lestDejaAjouteli 3 j 3 estDejaAjouteli 3 j 3 true estDejaAjoute j 3 i 3 true voisins i 3 new ListeEntier j 3 voisins i 3 voisins j 3 new ListeEntier i 3 voisins j 3 24 j public Arbre calculerArbre inti 1 int n 1 correspond au nb de points d ej a ajout es QueueListe q new QueueListe coords length coords q ajouter 0 voisins Segment s Arbre res null while n lt coords length amp amp q liste null s q retourneMinimum if q estAjoute s a amp amp q estAjoute s b I q ajouter s b voisins else if Iqg estAjoute s a amp amp q estAjoute s b q ajouter s a voisins else throw new Error segment min
6. A Pointeurs modifi s Point Pl ins rer I P l t 7 al J 20 Bilan Apr s ces quelques critiques sur notre algorithme nous pouvons tout de m me consid rer que notre impl mentation reste valable sachant que pour un ensemble de points donn s en cas de probl me de convexit de la triangulation obtenue il est toujours possible d augmenter la taille du triangle initial jusqu r solution du probl me 91 Annexe 1 Manuel d utilisation Il existe deux fa on de faire fonctionner le programme Premi re m thode La premi re est de fournir en entr e du programme un fichier texte contenant une liste de points Chaque ligne de ce fichier contient l abscisse et l ordonn e d un point Exemple d un fichier input txt 62 1155 83 4814 55 0049 377 853 514 752 610 353 239 056 116 934 237 073 560 439 162 64 6 93 529 227 307 395 033 375 592 123 253 La triangulation s effectue alors en tapant la ligne de commande gt java Triangulation lt input txt La triangulation est alors crite en postscript dans un fichier nomm par d faut loutput ps 99 Exemple de r sultat avec le fichier d environ 800 points fourni avec le code TTT ETES RES ER T SS RANCE TT N FN NS SIS VA gt y VA Pasi PENE EN DAN Q L RELY VALNIS TIA Kl 7 ARRET SSSR GENRER RSA 7 S NSR EZ AN NA KS ON SEE
7. dessinerTriangles tt tk g A7 j public void restore Triangle tt if tt null amp amp tt estDessine tt estDessine false restore tt ti restore tt tj restore tt tk public void redessiner clear true L setText Veuillez saisir les points a la souris t new Triangulation Delaunay NB_POINTS Delaunay LARGEUR Delaunay HAUTEUR repaint Liste des methodes du MouseListener public void mouseClicked MouseEvent e if Triangle nb 1 gt Delaunay NB_POINTS l setText Triangulation termin ee else int x e getX int y e getY clear false Point pt new Point double x double y System out println Ajout de pt t ajouter pt L setText Nombre de points restants a placer Delaunay NB_POINTS Triangle nb 1 repaint public void mousePressed MouseEvent e public void mouseReleased MouseEvent e public void mouseEntered MouseEvent e requestFocus public void mouseExited MouseEvent e public void nouveau t new Triangulation Delaunay NB_POINTS Delaunay LARGEUR Delaunay HAUTEUR redessiner AR La classe MyKeyAdapter class MyKeyAdapter extends KeyAdapter CanvasDelaunay c public MyKeyAdapter CanvasDelaunay c this c c public void keyTyped KeyEvent e switch e getKeyChar I case q System exit 0 case n c nouveau break default System out
8. points i x double Y2 points j y points i y double X3 points k x points i x double Y3 points k y points i y double det X2 Y3 X3 Y2 if det gt 0 return 1 if det lt 0 return 1 return 0 public int dansCercle int p On suppose i j k direct 1 si p hors du cercle 0 sur le cercle 1 dans le cercle double X2 points j x points i X double Y2 points j y points i y double Z2 X2 X2 Y2 Y2 double X3 points k x points i x double Y3 points k y points i y double Z3 X3 X3 Y3 Y3 double X4 points p x points i X double Y4 points p y points i y double Z4 X4 X4 Y4 Y4 DA double det Z2 X3 Y4 X4 Y3 Z3 X2 Y4 X4 Y2 Z4 X2 Y3 X3 Y2 if det gt 0 return 1 if det lt 0 return 1 return 0 j public boolean dansTriangle int p Attention le triangle doir etre orient e return estOriente p i j 1 amp amp estOriente p j k 1 amp amp estOriente p k i 1 public void print System out println i j kK public boolean toucheGrandTriangle return 0 I i 1 I i 2 1 I G 0 1G 1 I 1G 2 1 k 0 k 1 k 2 La classe Triangulation import java io class Triangulation Triangle trianglelnitial int X_MAX Y MAX public Triangulation int n int X MAX int Y MAX I this X MAX X MAX this Y MAX Y MAX Triangle points new Point n 3 Triangle nb 1
9. toutes les autres classes h riteraient mais Java ne permet pas l h ritage multiple et malheureusement certaines classes graphiques d rivent d j de classes d AWT Nous avons donc pr f r la solution finalement adopt e D autre part la taille du tableau points tant fix e arbitrairement l avance nous avons utilis une variable statique nb tel que nb 3 soit l indice du dernier point ins r autrement dit le nombre de points d j ins r s vaut nb 1 Cet entier sert trianguler au fur et mesure de l ajout des points la souris par le biais de l interface graphique La classe Point Un point est simplement repr sent par un couple de double Nous aurions pu choisir de mettre des entiers ou d utiliser la classe Point d AWT mais les erreurs num riques d arrondi auraient alors t p nalisantes notamment pour la v rification de certains pr dicats g om triques Cette remarque est encore plus pertinente lorsque les points sont fournis pas fichier texte dans la mesure o dans ce cas abscisse et ordonn e peuvent tre des doubles Avec l interface graphique la position de la souris est d crite par deux entiers Il convient donc alors de convertir ces entiers en doubles La classe Triangle Un triangle est d crit par ses trois sommets trois indices entiers du tableau de points ainsi que par des pointeurs vers ses trois triangles voisins pointeurs ventuellement null dans le cas de triangles
10. conflit avec P et le parcours en profondeur ne les a pas atteint Une fois la cavit exhib e il faut reconstruire la triangulation en maintenant jour les relations d adjacences des triangles Dans ce but il est n cessaire de trier les ar tes de la cavit On a donc d fini une relation d ordre simple Point de r f nce appel Depart dans le programme Centre P it x Avec les notations de la figure on dira que A est plus petit que B car lorsqu on parcourt le polygone dans le sens direct depuis le point D part on passe d abord par A puis par B La modification des triangles de la cavit On peut d sormais cr er les nouveaux triangles et faire la mise jour des relations d adjacence autrement dit des pointeurs de tous les triangles concern s S ALT 44 P Pa D ordre de cr ation des triangles A3 pr pointeurs modifi s On cr e donc les triangles PAjAj 1 dans l ordre dans lequel les segments AjAj apparaissent dans la cavit Les pointeurs rentrant ou sortant des triangles ext rieurs la cavit sont modifi s gr ce un maintien en m moire pour chaque ar te des deux triangles auxquels elle appartenait avant l insertion La mise jour des pointeurs est v ritablement la partie du programme la plus d licate impl menter b Complexit Nous allons maintenant dire quelques mots sur la complexit du programme Tout d abord cherchons une borne sup rieur
11. for int i 3 i lt Triangle nb 1 3 i g fillOval int Triangle points i x 3 int Triangle points i y 3 6 6 if Delaunay afficher_voronoi dessinerVoronoi t trianglelnitial g restore t trianglelnitial if Delaunay afficher_cercles dessinerCercles t trianglelnitial g restore t trianglelnitial if Delaunay afficher_triangles dessinerTriangles t trianglelnitial g restore t trianglelnitial gt if Delaunay afficher_arbre dessinerArbre g public void dessinerArbre Graphics g code ins rer pour dessiner l arbre if Triangle nb gt 1 g setColor Color ORANGE if Delaunay afficher_arbre Arbre a t retourneArbre for Arbre aa a aa null aa aa suite Point p Triangle points aa val a 3 Point q Triangle points aa val b 3 g drawLine int p x int p y int q x int q y j public void dessinerVoronoi Triangle tt Graphics g g setColor Color GREEN if tt null tt estDessine true return tt estDessine true Point c tt retourneCentre if I tt i 0 tt j 0 tt k 0 tt i 1 tt j 1 tt k 1 tt i 2 tt j 2 tt k 2 I if tt ti null AA j Point ci tt ti retourneCentre g drawLine int c x int c y int ci x int ci y if tt tj null Point cj tt tj retourneCentre g drawLine int c x int c y int cj x int cj y
12. rron dans calculerArbre res new Arbre s res N x return res j public String exportArbrePS permet d exporter l arbre en postscript Arbre arb calculerArbre String res 1 0 7 0 setrgbcolor n for Arbre aa arb aa null aa aa suite res res coords aa val a x coords aa val a y moveto res res coords aa val b x coords aa val b y lineto stroke n return res La classe Arbre class Arbre stocke les arltes de l arbre comme une liste de segments Segment val Arbre suite Arbre Segment s Arbre suite val s this suite suite void print 27 for Arbre a this a null a a suite I a val print La classe QueueListe class QueueListe boolean s1 ListeSegment liste Point coords QueueListe int n Point coords s1 new boolean n this coords coords j boolean estAjoute int i return s1 i void ajouter int i ListeEntier voisins s1 i true on enl eve les arites contenant i dans la liste supprimer i I on rajoute les segments int for ListeEntier ll voisins i IL null Il U suite if s1 ll val false j llval double d coords i x coords j x coords i x coords j x coords i y coords j y coords i y coords j y ajoutersegment new Segment i j d j void ajouterSegment Segment s
13. tant au bord de la triangulation Chaque objet de type Triangle comporte galement un champ centre correspondant au centre du cercle circonscrit au triangle ainsi que deux champs not s vu et estDessine qui sont des drapeaux Iflag utilis s par les fonctions parcourant la triangulation vu sert lors de la triangulation alors que estDessine sert pour l affichage graphique La classe Triangle a t munie de m thodes servant v rifier certains pr dicats g om triques gt retourneCentre qui renvoie le centre du cercle circonscrit au triangle Le coordonn es du centre du cercle circonscrit au triangle ABC sont donn es par les expressions 22 72 X2 z2 z3 y3 z3 z pe FA 7 X0 2 xi Jo 4a __ y 2 y2 E2 72 se Y3 3 y3 O X2 Y2 Z2 resp X3 Y3 Z3 d signent notations utilis es dans le code l abscisse ordonn e et la norme au carr du vecteur AB resp AC gt retourneCentreGravite qui renvoie le centre de gravit du triangle Cette m thode sert pour partir d un point int rieur la triangulation lors de la localisation par marche gt estOriente qui renvoie 1 si le triangle est direct 1 s il est indirect 0 s il est plat Pour tester si le triangle ABC est orient on calcule le d terminant det AB AC S il est de signe positif alors le triangle est orient sinon non gt dansCercle int p qui renvoie 1 si le point d indice p dans le tableau points est d
14. x x this y y public String toString return X this x y this y public static void main String agrs double d Double NaN System out println d int d System out println d int d La classe Triangle class Triangle static Point points static int nb correspond au niveau de remplissage du tableau de points int i j k Triangle ti tj tk les triangles adjacents boolean vu estDessine Point centre public Triangle int i int j int k Triangle ti Triangle tj Triangle tk this i i this j j this k K this ti ti this tj tj this tk tk vu false estDessine false j public Point retourneCentre IS j if centre null Point a points i Point b points j Point c points k double X2 b x a x double Y2 b y a y double Z2 X2 X2 Y2 Y2 double X3 c x a x double Y3 c y a y double Z3 X3 X3 Y3 Y3 double det X2 Y3 X3 Y2 double rx 0 5 Y3 Z2 Y2 Z3 det a x double ry 0 5 X2 Z3 X3 Z2 det a y centre new Point rx ry j return centre public Point retourneCentreGravite j Point a points i Point b points j Point c points k Point g new Point a x b x c x 3 a y b y c y 3 return g public static int estOriente int i int j int k j Orientation du triangle 1 direct 1 indirect 0 aligne double X2 points j x
15. 2 Consid rons A l arbre couvrant minimal de S Si AB n appartient pas A en rempla ant une ar te de A qui relie un point de S un point de S par AB on obtient un nouvel arbre couvrant mais plus court ce qui est contradictoire avec le fait que A soit l arbre couvrant minimal D o le r sultat D monstration du lemme 1 Soit AB la plus courte ar te entre un point de 1 et un point de Sz A dans Si B dans S2 Soit I le cercle de diam tre AB On suppose qu il existe un point P int rieur I Si P est dans Si alors PB lt AB ce qui est contradictoire Si P est dans S alors P lt AB ce qui est aussi contradictoire Donc I est vide Donc par le lemme 3 on conclu que AB est de Delaunay D monstration du th or me Consid rons A l arbre couvrant minimal de S Soit AB une de ses ar tes A AB s pare S en deux composantes connexes que l on nomme S et S2 AB est n cessairement la plus courte ar te entre S1 et S2 il ne peut y en avoir qu une dans A par minimalit de A et le lemme 2 permet d affirmer que c est la plus courte Par le lemme 1 AB est de Delaunay D o le r sultat Le th or me tant acquis on en d duit l algorithme de construction propos dans le sujet D tails sur la structure de donn es utilis e Nous avons envisag la classe Graphe comme compl tement ind pendante de la triangulation dans la mesure o elle peut aussi tre utilis e
16. Projet Informatique Sujet 3 Recherche d un arbre couvrant minimal par triangulation de Delaunay Alexandre GRAMFORT Cl ment MIGLIETTI Table des mati res I DESCRIPTION DES ALGORITHMES UTILIS S 3 1 LA TRIANGULATION DE DELAUNAY PAR L ALGORITHME INCR MENTAL 3 A PRINCIPE 3 B COMPLEXIT 6 2 L ALGORITHME DE CONSTRUCTION DE L ARBRE MINIMAL 7 A PRINCIPE 7 B COMPLEXIT 11 Il DESCRIPTION DE L ARCHITECTURE DU PROGRAMME 12 1 LES CLASSES DE LA TRIANGULATION DE DELAUNAY 12 2 LES CLASSES DE L ARBRE COUVRANT MINIMAL 15 3 LES CLASSES GRAPHIQUES ET LA CLASSE DE LECTURE 15 Ill CRITIQUE DES R SULTATS ET AM LIORATIONS DE L ALGORITHME 17 1 UNE PREMI RE MODIFICATION 17 2 UNE M THODE EXACTE 19 BILAN 21 ANNEXE 1 MANUEL D UTILISATION 22 ANNEXE 2 LISTING DU CODE 25 LA CLASSE POINT 25 LA CLASSE TRIANGLE 25 LA CLASSE TRIANGULATION 27 LA CLASSE CAVITE 35 LA CLASSE GRAPHE 36 LA CLASSE ARBRE 37 LA CLASSE QUEUELISTE 38 LA CLASSE LISTESEGMENT 39 LA CLASSE SEGMENT 39 LA CLASSE LISTEENTIER 40 LA CLASSE DELAUNAY 40 LA CLASSE CANVASDELAUNAY 45 LA CLASSE MYKEYADAPTER 49 LA CLASSE PANELDELAUNAY 49 LA CLASSE LECTURE 50 Utilisation du programme Le programme a t con u pour tre utilis de deux facons la premi re est d utiliser l interface graphique et de rentrer les points la souris la seconde de rentrer les points de la triangulation sous forme d un fichier texte Dans la fen tre graphique un
17. TEUR monLabel new Label Veuillez saisir les points Va la souris this add North monLabel monCanvas new CanvasDelaunay triangulation monLabel this add Center monCanvas monPanel new PanelDelaunay triangulation monCanvas this add South monPanel this setSize LARGEUR HAUTEUR setVisible true 49 public void handleQuit System exit 0 ActionListener pour les menus public void actionPerformed ActionEvent newEvent if newEvent getActionCommand equals miNew getActionCommand doNew else if newEvent getActionCommand equals miClose getActionCommand doClose else if newEvent getActionCommand equals miSaveAs getActionCommand doSaveAs else if newEvent getActionCommand equals miTriangles getActionCommand doTriangles else if newEvent getActionCommand equals miVoronoi getActionCommand doVoronoi else if newEvent getActionCommand equals miCircles getActionCommand doCircles else if newEvent getActionCommand equals miTree getActionCommand doTree public void doNew triangulation new Triangulation NB_POINTS LARGEUR HAUTEUR monCanvas redessiner j public void doClose handleQuit public void doSaveAs I 1 triangulation print FileDialog file new FileDialog Delaunay this Sauver dessin FileDialog SAVE file show Blocks String curFile if curFile file getF
18. Triangle points 0 new Point 50 X_MAX 50 Y_MAX on choisit un grand triangle initial pour eviter la perte de convexit e Triangle points 1 new Point 50 X_MAX 0 Triangle points 2 new Point 0 50 Y MAX trianglelnitial new Triangle 0 1 2 null null null j public void ajouter Point pt if pt x gt X_MAX pt y gt Y_MAX System out println Point hors du triangle initial return j 97 if Triangle nb 1 lt Triangle points length Triangle nb Triangle points Triangle nb 3 pt insere Triangle nb 3 public void insere int p Triangle t localise p Cavite c extraitCavite t p remplitCavite c p j public void calcule Point mesPoints int nombreDePoints System out println point 0 Triangle points 0 x Triangle points 0 y System out println point 1 Triangle points 1 x Triangle points 1 y System out println point 2 Triangle points 2 x Triangle points 2 y for int i 0 i lt nombreDePoints i I Triangle points i 3 mesPoints i 3 Triangle nb for int i 3 i lt nombreDePoints 3 i System out println j insere le point de coordonnees Triangle points i x Triangle points i y insere i j public boolean plusPetit int a int b int centre int depart on definit une relation d ordre sur les points retourne true si a lt b false sinon Point pa Triangle p
19. Writer f on choisit ce que l on veut voir affich e sur le dessin en postscript Delaunay afficher_cercles false Delaunay afficher_voronoi false Delaunay afficher_triangles true Delaunay afficher_arbre true String text tn exportPS on ajoute les segments de l arbre System out println Calcul de l arbre couvrant minimal text text g exportArbrePS text text showpage System out println d ebut d ecriture dans filename int textsize text length fw write text 0 textsize fw close System out println Enregistrement filename catch IOException exc System out println IOException filename 3 3 La classe Cavite class Cavite int a b correspondent aux indices des points de l ar te de la cavit e Triangle tint tExt tint et tExt pointent vers les triangles int erieurs et ext erieurs Cavite suivant Soit c le troisieme point du triangle interieur a et b sont tels que a b c est orient e Cavite int a int b Triangle tint Triangle tExt this a a this b b this tint tint this tExt tExt Cavite int a int b Triangle tint Triangle tExt Cavite suivant this a a this b b this tint tint this tExt tExt this suivant suivant 25 public static Cavite cons Cavite c1 Cavite c2 I if c1 null return c2 else I Cavite aux c1 while aux suivant null aux aux suivant
20. an estDejaAjoute permet de s assurer qu aucune ar te n est ajout e deux fois voisins Les m thodes de la classe Graphe sont gt ajouter int i int j qui comme son nom l indique ajoute l ar te i j gt calculerArbre renvoyant l arbre couvrant minimal La classe QueueListe Cette classe contient un tableau de boolean s1 sugg r par l nonc ainsi qu une liste tri e de segments sans oublier le tableau coords de Graphe afin d tre en mesure de pr ciser la taille des ar tes lors de l ajout Une m thode permet l ajout d un point d indice il ajouter int i ListeEntier voisins Celle ci adopte fid lement l algorithme de l nonc La classe ListeSegment Cette classe n est rien d autre qu une impl mentation de liste tri e croissante selon la longeur des segments La m thode ajouter est ici exceptionnellement choisie static pour viter l embarras des pointeurs null La classe ListeEntier C est une simple liste d entiers La classe Arbre Cette classe correspond une liste de Segment La classe Segment Elle contient 3 champs les deux entiers des indices des points avec la distance qui les s pare 3 Les classes graphiques et la classe de lecture Sans rentrer dans les d tails voici quelques informations sur l impl mentation de l interface graphique La classe Delaunay Cette classe d rive de Frame et contient comme champs un CanvasDelaunay monCanvas un Pane
21. ans le cercle 1 s il est l ext rieur 0 s il est dessus Cette fonction utilise donc le d terminant de cocyclicit ci dessous 1 ZA YA xa tya 1 XB yB XB YE 1 XC yc xc yc 1 ED YD xp yp gt dansTriangle int p qui renvoie true sille point d indice p dans le tableau points est int rieur au triangle false sinon Pour cela on se sert de la propri t Ile point P est int rieur au triangle ABC quivaut PAB PBC et PCA sont directs Cette fonction fait donc trois appels estOriente Enfin une m thode print qui affiche une cha ne de caract res d crivant le triangle servant essentiellement au d bugage a galement t crite La classe Triangulation Une triangulation est d crite par l ensemble de ses triangles On dispose d un pointeur d entr e dans la triangulation que nous avons nomm trianglelnitial Ce dernier est d plac chaque insertion d un nouveau point On a muni la classe triangulation des m thodes suivantes Tout d abord les m thodes pour l insertion gt localise int p qui renvoie le triangle qui contient P Localise effectue une localisation par marche partir de trianglelnitial et prend pour point de d part son centre de gravit gt extraitCavite Triangle t int p qui renvoie la cavit autour du point d indice p en partant du triangle localis t gt remplitCavite Cavite c int p met alors jour la triangulation autour de p apr s av
22. ci pouvaient tre dans l arbre couvrant minimal Pour rem dier cela nous avons pens une premi re modification de notre approche 1 Une premi re modification Pour obtenir la triangulation de Delaunay nous avons pens gt commencer par d terminer les points de l enveloppe convexe des points de la triangulation gt ins rer ces points dans le grand triangle gt Id tacher ces points du grand triangle c est dire d truire toutes les ar tes touchant une des extr mit s du grand triangle et mettre null les pointeurs des triangles touchant le bord de l enveloppe convexe gt ins rer les autres points de la triangulation qui d sormais seront tous int rieurs l enveloppe qui vient d tre cr e Le calcul d enveloppe convexe ne se fait donc qu une seule fois et par l algorithme de Graham en n In n du nombre de points Il s effectue ainsi en travaillant sur les points et non pas sur les triangles on ne fait donc pas de parcours en profondeur pour calculer l enveloppe convexe Avec cette m thode on obtient notamment un diagramme de Vorono correct au bord de la triangulation Nous avons impl ment cette modification en ajoutant la classe suivante La classe Enveloppe La classe Enveloppe permet la gestion du calcul de l enveloppe convexe des points sur lesquels va s appuyer la triangulation Un objet de type Enveloppe comporte 3 champs gt Un champ points qui ne se
23. cours en profondeur pour trouver la cavit Dans la fonction dansCercle de la classe triangle il faudrait ne pas calculer le d terminant si le triangle est de type infini mais v rifier si le point ins rer appartient au demi plan repr sentant le cercle circonscrit de ce triangle Concernant la construction de la cavit il faut imposer de ne pas ajouter la cavit les segments comportant un point infini Un autre probl me appara t dans l ordonnancement des segments de la cavit puisque le point de d part cf 1 a figure de la suite de segments est pris au hasard dans la majorit des cas apr s tri nous obtiendrions une suite de segments non contig s Ce probl me peut tre r solu en refaisant un tri avec pour point de d part le point de rupture on obtient alors une suite de segments contigis d finissant la cavit Le remplissage de la cavit est galement modifier puisque dans le cas d une insertion d un point ext rieur il faudrait cr er deux triangles infinis avec pour pointeur les triangles des bords voisins La mise jour des pointeurs est donc assez diff rente Enfin puisqu il n y aurait plus aucun triangle null il faudrait remplacer tous les tests faisant r f rence au triangle null par des tests l aide d une m thode estinfini qui renverrait true si le triangle consid r est infini c est a dire si l un des sommets a pour indice 1 Camt Nouveaux triangles
24. e ar te de la triangulation de Delaunay Lemme 2 Si S S4 U S gt alors la plus courte ar te entre un point de S et un point de S2 est une ar te de l arbre couvrant minimal Lemme 3 Une ar te est de Delaunay si et seulement si il existe un cercle passant par ses extr mit s en ne contenant pas de point de S Lemme 4 Soit A B C D quatre points du plan Soit I un cercle passant par et B Si C et D sont ext rieurs T alors C est ext rieur au cercle circonscrit ABD et D est ext rieur au cercle circonscrit ABC Lemme 5 Soit ABC et BCD deux triangles adjacents et poss dant la propri t de Delaunay Alors les triangles ABD et ACD ne poss dent pas la propri t de Delaunay Rappelons tout d abord qu avec les notations de la figure on al Q n appartient pas Bp lt gt P n appartient pas Ba 1 D autre part notons que la propri t D est l ext rieur du cercle circonscrit ABC se traduit dans la configuration du dessin par B lt Tr a Jr N DA i NG C i mm verd AS NG A Dr I N p N o Le D D monstration du lemme 5 Supposons que les 4 triangles poss dent la propri t de Delaunay Par ce qui pr c de on a alors IN FA i da 7 F pr 4 f di H k B Fi N Cz N f if a3 lt T 044 et a4 lt T 02 et donc a1 02 a3 a4 lt 2m Contradiction D monstration du lemme 4 i x p O I X Li VA
25. e du nombre de triangles cr s chaque insertion Comme en t moignent les deux graphes suivants nous voyons qu il est possible lors de l insertion du point n 1 de d truire l ensemble des triangles jusque l construits et d en cr er alors n 1 Triangulation apr s insertion de 5 points Triangulation apr s insertion de 6 points Ce cas est clairement le pire et donc le co t l tape n 1 et au plus lin aire en nombre de nouveaux triangles cr s On en d duit donc une majoration de la complexit de l insertion de n points de fa on incr mentale O n En ce qui concerne la borne inf rieure On peut remarquer qu en placant comme ci dessus les points sur une parabole le fait de trianguler donne un tri des abscisses des points et de fait ne peut avoir une meilleure complexit que n In n L algorithme est donc un n In n 2 L algorithme de construction de l arbre minimal a Principe Le principe g n ral de construction est donn dans l nonc du sujet Nous nous contenterons donc de d montrer les lemmes servant justifier l utilisation de la triangulation de Delaunay pour la recherche de l arbre couvrant minimal Th or me l arbre couvrant minimale est inclus dans la triangulation de Delaunay Nous donnons une d monstration de cette propri t utilisant les lemmes suivants Lemme 1 Si S S U S alors la plus courte ar te entre un point de S et un point de Sz est un
26. e en O n In n Cependant l algorithme de Delaunay tant en O n ceci n est pas grave Il aurait t int ressant d impl menter une telle structure de donn es si l algorithme de triangulation par division fusion avait t choisi La complexit globale aurait alors t en O n In n II Description de l architecture du programme Le programme est structur en un certain nombre de classes o l on peut distinguer trois groupes les classes de l algorithme de triangulation celles utilis es pour la d termination de l arbre de recouvrement minimal et enfin les classes ayant servi l interface graphique et l entr e des points sous forme de fichier texte D autre part nous avons adopt un style de programmation plut t orient objet pour traiter le sujet 1 Les classes de la triangulation de Delaunay Remarques g n rales sur l impl mentation Nous avons choisi de stocker tous les points figurant dans la triangulation dans le tableau static points de la classe Triangle La quasi totalit des m thodes du programme ne prend donc pas en arguments ces points mais des entiers qui repr sentent leurs indices dans le tableau Mentionnons galement que les trois premi res cases de ce tableau sont occup es par les trois points qui d finissent le grand triangle que nous avons voqu plus haut Nous avions pour faciliter l criture du programme pens mettre le tableau de points dans une classe dont
27. erCree to Triangle courant to System out print on cree le triangle courant print if c tExt null if c tExt ti c tInt c tExt ti courant else if c tExt tj c tInt c tExt tj courant else c tExt tk courant an System out print maintenant c tExt print System out print pointe vers courant print for Cavite cs c suivant cs null cs cs suivant courant new Triangle p cs a cs b cs tExt null dernierCree System out print on cree le triangle courant print if cs tExt null I if cs tExt ti cs tInt cs tExt ti courant else if cs tExt tj cs tInt cs tExt tj courant else cs tExt tk courant System out print maintenant cs tExt print System out print pointe vers courant print dernierCree tj courant dernierCree courant to tk courant courant tj to j public boolean sontOriente Point pi Point pj Point pk double X2 pj x pi x double Y2 pj y pi y double X3 pk x pi x double Y3 pk y pi y double det X2 Y3 X3 Y2 if det gt 0 return true else return false j public Triangle localise int p System out println D ebut localise de p Triangle t trianglelnitial Point c t retourneCentreGravite System out println Point de d epart c Point points Triangle points while t dansTriangle p while t dansCercle p 1 I if sontOriente c points t i po
28. ile null String filename file getDirectory curFile setCursor Cursor getPredefinedCursor Cursor WAIT_CURSOR String aux if Delaunay afficher_arbre 42 Graphe g triangulation retourneGraphe aux g exportArbrePS File f new File filename try FileWriter fw new FileWriter f String text triangulation exportPS text text aux showpage int textsize text length fw write text 0 textsize fw close System out println Enregistrement filename catch IOException exc System out println IOException filename setCursor Cursor getPredefinedCursor Cursor DEFAULT_CURSOR j public void doVoronoi if afficher_voronoi System out println Fin d affichage de Voronoi miVoronoi setLabel Afficher Voronoi afficher_voronoi false else System out println affichage de Voronoi miVoronoi setLabel Effacer Voronoi afficher_voronoi true j monCanvas repaint public void doCircles if afficher_cercles System out println Fin d affichage des cercles miCircles setLabel Afficher les cercles circonscrits afficher_cercles false else System out println affichage des cercles miCircles setLabel Effacer les cercles circonscrits afficher_cercles true j monCanvas repaint public void doTriangles if afficher_triangles System out println Fin d affichage de
29. ints p amp amp sontOriente c points p points t j t t tk else if sontOriente c points t j points p amp amp sontOriente c points p points t k t t ti 21 else if sontOriente c points t k points p amp amp sontOriente c points p points t i t t tj System out print Triangle localis e t print return t j ERRE NE RER NNN EN STE Fonctions d impression et d exportation de la triangulation hd Sk der public void print System out println Affichage de la triangulation printAux trianglelnitial restorePrint trianglelnitial j public void printAux Triangle t if t null amp amp It vu I t print t vu true printAux t ti printAux t tj printAux t tk j public void restorePrint Triangle t permet de remmettre les vu a false if t null amp amp t vu I t vu false restorePrint t ti restorePrint t tj restorePrint t tk j public String exportPS permet d exporter la triangulation en postscript String res exportPSaux trianglelnitial restorePrint trianglelnitial res n res return res 29 public String exportPSaux Triangle t String res if t null amp amp t vu I t vu true if I t i t j t k 0 t i 1 t j 1 t k 1 t i 2 t j 2 t k 2 if Delaunay afficher triangles moveto lineto strokeln m
30. lDelaunay monPanel ainsi que l ensemble du code n cessaire l affichage des menus Elle poss de aussi quelques booleans static servant d terminer les l ments afficher dans monCanvas La classe CanvasDelaunay Cette classe d rive de la classe Canvas d AWT et constitue la portion de la fen tre sur laquelle les points sont plac s la souris Elle impl mente donc naturellement MouseListener et poss de un KeyAdapter permettant la gestion des racourcis claviers Elle poss de galement toutes les m thodes servant au dessin de la triangulation La classe PanelDelaunay Elle g re le champ texte et le bouton de bas de fen tre permettant de modifier le nombre de points pouvant tre ins r s Ces trois m thodes se partagent une m me instance de Triangulation La classe Lecture Cette classe permet l entr e des points sous forme d un fichier texte C est un simple lexeur adapt l entr e des points sous forme abscisse ordonn e au format double III Critique des r sultats et am liorations de l algorithme Le premier constat que nous avons fait apr s avoir impl ment cette m thode fut que si le triangle initial n tait pas suffisamment grand il tait tr s facile de n obtenir qu une approximation de la triangulation souhait e En effet celle ci pouvait apr s suppression des triangles ext rieurs ne plus contenir les ar tes de l enveloppe convexe Ceci tait g nant car celles
31. lireBlancs while carCourant carCourant t carCourant n avancer j public static void main String args throws IOException init System in Initialisation de carCourant Point mesPoints Lecture retourne_points for int i 0 i lt mesPoints length i System out println mesPoints i j 59
32. menu permet d afficher l arbre couvrant minimal le diagramme de Voronoi et les cercles circonscrits aux triangles de la triangulation Pour plus de d tails sur l utilisation du programme se r f rer l annexe 1 I Description des algorithmes utilis s La construction de l arbre couvrant minimal se fait en deux tapes Tout d abord on calcule de facon incr mentale la triangulation de Delaunay des points consid r s Puis dans un second temps partir des ar tes de la triangulation on d termine l arbre couvrant minimal 1 La triangulation de Delaunay par l algorithme incr mental Comme son nom l indique le principe de cet algorithme est d ajouter un un les points et de modifier en cons quence la triangulation Dans ce but nous utilisons la propri t caract ristique de la triangulation de Delaunay lle cercle circonscrit un triangle ne contient aucun autre point de la triangulation que ceux du triangle lui m me Les modifications sont donc op r es de fa on conserver cette propri t a Principe Nous allons d tailler le m canisme de l insertion d un point P Deux cas peuvent se pr senter lors de l insertion d un point P ou bien P est dans un triangle d j construit ou bien P est hors de l enveloppe convexe des points d j ins r s Pour simplifier l algorithme il est possible de ne consid rer que le premier cas en consid rant que tous les points sont ins re
33. od ee par 1 selon read carCourant carEOF static void init InputStream inp par exemple inp System in in new BufferedReader new InputStreamReader inp avancer static Point retourne_points ListePoints lp null intnb 0 sn while carCourant carEOF nb lp new ListePoints point_suivant lp Point res new Point nb 3 nb 0 for ListePoints Ll lp Ul null U IL suivant res nb 3 ll val nb return res j static Point point_suivant lireBlancs double x nombre lireBlancs double y nombre lireBlancs return new Point x y j Lecture d un nombre static private double nombre if Character isDigit carCourant throw new Error Un chiffre est attendu en entr e de nombre double n 0 while Character isDigit carCourant int chiffre int carCourant int 0 Les caract eres 0 1 2 sont cod es dans cet ordre en ascii par des nombres cons ecutifs voir man ascii n n 10 chiffre avancer if carCourant avancer intr 10 while Character isDigit carCourant int chiffre int carCourant int 0 I Les caract eres 0 1 2 sont cod es dans cet ordre 1 I en ascii par des nombres cons ecutifs Voir man ascii n n chiffre r r r 10 avancer j return double n Lecture des blancs S1 static void
34. oints a Point pb Triangle points b Point pcentre Triangle points centre Point pdepart Triangle points depart if pa x pdepart x amp amp pa y pdepart y return true if pb x pdepart x amp amp pb y pdepart y return false if sontOriente pcentre pdepart pa sontOriente pcentre pdepart pb return sontOriente pcentre pa pb return sontOriente pcentre pdepart pa j public Cavite insereDansCavite int aa int bb Triangle tin Triangle tex Cavite cav int centre cette fonction insere un segment dans la cavit e en respectant l ordre IR defini par la fonction plusPetit Ile but est d obtenir au final une cavite form ee de segment contigus trie dans le sens direct if cav null System out println j ai ajoute le segment aa bb dans la caverne return new Cavite aa bb tin tex else return insereDansCaviteAux aa bb tin tex cav centre cav a j public Cavite insereDansCaviteAux int aa int bb Triangle tin Triangle tex Cavite cav int centre int depart if cav null f System out println j ai ajoute le segment aa bb en fin de caverne return new Cavite aa bb tin tex if plusPetit aa cav a centre depart System out println j ai ajoute le segment aa bb dans la caverne return new Cavite aa bb tin tex cav else cav suivant insereDansCaviteAux aa bb tin tex cav suivant centre depart return cav public Cavite extraitCavite Triangle t int
35. oir tri la cavit Le tri utilise la m thode plusPetit int a int b int centre int depart et la m thode insereDansCavite int aa int bb Triangle tin Triangle tex Cavite cav int centre qui ins re en conservant l ordre d finit par plusPetit IL s ajoute cela un certain nombre de m thodes servant l exportation postscript ainsi que Les m thodes servant la cr ation du graphe gt retourneGraphe renvoie le Graphe recherch gt retourneArbre renvoie l arbre apr s avoir calcul le graphe Quant la fonction main elle permet d ins rer les points partir d un fichier texte Pour plus de d tails voir Annexe 1 La classe Cavite La cavit est d finie comme tant une liste de segments tri s cf la relation d ordre introduite ci dessus Deux premiers champs a et b d signent les extr mit s du segment De plus chaque segment sont associ s deux pointeurs un pointeur tint qui pointe vers le triangle int rieur la cavit ayant pour ar te ab un pointeur tExt qui pointe vers le triangle ext rieur la cavit ayant pour ar te ab Ces pointeurs servent lors de la cr ation des nouveaux triangles qui vont venir combler la cavit cf ci dessus 2 Les classes de l arbre couvrant minimal La classe Graphe La classe Graphe stocke les relations d adjacence dans voisins qui est un tableau de listes de points ainsi que les points dans un tableau nomm coords La matrice de boole
36. ose addActionListener this mainMenuBar add fileMenu public void addEditMenultems if afficher triangles I miTriangles new Menultem Effacer les triangles else miTriangles new Menultem Afficher les triangles drawMenu add miTriangles setEnabled true miTriangles addActionListener this if afficher_voronoi miVoronoi new Menultem Effacer Voronoi else miVoronoi new Menultem Afficher Voronoi drawMenu add miVoronoi setEnabled true A1 j miVoronoi addActionListener this if afficher_cercles miCircles new Menultem Effacer les cercles circonscrits else miCircles new Menultem Afficher les cercles circonscrits drawMenu add miCircles setEnabled true miCircles addActionListener this if afficher_arbre miTree new Menultem Effacer arbre couvrant minimal else miTree new Menultem Afficher arbre couvrant minimal drawMenu add miTree setEnabled true miTree addActionListener this mainMenuBar add drawMenu public void addMenus j fileMenu new Menu Fichier drawMenu new Menu Dessin addFileMenultems addEditMenultems setMenuBar mainMenuBar public Delaunay super WindowAdpt WAdapter new WindowAdpt this addWindowListener WAdapter setTitle Delaunay setResizable false setLayout null addMenus setLayout new BorderLayout triangulation new Triangulation NB POINTS LARGEUR HAU
37. ous a pos probl me Bien s r dans la pratique il est relativement peu probable si Les points sont r partis peu pr s al atoirement dans la fen tre graphique et si la taille du grand triangle de d part est augment e Points du grand triangle Points ins r s Une fois encore ici le probl me est imparfaitement r solu et impose comme seule solution d augmenter la taille du triangle initial Cependant une m thode exacte existe Remarque Nous n avons pas fourni le code de la classe Enveloppe car l ayant abandonn par constat d imperfection Cependant il reste bien s r disponible sur votre demande 2 Une m thode exacte Nous pr sentons enfin une autre facon de proc der qui cette fois fournit une solution exacte au probl me pos la m thode consiste consid rer que les ar tes des bords appartiennent un triangle dont le troisi me point est l infini cf dessin Point P ins rer Demi plan dans lequel on consid re que le point ins rer appartient au cercle circonscrit du triangle infini Triangles infinis Par manque de temps nous n avons pas impl ment cette m thode mais voici les modifications qu il faudrait op rer gt gt On mat rialiserait le point infini par l indice du tableau des points 1 Un triangle infini devrait avoir pour triangles adjacents les triangles infinis des bords les plus proches de facon pouvoir effectuer un par
38. oveto lineto stroke n moveto lineto stroke n su i ie nad res res 000 setrgbcolor n res res Triangle points t i x Triangle points t i y res res Triangle points t j x Triangle points t j y res res Triangle points t j x Triangle points t j y res res Triangle points t k x Triangle points t k y res res Triangle points t k x Triangle points t k y res res Triangle points t i x Triangle points t i y Delaunay afficher_cercles res res 1 0 0 setrgbcolor n Point c t retourneCentre Point a t points t i double r Math sgrt a x c x a x c x a y c y a y C y res res c x c y int r 0360arc stroke n Delaunay afficher_voronoi res res 0 1 0 setrgbcolor n Point c t retourneCentre Point cc if t ti null CC t ti retourneCentre res res C X c y moveto res res CC X cc y lineto stroke n if I t tj null I CC t tj retourneCentre res res C X c y moveto res res CC X cc y lineto stroke n if I t tk null I cc t tk retourneCentre res res C X c y moveto res res CC X cc y lineto stroke n j res res exportPSaux t ti RR res res exportPSaux t tj res res exportPSaux t tk j
39. p Cavite cav chercheCav t p null return cav public Cavite chercheCav Triangle t int p Cavite cav t vu true System out print je suis dans t print Cavite res cav if t ti null t ti print System out println est adjacent if t ti vu if I t ti dansCercle p 1 res chercheCav t ti p res else I res insereDansCavite t j t k t t ti res p gelse I else 70 j System out println je touche un bord res insereDansCavite t j t k t t ti res p if t tj null t tj print System out println est adjacent if t tj vu if t tj dansCercle p 1 res chercheCav t tj p res else res insereDansCavite t k t i t t tj res p else else System out println je touche un bord res insereDansCavite t k t i t t tj res p if t tk null t tk print System out println est adjacent if t tk vu if t tk dansCercle p 1 res chercheCav t tk p res else res insereDansCavite t i t j t t tk res p gelse I else System out println je touche un bord res insereDansCavite t i t j t t tk res p System out print fini pour t print return res public void remplitCavite Cavite c int p if c null throw new Error Cavite null ne entr ee de remplitCavit e c print Triangle to new Triangle p c a c b c tExt null null trianglelnitial to Triangle derni
40. println Caractere inconnu e getKeyChar break j La classe PanelDelaunay import java awt import java awt event class PanelDelaunay extends Panel implements ActionListener CanvasDelaunay monCanvas Triangulation t TextField monTextField Button boutonValider public PanelDelaunay Triangulation t CanvasDelaunay monCanvas I this monCanvas monCanvas this t t setBackground Color blue add new Label Indiquer le nombre de point souhait e monTextField new TextField Integer toString Delaunay NB_POINTS 10 add monTextField add boutonValider new Button Valider boutonValider addActionListener this j 40 public void actionPerformed ActionEvent ev I String label ev getActionCommand if label equals Valider int n Integer parselnt monTextField getText Delaunay NB_POINTS n t new Triangulation n Delaunay LARGEUR Delaunay HAUTEUR monCanvas redessiner La classe Lecture import java io class Lecture Variable statique li ees a la lecture par avancer static char carCourant caract ere courant static BufferedReader in Stream de lecture final static char carEOF char 1 caract ere codant la fin de fichier static void avancer try carCourant char in read read renvoie un int catch java io IOException e En cas d exception on consid ere la fin de fichier atteinte c
41. r dans un grand triangle qui sera en fait construit l initialisation de la triangulation et avant toute insertion Cependant il faut alors remarquer que la triangulation obtenue in fine peut ne pas exactement tre la triangulation de Delaunay pour les points utilis s en entr e puisque la pr sence du grand triangle entra nera certaines modifications nous tudierons plus pr cis ment le moyen d y rem dier en troisi me partie L algorithme fournit ici donne donc une solution qui co ncidera avec la solution optimale dans de nombreux cas et qui en fournira une approximation relativement bonne sinon Lors de l insertion d un point il s agit tout d abord de d terminer la partie de la triangulation qui est constitu e des triangles dont les cercles circonscrits contiennent le nouveau point P Pour localiser un triangle de cette partie on effectue ce qu on appelle une localisation par marche Localisation par marche Une fois choisi un point O du plan dont la seule contrainte est d tre l int rieur d un triangle de la triangulation on lse d place dans celle ci gr ce aux relations d adjacences On a choisi de prendre pour O le centre de gravit d un triangle connu de la triangulation Pour passer d un triangle un autre nous avons utilis des conditions d orientation Sur la figure pour sortir de IJK nous utilisons le fait que OPK et OPJ sont d orientations contraires Le triangle suivant e
42. ra utilis que comme un pointeur vers le tableau de points de la classe triangle gt Un int m qui donne l indice du tableau points du premier point n appartenant pas l enveloppe convexe gt Un int nb qui contient le nombre de points de la triangulation La classe Enveloppe est munie des fonctions e theta point p1 point p2 qui rend langle entre le vecteur PP et laxe des abscisses e D une fonction tri qui est un quick sort triant les nb points du tableau par ordre des th ta croissant avec pour points P4 le point d abscisse la plus petite Point le plus bas gt D une fonction enveloppeConvexe qui partir de l d termine l enveloppe convexe des points en remplissant le champ m d fini ci dessus Le constructeur fait un appel la fonction enveloppeConvexe et donc modifie le tableau de points qui lui est rentr en argument Critique de cette m thode Si cette mani re de proc der permet d obtenir la triangulation de Delaunay souvent de mani re plus correcte elle g n re cependant des erreurs dans certaines situations et en particulier lors des premi res insertions lorsque les points forment des triangles tr s aplatis Les erreurs sont dues au fait que les segments de l enveloppe convexe peuvent ne pas appartenir la triangulation Dans le pire des cas on peut observer la configuration o tous les triangles form s touchent le grand triangle cf dessin C est ce cas particulier qui n
43. return res ARRETRARE TREIA ATEN construction de l arbre minimal PRETORIO public Arbre retourneArbre Graphe g retourneGraphe return g calculerArbre j public Graphe retourneGraphe permet de cr eer le graphe on ajoute les ar tes par parcours en profondeur de la triangulation Graphe res new Graphe Triangle points Triangle nb 1 retourneGrapheaux trianglelnitial res restorePrint trianglelnitial return res public void retourneGrapheaux Triangle t Graphe res t vu true res ajouter t j t k res ajouter t k t i res ajouter t i t j if t ti null amp amp t ti vu false retourneGrapheaux t ti res if t tj null amp amp t tj vu false retourneGrapheaux t tj res if t tk null amp amp t tk vu false retourneGrapheaux t tk res public static void main String args permet de rentrer les points en input exemple java Triangulation lt input txt I le resultat est enregistr e en postscript dans output ps Lecture init System in Point mesPoints Lecture retourne_points Triangulation tn new Triangulation mesPoints length Delaunay LARGEUR Delaunay HAUTEUR tn calcule mesPoints mesPoints length 3 System out println Fin de la triangulation System out println Exportation du graphe Graphe g tn retourneGraphe String filename output ps File f new File filename 34 try FileWriter fw new File
44. s triangles miTriangles setLabel Afficher les triangles afficher_triangles false AA else System out println affichage des triangles miTriangles setLabel Effacer les triangles afficher_triangles true monCanvas repaint j public void doTree if afficher_arbre System out println Fin d affichage de l arbre miTree setLabel Afficher l arbre couvrant minimal afficher_arbre false else System out println affichage de l arbre miTree setLabel Effacer l arbre couvrant minimal afficher_arbre true monCanvas repaint class WindowAdpt extends java awt event WindowAdapter public void windowClosing java awt event WindowEvent event handleQuit public static void main String args if args length 2 Delaunay HAUTEUR Integer parselnt args 0 Delaunay LARGEUR Integer parselnt args 1 new Delaunay j La classe CanvasDelaunay import java awt import java awt event class CanvasDelaunay extends Canvas implements MouseListener Triangulation t Label l boolean clear false CanvasDelaunay Triangulation t Label this t t AS this l l addMouseListener this addKeyListener new MyKeyAdapter this Methode appel ee pour red essiner tout le Canvas public void paint Graphics g if Iclear dessiner g j public void dessiner Graphics g g setColor Color BLACK
45. sans Delaunay en mettant dans le graphe initial toutes les ar tes possibles entre chaque point La classe Graphe poss de donc un tableau de points qui n est rien d autre qu une copie des points de la classe Triangle On stocke les relations d adjacences du graphe dans un tableau contenant en position i une liste d entiers correspondant aux indices des voisins de i Ceci permet notamment lors de la recherche des voisins de i lors de l ajout de i l arbre couvrant minimal de ne pas tester si i est reli tous les autres points comme cela aurait t n cessaire avec un stockage sous forme de matrice La queue elle poss de un tableau s1 de boolean comme le sugg re l nonc et une liste tri e de segments autoris s pour l ajout du point suivant Le fait que cette liste soit tri e de facon croissante facilite grandement la recherche du segment minimum c est toujours le premier l ment de la liste b Complexit Ce qui d termine la complexit de l algorithme de construction d arbre minimal est la structure de donn e utilis e pour la queue Avec une liste tri e au pire des cas on ajoute la liste lors de l tape n un segment en fin de liste On a alors dans ce cas un co t lineaire en n pour passer de n n 1 La complexit finale est donc en O n L utilisation d un arbre bianire quilibr pour la gestion de la queue aurait permis une recherche de minimum en In n et une complexit final
46. st donc le voisin avec lequel IJK partage l ar te KJ Extraction de la cavit Une fois la localisation faite nous connaissons le triangle auquel P appartient Pour trouver tous les triangles dont les cercles circonscrits contiennent P on proc de un parcours en profondeur du graphe associ la triangulation l aide des relations d adjacence En effet lorsqu il s agit de parcourir la triangulation par exemple lorsqu on veut la dessiner on peut l assimiler un graphe non orient dont chaque sommet poss de au plus trois voisins et donc utiliser un algorithme de parcours en profondeur Au cours de ce parcours on marque par vu les triangles visit s afin de ne pas boucler La descente en profondeur s arr te d s qu on rencontre un triangle pour lequel P n appartient pas au cercle circonscrit La cavit est d finie par une liste d ar tes cf classe Cavite partie II Lorsqu on se trouve dans un triangle on choisit d ajouter un segment la cavit si ce segment se trouve tre une ar te mitoyenne entre un triangle len conflit avec P et entre un triangle ne l tant pas le triangle Inull n est jamais consid r en conflit avec un point ins rer w Triangle en conflit avec P Triangle n entrant pas en conflit avec P Y Sur la figure les triangles non marqu s par un drapeau n ont pas t visit s en effet ils ne sont pas voisins d un triangle en
47. steEntier int val ListeEntier suite this val val this suite suite La classe Delaunay import java awt import java awt event import java io class Delaunay extends Frame implements ActionListener static int HAUTEUR 600 static int LARGEUR 800 nombre de points autoris es static int NB_POINTS 15 champs Triangulation triangulation CanvasDelaunay monCanvas PanelDelaunay monPanel Label monLabel les booleans n ecessaires pour l affichage static boolean afficher_voronoi true static boolean afficher_cercles true AN static boolean afficher_triangles true static boolean afficher_arbre true d eclaration de la police private Font font new Font serif Font ITALIC Font BOLD 36 Declarations des menus static final MenuBar mainMenuBar new MenuBar protected Menu fileMenu protected Menultem miNew protected Menultem miClose protected Menultem miSaveAs protected Menu drawMenu protected Menultem miTriangles protected Menultem miVoronoi protected Menultem miCircles protected Menultem miTree public void addFileMenultems I miNew new Menultem Nouveau fileMenu add miNew setEnabled true miNew addActionListener this miSaveAs new Menultem Enregistrer sous fileMenu add miSaveAs setEnabled true miSaveAs addActionListener this miClose new Menultem Fermer fileMenu add miClose setEnabled true miCl
Download Pdf Manuals
Related Search