Delaunay Generalites Od

De la geometrie algorithmique

au calcul geometrique

l’exemple

de la triangulation de Delaunay

Definition, proprietees, premiers algorithmes

Geometrie algorithmique

Probleme geometrique

Analyse des performances

Borne inferieureBorne superieureComplexite asymptotique

Analyse dans le cas le pireAnalyse en moyenne

Definition de

la triangulation de Delaunay

L’exemple

L’exemplerecherche de plus proche voisin





Voronoı L’exemplerecherche de plus proche voisin

Voronoı L’exemple

Voronoı

Delaunay

L’exemple

Voronoı

Delaunay

Le probleme emblematique de la geometrie algorithmique

L’exemple

Voronoı

Probleme du plus proche voisin

Voronoı


Voronoı


Voronoı


Cellule de Voronoı

Vi = q;∀j 6= i|qpi| ≤ |qpj|

LA propriete de


Voronoı

Voronoı

Propriete du cercle vide

Voronoı


Delaunay

Voronoı


Delaunay

Quelques applications de


graphe des plus proche voisins

Applications “theoriques”


p

q


q plus proche voisin de p

alors pq arete de Delaunay




plus grand cercle vide


plus grand cercle vide

Recherche a rayon fixe






Arbre couvrant de longueur minimale


Arbre couvrant de longueur minimale


Applications

Reconstruction

Applications

Maillage

Reconstruction

Applications

Maillage / Remaillage

Reconstruction

Applications


Reconstruction

Applications


Reconstruction

Plainfication de trajectoires

Proprietes de


Relation d’Euler

c: nombre de cellules (inclus ∞)

a: nombre d’aretes

n: nombre de sommets

n− a + s = 2

Relation d’Euler




1− 3 + 3 = 2

n− a + s = 2

Relation d’Euler




n− a + s = 2

0− 1 + 1 = 0

Relation d’Euler




n− a + s = 2

1− 1 + 0 = 0

Nombre d’aretes orienteesdans une triangulation

2a = 3c + k

k: taille cellule ∞

Relation d’Euler

c− a + n = t + 1− a + n = 2

Triangulation

2a = 3t + k

t = 2n− 2− k

a = 3n− 3− k

Propriete : le plus petit angle est maximal

Maximise dans l’ordre lexicographique

Optimalite locale vs globale

locallementDelaunay

mais pas globalementDelaunay

Theoreme

Localement Delaunay partout

Globalement Delaunay

⇐⇒

Demonstration:

Demonstration:

Soit t localement mais pas globalement Delaunay

Demonstration:


Demonstration:


Demonstration:


Demonstration:


Comme le nombre de points est fini

Optimalite locale et plus petit angle

Cas de 4 points


Cas de 4 points

Lemme:Pour 4 points en position convexeDelaunay ⇐⇒ maximise le plus petit angle


Cas de 4 points

δ

δ le plus petit angle


Cas de 4 points

pq

rs

δ

δ

≤ δ

TheoremeDelaunay ⇐⇒ maximise le plus petit angle


Demonstration:


Triangulation max pour ordre des angles


Demonstration:



=⇒ Max dans chaque quadrilatere


Demonstration:




=⇒ localement Delaunay


Demonstration:




=⇒ localement Delaunay

=⇒ globalement Delaunay


Demonstration:

Predicats pour


Algorithmes geometriques

Prendre des decisionsrepose sur des predicats geometriques

Entree de taille constante

Sortie discrete (signe)

Predicats

Predicats

Predicat d’orientation

∣∣∣∣∣∣∣∣xq − xp xr − xp

yq − yp yr − yp

∣∣∣∣∣∣∣∣

p

q

r

−

p

q

r

0

p

q

r+

Predicats

Predicat de cocyclicite

∣∣∣∣∣∣∣∣xq − xp xr − xp xs − xp

yq − yp yr − yp ys − yp

(xq−xp)2+(yq−yp)

2 (xr−xp)2+(yr−yp)

2 (xs−xp)2+(ys−yp)

2

∣∣∣∣∣∣∣∣

p

q r

s

Π : x2 + y2 = z

p = (xp, yp)

p? = (xp, yp, x2p + y2

p)

C : x2 + y2 − 2ax− 2by + c = 0

C† : z − 2ax− 2by + c = 0

p ∈ ∂C

p? ∈ C†

p ∈ C

p? au dessous de C†

p 6∈ C

p? au dessus de C†

Predicat d’orientation 3D

Predicat de cocyclicite

PredicatsPredicat : cercle le plus a droite p1

q1

r1 = p2

q2

r2

6 points

polynome de degre 24

Predicats

Problemes de robustesse

Paradigme du calcul exact

Arithmetique arrondie

Pas de coherence entre les resultats arrondis

Structures de donnees pour

la triangulation (de Delaunay)

Geometrie

(x, y)

connectivite

Geometrie

(x, y)

Representationbasee triangles


triangle :


trois sommets

triangle :


trois sommets

triangle :

trois voisins


trois sommets

triangle :

trois voisins

numerotation : voisin oppose au sommet


sommet :


sommet :x, yun triangle



tourner autour d’un sommet


v


v

t

t = v->triangle;


v

t

t = v->triangle;

i tel que t->v[i] == v;

i


v

t

t = v->triangle;


i

t = t->n[ i+1 mod 3 ];

i+1


v

t

t = v->triangle;


i

t = t->n[ i+1 mod 3 ];

i+1

t



tourner dans l’autre sens


v


v

t

t = v->triangle;


v

t

t = v->triangle;


i


v

t

t = v->triangle;


i

t = t->n[ i-1 mod 3 ];

i-1

t

Representationbasee (demi) aretes



twin


next


previous


target


face


(x, y)


Representation

tourner autour d’un sommet

basee (demi) aretes

Representation

v

basee (demi) aretes

Representation

v e

e = v->edge;

basee (demi) aretes

Representation

v e

e = v->edge;

e = e->twin->next->next;

basee (demi) aretes


Representation

tourner dans l’autre sens

basee (demi) aretes

Representation

v

basee (demi) aretes

Representation

v e

e = v->edge;

basee (demi) aretes

Representation

v e

e = v->edge;

e = e->next->twin;

basee (demi) aretes

Borne inferieure pour


Borne inferieure pour Delaunay


Delaunay sert a trier


Delaunay sert a trier

Ω(n log n)

Premiers algorithmes pour


Algorithme incrementral



en conflit


pas en conflit


pas en conflit



Trouver les triangles en conflit




Supprimer les triangles en conflit



Trianguler le trou


Un nouveau triangle est de Delaunay


Un nouveau triangle est de Delaunay


Complexite

O(n) pour chaque insertion

O(n2)


Complexite


O(n2)

Ω(n2)


Complexite


O(n2)

Ω(n2)


Insertion


Insertion


Insertion


Insertion


Insertion

Strategies de localisation


Insertion


Tous

O(n)


Insertion


Marche rectiligne

O(√

n) en moyenne


Insertion


Marche par visibilite


Insertion




Insertion



O(√

n) ???? en moyenne


Insertion


Jump & walk


Insertion


Jump & walk


Insertion


Jump & walk

O( 3√

n) en moyenne



Complexite

O(n2)

O(n√

n) en moyenne

O(n 3√

n) en moyenne


Complexite

O(n2)

Ω(n2) dans le cas le pire

O(n√

n) en moyenne

O(n 3√

n) en moyenne

Bascule de diagonales





Complexite

Algorithme en O(n2)


Complexite

Une arete basculee n’est

jamais reconstruite

(les nouvelles aretes

sont toujours dessous)

Algorithme en O(n2)


Bascule de diagonales et algorithme incremental


Localisation


LocalisationNon localement Delaunay

Bascule


LocalisationNon localement Delaunay ?Bascule ?



Bascule

OUI





Bascule

NON





Bascule

NON





Bascule

OUI





Bascule

NON





Bascule

NON





Bascule

OUI





Bascule

NON





Bascule

OUI





Bascule

NON





Bascule

NON


OUI]


OUI]

] aretes creees


NON]


NON]

] triangles crees


O(degre( ))

C’est tout pour aujourd’hui

Documents

Delaunay Generalites Od