Chapitre Triangulation et applications

Publié par

Chapitre 3 : Triangulation et applications Arnault Ioualalen, Arnaud Mary, Helene Amodeos, Benoit Lopez 1 Probleme de la triangulation But : Partitionner en triangles un polygone ou l'enveloppe convexe d'un en- semble de points. Motivations : – Imagerie 3D – Decomposition d'un polygone : calcul d'aire, calcul de plus court chemin... – Reconstruction 3D : construire un maillage realiste a partir d'un ensemble de points. Objectif : Faire de (( belles )) triangulations. Fig. 1 – Exemple d'une mauvaise triangulation Fig. 2 – Exemple d'une bonne triangulation 1

  • tri des points

  • eci

  • enveloppe convexe

  • triangulation

  • illustration du principe de l'algorithme

  • algorithme precedent

  • points visibles de eci

  • partition de l'interieur du polygone


Publié le : mardi 19 juin 2012
Lecture(s) : 377
Source : lirmm.fr
Nombre de pages : 11
Voir plus Voir moins
1
Chapitre 3 : Triangulation et applications
ArnaultIoualalen,ArnaudMary,He´l`eneAmod´eos,BenoitLopez
Probl`emedelatriangulation
But :Partitionner en triangles un polygone ou l’enveloppe convexe d’un en-semble de points.
Motivations : – Imagerie 3D De´compositiondunpolygone:calculdaire,calculdepluscourtchemin... Reconstruction3D:construireunmaillagere´alistea`partirdunensemble de points.
Objectif :
Faire debellestriangulations.
Fig.1 – Exemple d’une mauvaise triangulation
Fig.2 – Exemple d’une bonne triangulation
1
Unprobl`emeconnexea`latriangulation: du plan (diagramme deVorono¨ı).
D´eterminerunr´egionnement
Exemple 1.1La triangulation permet notament de : – Trouver le site le plus proche d’un point du plan (bureau de poste). Trouveruncheminqui´eviteaumieuxtouslessites(mines).
Fig.3 – Exemple du bureau de poste
D´enition1.1SoitPun ensemble de points. Une triangulation dePest un ensemble de trianglesτ= (T1, T2, ..., Tt) tels que : 1. les sommets des triangles sont des points deP, 2.pP,i[1..t]pest un sommet deTioup /Ti, 3. (T1, T2, ..., Tt) est une partition deEC(P).
Pour un polygone simple (i.e. sans trou) Q = (p0, p1, ..., pr, p0), une triangu-lation de Q est un ensemble de trianglesτ= (T1, T2, ..., Tt) tel que : 1. les sommets des triangles sont des points deP, 2.pP,i[1..t]pest un sommet deTioup/ Ti, 3. (T1, T2, ..., Tt)gylo.enodrpuiruetne´leiiondrtitnepaestu
Remarque : tiques.
Seuleladernie`reconditionchange,lesdeuxpremi`eressontiden-
2
Exemple 1.2
Fig.lbseoprunuˆ4mm2etereiangulationspossiemnsedbloiepsnt
Dans les 2 cas, il existe plusieurs triangulations possibles, mais on a toujours les invariants suivants (voir chapitre sur les graphes planaires) : – SoitPun ensemble denpoints, si on note : ne= le nombre de sommets deEC(P). mcrts´e´e`as(rtpaedriengmsederembnole=EC(P)). tnombredetrianglecs´r´ese.el= alorsonalesegalit´essuivantes: m= 3(n1)ne. t= 2(n1)ne. – SoitQugay`neopnlonsommets, si on notemile nombre de segments cre´e´s`alint´erieurdeQ,onalese´galite´ssuivantes: mi=n3. t=n2.
De´nition1.2Le dual d’une triangulationτ= (T1, T2, ..., Tt) est le graphe dont les sommets sont 1, .., tseostnelpsiaersetdontlesarˆet{i,j}pour lesquelles TietTjutnorfennu.eocmme`ernoit
2
Fig.5 – Duals de triangulations d’un ensemble de points et d’un polygone
Triangulation d’un ensemble de points : algorithmeincr´emental
Onconsid`ereP= (p1, p2, ..., pr) un ensemble de points du plan.
3
Principe de l’algorithme :On trie les points de P par ordre lexicographique 0 0 0 0 0 croissant, i.e. (x, y)<lex(yx , )(x < x)ou(x=y < yx et ). Puisonlesins`eredanslatriangulation. On notep1, p2, ..., pnetnassioetonnotlseopnisttri´esparordrecrECil’en-veloppe convexeEC(p1, p2, ..., pi).On dit qu’un pointpjdeECiest visible par pi+1si le segment [pi+1pj] ne coupe pasECioP.e´atepuler`alurtriangion+ 1 cherchetouslespointsvisiblesparlepointquoncherche`aajouter.
Fig.6 – Illustration du principe de l’algorithme
DufaitquelespointsdePsonttri´esparordrelexicographiqueonalelemme suivant :
Lemme 2.1i∈ {1, ..., n}on a : piest un point deECi. – les points visibles deECiforment un intervale. piest visible parpi+1.
Decefaitlorsducalculdele´tapei+1 les points visibles deECierchrechtna`eros autour depi
Fig.7 – Points visibles parpi+1
4
On a l’algorithme suivant :
Algorithme 1TRIANGULATION INCREMENTALE :es´ennDoP= (p1, ..., pn) des points du plan Sortie :τune triangulation de P τ← {p1, p2, p3} EC(p1, p2, p3) ou (p1, p3, p2) (dans le sens direct) pour=i`3na1-faire # ajout depi+1 On noteEC= (q1, ..., ql) avecqk=pi tant que(det(pi+1qk, pi+1qk+1)<0)faire ττ∪ {pi+1qkqk+1} kk+ 1 fin tant que khautk Retrouver k tel queqk=pi tant que(det(pi+1qk, pi+1qk1)>0)faire ττ∪ {pi+1qkqk1} kk1 fin tant que kbask Misea`jourdeEC:onremplace(qkbas+1qkbas+2...qkhaut1) parpi+1 fin pour Retourner :τ
Preuve :
Onadmetlavalidite´delalgorithme.
Complexite´: – le tri des points peut se calculer enO(n log(n)) lamise`ajourdelenveloppeconvexepeutsimplementerenO(1) avec une listedoublementchaˆın´ee. laboucleprincipalecr´eeraauplus2ntriangles. Total :O(n log(n))
3
Triangulation de Delaunay
Motivation :Ampauioirfensresddairt-ugn´eliorerlalgorihtemrpe´´cdeneqt lationsmoches
5
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.