Remerciez-le!

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

Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Univer

Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 1 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 Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 2 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 Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 3 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éfini par ses deux coordonnées, supposées entières) - le segment de droite (défini par une paire de points) - le polygone (défini par une liste de points) struct point { int x, y; char c; }; struct line { struct point p1, p2; }; 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[0]=p[n] et p[n+1]=p[1] Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 4 Exemple de données: ensembles de points Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 5 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érifier 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 Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 6 Algorithme de détermination du sens de parcours de trois points int ccw(struct point p0, struct point p1, struct point p2) { int dx1, dx2, dy1, dy2; dx1 = p1.x - p0.x; dy1 = p1.y - p0.y; dx2 = p2.x - p0.x; dy2 = p2.y - p0.y; if (dx1*dy2 > dy1*dx2) return +1; if (dx1*dy2 < dy1*dx2) return -1; if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1; if ((dx1*dx1 + dy1*dy1) < (dx2*dx2 + dy2*dy2)) return +1; return 0; } • lorsque les points p0, p1, p2 sont colinéaires la convention est: - si p0 est entre p1 et p2, ccw retourne -1 - si p2 est entre p0 et p1, ccw retourne 0 - si p1 est entre p0 et p2, ccw retourne +1 Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 7 Algorithme d'intersection int intersect(struct line l1; struct line l2;) { return ((ccw(l1.p1, l1.p2, l2.p1) *ccw(l1.p1, l1.p2, l2.p2)) <= 0) && ((ccw(l2.p1, l2.p2, l1.p1) *ccw(l2.p1, l2.p2, l1.p2)) <= 0) } Commentaire • cet algorithme astucieux semble nécessiter beaucoup de calculs • la recherche d'une solution plus courte, mais néanmoins complète est loin d'être triviale Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 8 Appartenance d'un point à l'intérieur d'un polygone • deuxième problème: déterminer si un point donné se trouve à l'intérieur d'un polygone donné • première solution: à partir du point, tirer un long segment (dont l'extrémité est en dehors du polygone) et déterminer la parité du nombre d'intersections avec les arêtes du polygone • il faut cependant faire attention aux cas ou le segment passe par un sommet du polygone Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 9 Algorithme d'inclusion dans un polygone int inside(struct point t, struct point p[], int N) { int i, count = 0; j = 0; struct line lt, lp; p[0] = p[N]; p[N+1] = p[1]; lt.p1 = t; lt.p2 = t; lt.p2.x = INT_MAX; for (i = 1; i <= N; i++) { lp.p1 = p[i]; lp.p2 = p[i]; if (!intersect(lp,lt)) { lp.p2 = p[j]; j = i; if (intersect(lp,lt)) count++; } } return count & 1; } • le programme suppose que p[1] contient le point avec la plus petite valeur de x parmi les points avec la plus petite valeur de y; ceci garantit que si p[1] est sur la droite de test, p[0] n'y est pas ! Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 10 Commentaires sur l'appartenance d'un point à l'intérieur un polygone • des méthodes plus simples peuvent être utilisées dans des cas particuliers - lorsque le polygone est un triangle ou un quadrilatère - lorsque le polygone est convexe Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 11 Enveloppe convexe • troisième problème: déterminer les frontières d'un nuage (grand ensemble) de points • il est ainsi possible de distinguer les points de la frontière et les points à l'intérieur • la définition de la frontière repose sur la propriété de convexité: - un polygone P est convexe si le segment de droite reliant deux points quelconques de P est entièrement inclus dans P • l'enveloppe convexe d'un ensemble de points est le plus petit polygone convexe qui englobe tous les points; c'est aussi le plus court chemin entourant tous les points • étant donné N points, le polygone convexe est formé de 3 à N points Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 12 Illustration de polygones convexes Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 13 Enoncé du problème • étant donné un tableau de N points, l'algorithme de construction du polygone convexe réorganise le tableau de sorte que ses points figurent au M premières positions • ainsi, la construction de l'enveloppe convexe revient à une sorte de tri "bidimensionnel" • comme pour le tri, la construction de l'enveloppe convexe de N points est de complexité N log N dans le pire cas • dans le cas où plusieurs points sont alignés sur une arête de l'enveloppe, les algorithmes peuvent poser des problèmes et réagir de différentes façon Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 14 Méthode de l'emballage de paquets • algorithme naturel dû à R.A. Jarvis (1973) • en partant d'un sommet de l'enveloppe on effectue un balayage circulaire avec une droite jusqu'à rencontrer un nouveau point qui devient le sommet suivant; l'algorithme s'arrête lorsqu'on tombe sur le point de départ • comme point de départ on peut choisir un point dont l'une des coordonnées est minimale ou maximale • l'algorithme est similaire au tri par sélection, où à chaque étape on sélectionne le point qui minimise le changement d'angle • l'angle peut être approximé par une fonction theta représentant un pseudo-angle Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 15 Illustration de l'emballage de paquets Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 16 Illustration du tri des points lors de l'emballage de paquets Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 17 Algorithme de l'emballage de paquets int wrap (struct point p[], int N) { int i, min, M; float th, v; struct point t; for (min = 0, i = 1; i < N; i++) if (p[i].y < p[min].y) min = i; p[N] = p[min]; th = 0.0 for (M = 0; M < N; M++) { t = p[M]; p[M] = p[min]; p[min] = t; min = N; v = th; th = 360.0; for (i = M+1; i <= N; i++) if (theta(p[M], p[i]) > v) if (theta(p[M], p[i]) < th) { min = i; th = theta(p[M], p[min]); } if (min == N) return M; } } Programmation 3A: Algorithmique 11 Algorithmes géométriques © R. Ingold, Université de Fribourg 14.01.03 - 18 Pseudo-angle polaire • le caclul de l'angle au moyen de la fonction Arctg peut être remplacé par une fonction plus simple qui conserve la même relation d'ordre: dy/(dy+dx) float theta(struct point p1, struct point p2) { int dx, dy, ax, ay; float t; dx = p2.x - p1.x; ax = abs(dx); dy = p2.y - p1.y; ay = abs(dy); t = (ax+ay == 0) ? 0 : (float) dy/(ax+ay); if (dx < 0) t = 2-t; else if (dy < 0) uploads/Geographie/ transp-11.pdf