Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Transp 11 Programmation A Algorithmique Algorithmes géométriques ALGORITHMES GÉOMÉTRIQUES Contenu du chapitre ? Introduction ? Représentation de points de segments et de polygones ? Intersection de segments ? Appartenance d'un point à l'intérieur d'un pol

Programmation A Algorithmique Algorithmes géométriques ALGORITHMES GÉOMÉTRIQUES Contenu du chapitre ? Introduction ? Représentation de points de segments et de polygones ? Intersection de segments ? Appartenance d'un point à l'intérieur d'un polygone ? Enveloppe convexe ? Conclusion ? R Ingold Université de Fribourg - CProgrammation A Algorithmique Algorithmes géométriques Méthodes géométriques élémentaires - Introduction ? la manipulation algorithmique d'objets géométriques points segments polygones etc est importante pour bon nombre d'applications - conception assitée par ordinateur CAO - systèmes d'information géographiques SIG - etc ? de nombreux problèmes en mathématiques statistique ? peuvent être exprimés géométriquement ? les problèmes géométriques faciles à visualiser peuvent être résolus trivialement par une personne mais nécessiter des algorithmes complexes - exemple un point est-il inclus dans un polygone ? la géométrie algorithmique est une discipline relativement récente même si elle fait appel à un riche contexte historique ? R Ingold Université de Fribourg - CProgrammation A Algorithmique Algorithmes géométriques Points segments et polygones ? la plupart des algorithmes étudiés concerneront l'espace à deux dimensions ? les objets fondamentaux considérés sont le point dé ?ni par ses deux coordonnées supposées entières - le segment de droite dé ?ni par une paire de points - le polygone dé ?ni par une liste de points struct point int x y char c struct line struct point p p struct point polygon Nmax ? les points peuvent être étiquetés par un caractère ? d'autres informations pourraient être ajoutées aux enregistrements en utilisant un champ info ? il est parfois utile de représenter un polygone avec des sentinelles p p n et p n p ? R Ingold Université de Fribourg - CProgrammation A Algorithmique Algorithmes géométriques Exemple de données ensembles de points ? ? R Ingold Université de Fribourg - CProgrammation A Algorithmique Algorithmes géométriques Intersection de segments ? premier problème étant donné deux segments déterminer s'ils s'intersectent ? plusieurs situations sont à considérer ? topologiquement les segments sont supposés fermés les extrémités appartiennent au segment ? première méthode calculer le point d'intersection des droites supportant les deux segments et véri ?er si ce point se trouve à l'intérieur de chaque segment ? seconde méthode déterminer si le chemin reliant trois points tourne dans le sens des aiguilles d'une montre ou en sens inverse ? R Ingold Université de Fribourg - CProgrammation A Algorithmique Algorithmes géométriques Algorithme de détermination du sens de parcours de trois points int ccw struct point p struct point p struct point p int dx dx dy dy dx p x - p x dy p y - p y dx p x - p x dy p y - p y if dx dy dy dx return if dx dy dy dx return - if dx dx dy dy return - if dx dx dy dy dx dx dy dy return return ? lorsque les points p p p sont colinéaires la convention est si p est entre p et p ccw retourne - si p est entre p et p ccw retourne