Construction de partitions élémentaires de segments dans le plan
6
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
6
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Construction de partitions élémentaires
de segments dans le plan
Mathieu Brévilliers, Nicolas Chevallier, Dominique Schmitt
Laboratoire Mathématique, Informatique et Applications
4-6, rue des Frères Lumière 68093 Mulhouse Cédex 07
RÉSUMÉ
Nous généralisons la notion de triangulation à un ensemble de points et de segments du plan qui sont disjoints. Nous
définissons des partitions élémentaires de tels ensembles et nous donnons diverses propriétés (formes des arêtes,
nombres de faces et d'arêtes) qui permettent de déduire un algorithme de construction par balayage en temps O(n log n)
à l’aide d’une structure de données adpatée. Nous définissons ensuite la partition élémentaire de Delaunay et nous
montrons qu’elle correspond au dual du diagramme de Voronoï de segments.
Mots-clés : partition élémentaire, algorithme par balayage, Delaunay, Voronoï.
1. INTRODUCTION
La triangulation d’un ensemble de points (encore appelée maillage triangulaire) est un problème classique qui a été
largement étudié en géométrie algorithmique. Ce problème admet de nombreuses applications telles que la modélisation
de surfaces. Il a été démontré que la triangulation la plus régulière d’un ensemble de points du plan est la triangulation
de Delaunay [La77]. La notion de triangulation a ensuite été généralisée à un ensemble de points et de segments avec
l’introduction de la triangulation contrainte et il a été démontré que la triangulation de Delaunay contrainte d’un
ensemble de ...
Voir
de segments dans le plan
Mathieu Brévilliers, Nicolas Chevallier, Dominique Schmitt
Laboratoire Mathématique, Informatique et Applications
4-6, rue des Frères Lumière 68093 Mulhouse Cédex 07
RÉSUMÉ
Nous généralisons la notion de triangulation à un ensemble de points et de segments du plan qui sont disjoints. Nous
définissons des partitions élémentaires de tels ensembles et nous donnons diverses propriétés (formes des arêtes,
nombres de faces et d'arêtes) qui permettent de déduire un algorithme de construction par balayage en temps O(n log n)
à l’aide d’une structure de données adpatée. Nous définissons ensuite la partition élémentaire de Delaunay et nous
montrons qu’elle correspond au dual du diagramme de Voronoï de segments.
Mots-clés : partition élémentaire, algorithme par balayage, Delaunay, Voronoï.
1. INTRODUCTION
La triangulation d’un ensemble de points (encore appelée maillage triangulaire) est un problème classique qui a été
largement étudié en géométrie algorithmique. Ce problème admet de nombreuses applications telles que la modélisation
de surfaces. Il a été démontré que la triangulation la plus régulière d’un ensemble de points du plan est la triangulation
de Delaunay [La77]. La notion de triangulation a ensuite été généralisée à un ensemble de points et de segments avec
l’introduction de la triangulation contrainte et il a été démontré que la triangulation de Delaunay contrainte d’un
ensemble de ...
Construction de partitions élémentaires
de segments dans le plan
Mathieu Brévilliers, Nicolas Chevallier, Dominique Schmitt
Laboratoire Mathématique, Informatique et Applications
4-6, rue des Frères Lumière 68093 Mulhouse Cédex 07
RÉSUMÉ
Nous généralisons la notion de triangulation à un ensemble de points et de segments du plan qui sont disjoints. Nous
définissons des partitions élémentaires de tels ensembles et nous donnons diverses propriétés (formes des arêtes,
nombres de faces et d'arêtes) qui permettent de déduire un algorithme de construction par balayage en temps
O(n log n)
à l’aide d’une structure de données adpatée. Nous définissons ensuite la partition élémentaire de Delaunay et nous
montrons qu’elle correspond au dual du diagramme de Voronoï de segments.
Mots-clés :
partition élémentaire, algorithme par balayage, Delaunay, Voronoï.
1. INTRODUCTION
La triangulation d’un ensemble de points (encore appelée maillage triangulaire) est un problème classique qui a été
largement étudié en géométrie algorithmique. Ce problème admet de nombreuses applications telles que la modélisation
de surfaces. Il a été démontré que la triangulation la plus régulière d’un ensemble de points du plan est la triangulation
de Delaunay [La77]. La notion de triangulation a ensuite été généralisée à un ensemble de points et de segments avec
l’introduction de la triangulation contrainte et il a été démontré que la triangulation de Delaunay contrainte d’un
ensemble de points et de segments du plan est la plus régulière [LL86],[Ch89]. Cela permet une modélisation plus
crédible d’un terrain montagneux avec, par exemple, des crêtes, des vallées, et des rivières imposées. Une autre solution
pour la triangulation d’un ensemble de points et de segments est l’utilisation des triangulations de Steiner [BE92] : cela
consiste à ajouter un nombre raisonnable de points supplémentaires tout en fixant a priori la qualité des triangles de la
triangulation finale. Ces triangulations sont particulièrement adaptées à la discrétisation d'une partie bornée du plan
pour résoudre un problème par la méthode des éléments finis. Cependant ces généralisations se ramènent toujours à un
ensemble de points pour résoudre le problème. Au contraire, nous proposons une approche basée directement sur les
segments qui avait déjà été décrite par Chew et Kedem [CK89] dans un cas pratique très spécifique. Les nouvelles
subdivisions que nous proposons pourraient permettre d’améliorer les triangulations de Delaunay contraintes et les
triangulations de Steiner définies jusqu'à présent.
La section 2 présente la notion de partition élémentaire qui est une extension de la notion de triangulation à un ensemble
de segments disjoints du plan, et donne plusieurs propriétés remarquables des partitions élémentaires. La section 3
décrit un algorithme de construction par balayage d'une partition élémentaire d'un ensemble de points et de segments du
plan, ainsi que la structure de données utilisée pour représenter les partitions élémentaires sur machine. La section 4
définit la notion de partition élémentaire de Delaunay et donne quelques propriétés intéressantes à ce sujet. Enfin la
section 5 précise les objectifs qu'il sera intéressant d'atteindre à l'aide de ces premiers résultats.
2. PARTITION ÉLÉMENTAIRE D’UN ENSEMBLE DE SEGMENTS DU PLAN
Définition 1.
Soit
S
un ensemble de segments et de points du plan qui sont disjoints : les éléments de
S
sont appelés des
sites. Une partition élémentaire
P
de
S
est une partition de l'enveloppe convexe de
S
en sites, faces, et arêtes telle que:
•
l'ensemble
F
des faces de
P
est un ensemble maximal de triangles ouverts disjoints qui ne coupent pas
S
et tels
que les trois sommets d'un même triangle sont sur trois sites distincts de
S
,
•
les arêtes de
P
sont les composantes connexes de l'enveloppe convexe privée de
S
et de
F
.
De manière plus intuitive, on peut construire une partition élémentaire de
S
en plaçant dans l'enveloppe convexe de
S
un
maximum de triangles disjoints dont les sommets sont sur trois sites distincts (figure 1). Les arêtes de
P
sont définies
par complémentarité mais elles peuvent être décrites plus précisément.
Propriété 1.
La fermeture d’une arête de
P
coupe exactement deux sites de
S
.
Preuve abrégée.
L’idée de la preuve consiste à réaliser une triangulation contrainte d’une arête fermée qui coupe au
moins trois sites pour montrer que cette triangulation contient au moins un triangle dont les sommets sont sur trois sites
de
S
distincts. Cela revient à montrer que si une arête fermée coupe au moins trois sites de
S
, alors il est possible
d’ajouter une face à l’intérieur de cette arête (figure 2). Ceci contredit l’hypothèse de maximalité du nombre de faces de
P
.
Figure 1.
Une partition élémentaire de
S
. On
distingue les sites en noir, les faces en blanc, et les arêtes en gris.
Figure 2.
Si une arête fermée coupe plus de deux sites, alors on peut ajouter une face (en pointillés) dans cette arête.
Propriété 2.
Une arête de
P
est soit un segment de droite, soit un triangle, soit un quadrilatère.
Preuve.
Comme une arête d'une partition élémentaire est adjacente à exactement deux sites, on peut en déduire les
formes géométriques possibles d'une arête. La forme d'une arête varie selon la nature des portions de sites adjacents à
l'arête et de leurs orientations. L'arête qui relie les deux sites est un segment de droite si les portions de sites adjacents
sont des points (figure 3a), un triangle si l'une des portions de sites adjacents est un segment et l'autre un point (figure
3b) et un quadrilatère si les deux portions de sites adjacents sont des segments (figure 3c). Dans ce dernier cas on peut
remarquer que le quadrilatère n'est pas forcément convexe (figure 3d).
Figure 3.
Forme des arêtes de
P
: segment de droite (a), triangle (b) ou quadrilatère (c), (d).
Comme une arête de
P
est adjacente à exactement deux sites de
S
, on peut dire que l'arête « relie ces deux sites »,
comme on a l'habitude de le faire pour les graphes ou les triangulations de points. Cette remarque permet d'appréhender
la notion de topologie d’une partition élémentaire.
A toute partition élémentaire
P
de
S
, on peut associer un diagramme topologique
D(P)
tel que :
•
pour tout site
t
de
S
,
D(t)
est un sommet de
D(P)
,
•
pour toute arête de
P
adjacente à deux sites
t
et
u
, il existe une ligne simple qui relie
D(t)
à
D(u)
dans
D(P)
,
•
pour toute face de
P
dont les sommets sont dans l'ordre trigonométrique sur les sites
t
,
u
et
v
de
S
,
(D(t),D(u),D(v))
est une face de
D(P)
d’orientation positive.
Propriété 3.
A toute partition élémentaire
P
de
S
, on peut associer un diagramme topologique
D(P)
planaire.
Preuve.
Supposons qu'on dispose d'une partition élémentaire de
S
(figure 4a) et qu'on isole un segment de
S
dans un
convexe. On peut remplacer ce site par un point quelconque à l'intérieur du convexe tel que les faces incidentes à ce site
sont maintenant incidentes à ce nouveau point dans le même ordre. En effectuant cette opération pour tous les segments
de
S
, on obtient une nouvelle représentation géométrique qui conserve la planarité et la topologie initiale. Dans ce
nouveau diagramme, chaque arête de
P
est toujours adjacente à exactement deux sites et chaque arête est soit une ligne
polygonale, soit un polygone simple. Donc on peut trouver dans chaque arête une ligne simple qui relie les deux sites
adjacents à l'arête. Autrement dit on peut remplacer toutes les arêtes par des lignes simples tout en conservant la
planarité et la topologie initiale (figure 4b).
Figure 4.
Une partition élémentaire (a) et son diagramme topologique associé (b).
On remarque que les faces bornées du diagramme topologique ont toutes trois côtés (figure 4b) : ces faces représentent
les faces triangulaires de la partition élémentaire initiale. La planarité du diagramme topologique nous permet d'utiliser
la formule d'Euler pour montrer que les nombres de faces et d'arêtes dans le diagramme topologique et dans la partition
élémentaire sont des invariants de l’ensemble de sites. On obtient les résultats suivants :
Propriété 4.
Une partition élémentaire de
S
contient
3n – n' – 3
arêtes et
2n – n' – 2
faces où
n
est le nombre de sites de
S
, et
n'
est le nombre de côtés de l'enveloppe convexe de
S
qui ne sont pas des sites, c'est-à-dire que
n'
est le nombre de
côtés de la face externe.
Cette propriété est à la fois surprenante et intéressante puisque le nombre d'arêtes et de faces d'une partition élémentaire
dépend uniquement de l'ensemble des sites et pas de la manière dont on place les faces dans l'enveloppe convexe.
3. ALGORITHME DE CONSTRUCTION PAR BALAYAGE
D’UNE PARTITION ÉLÉMENTAIRE
Sur machine on représente une partition élémentaire par son diagramme topologique en utilisant une structure de carte,
c'est-à-dire qu'on dispose d'un ensemble de demi-arêtes, d'une involution qui associe à une demi-arête sa demi-arête
opposée et d'une permutation qui associe à chaque demi-arête son successeur dans l'ordre trigonométrique autour du site
dont elle est issue. Cette structure permet de représenter la topologie d'une partition élémentaire mais ce n'est pas
suffisant car plusieurs partitions élémentaires ont en commun le même diagramme topologique.
Il faut ajouter les informations géométriques qui indiquent la position des faces de la partition élémentaire. Dans la
structure de carte, chaque face interne a trois demi-arêtes représentatives. Il suffit d'ajouter à ces demi-arêtes les
coordonnées des sommets des faces pour caractériser leur position géométrique (figure 5).
Figure 5.
Une partition élémentaire (a), son diagramme topologique (b), et la structure de carte associée (c). La face de
gauche est représentée par les demi-arêtes pleines, la face de droite par les demi-arêtes en tirets, et la face externe par
les demi-arêtes en pointillés.
Après avoir défini la structure de données nécessaire, nous pouvons maintenant présenter un algorithme de construction
d'une partition élémentaire. Pour introduire cet algorithme, il faut montrer la similitude qui existe entre les partitions
élémentaires et les triangulations contraintes. Commençons par rappeler rapidement la définition d'une triangulation
contrainte. Soit
S
un ensemble de points et de segments du plan. Une triangulation contrainte de
S
est une triangulation
des points et des extrémités des segments de
S
telle que les segments de
S
sont des arêtes de la triangulation (figure 6a).
On remarque qu'une triangulation contrainte comporte deux types de triangles : d’une part des triangles dont les
sommets sont sur trois sites de
S
distincts, et d'autre part des triangles dont l'un des côtés est un segment de
S
(figure 6).
Si on colorie en gris les triangles du deuxième type et qu’on fusionne les triangles gris adjacents, on obtient une
partition élémentaire telle que les sommets de ses faces sont exclusivement sur des points ou des extrémités de
segments de
S
. Cela signifie que ces partitions élémentaires particulières peuvent être construites en adaptant un
algorithme de construction de triangulation contrainte.
Figure 6.
Partition élémentaire (b) obtenue à partir d’une triangulation contrainte (a).
Nous adaptons pour cela l'algorithme de construction d'une triangulation contrainte par balayage donné par
Edelsbrunner [Ed00]. L’algorithme balaye le plan avec une droite verticale qui se déplace de
–
∞
vers
+
∞
. Les points et
les extrémités de segments de
S
sont traités au fur et à mesure qu’ils sont rencontrés par la droite. Supposons que les
k
premiers de ces points aient été traités et que la partie de la partition élémentaire finale qui s’appuie sur ces points ait été
construite. Considérons la décomposition de la droite de balayage en intervalles formés par les intersections de la droite
avec les segments de
S
dont une et une seule extrémité a déjà été traitée (voir figure 7a). On peut montrer que la partie
de la partition élémentaire déjà construite qui est visible depuis un intervalle donné est convexe. Au cours de l'insertion
du
k+1
ième point, on distingue trois cas possibles :
•
Dans le premier cas, le nouveau point est un point de
S
(figure 7b) : on commence par localiser l'intervalle dans
lequel se trouve le point, puis on ajoute les arêtes qui relient le nouveau point à tous les sites de la frontière de
la partition courante qui sont visibles de ce nouveau point.
•
Dans le deuxième cas, le nouveau point est l'extrémité gauche d'un segment de
S
(figure 7c) : on localise le
nouveau point et on ajoute les arêtes comme dans le cas précédent. Il faut encore mettre à jour la
décomposition de la droite en intervalles puisqu’elle coupe un segment supplémentaire.
•
Enfin dans le troisième cas, le nouveau point est l'extrémité droite d'un segment de
S
(figure 7d) : ce segment
délimite deux intervalles et on effectue l’insertion du nouveau point pour chacun des intervalles comme
précédemment. Il faut ensuite fusionner les deux intervalles car la droite de balayage coupe maintenant un
segment de moins.
Dans tous les cas, une fois que le nouveau point est inséré, la frontière de la partition élémentaire visible depuis un
intervalle donné reste bien convexe.
(a)
(b)
(c)
(d)
Figure 7.
Insertion du
k+1
ième point en fonction de sa nature.
Théorème 1.
L’algorithme décrit ci-dessus construit une partition élémentaire de
S
en temps
O(n log n)
.
Preuve.
Le nombre de points à insérer est en
O(n)
où
n
est le cardinal de
S
. Ces points sont triés en temps
O(n log n)
.
Pour stocker les intervalles, on peut choisir une structure de données telle qu’un arbre binaire de recherche qui permet
de faire une recherche ou une mise à jour en temps
O(log n)
. De plus, pour chaque intervalle l'algorithme conserve le
dernier point inséré dans cet intervalle pour pouvoir y accéder en temps constant. L'algorithme effectue au pire une
recherche et une mise à jour par point traité et insère des arêtes en temps constant par arête. Finalement, comme le
nombre d’arêtes est majoré par
3n
d’après la propriété 4, l'algorithme s'exécute en temps
O(n log n)
.
4. PARTITION ÉLÉMENTAIRE DE DELAUNAY
Définition 2.
Une partition élémentaire
P
de
S
est dite de Delaunay si le cercle circonscrit à chaque face de
P
est vide,
c'est-à-dire que l'intérieur du cercle ne coupe pas
S
.
Propriété 5.
Quel que soit
S
, il existe une partition élémentaire de Delaunay de
S
.
Preuve intuitive.
Supposons qu'on dispose pour l'instant de l'enveloppe convexe de
S
: on peut dire que c’est une
partition non élémentaire de
S
dans ce sens que le nombre de faces n’est pas maximal. On dit qu'un cercle est tangent à
un site s'il coupe ce site en un seul point. Etant donnés deux sites consécutifs sur la frontière de l'enveloppe convexe, il
existe un cercle vide dont le diamètre tend vers l'infini et qui est tangent à ces deux sites (figure 8a). Si on réduit le
diamètre de ce cercle vide et qu'il reste tangent à ces deux sites, on peut le faire glisser vers l'intérieur de l'enveloppe
convexe jusqu'à ce qu'il soit tangent à un troisième site de
S
. Le cercle est alors circonscrit à une face de Delaunay de la
partition élémentaire de Delaunay de
S
. On peut continuer à faire glisser le cercle vers l’intérieur de l’enveloppe
convexe pour obtenir les faces de Delaunay adjacentes à celle qu’on vient d’ajouter (figure 8b). Si on continue à faire
glisser les cercles sur les sites de cette façon, on va finir par placer dans l’enveloppe convexe un maximum de faces de
Delaunay et on obtiendra la partition élémentaire de Delaunay de
S
(figure 8c).
(a)
(b)
(c)
Figure 8.
Construction intuitive de la partition élémentaire de Delaunay de
S
.
Remarque.
On peut également montrer que si les sites de
S
sont en position générale, c’est-à-dire s’il n’existe pas de
cercle tangent à plus de trois sites, alors la partition élémentaire de Delaunay est unique.
A l’aide de la preuve précédente, on peut remarquer une propriété intéressante des arêtes d’une partition élémentaire de
Delaunay. Quand le cercle glisse sur deux sites pour passer d’une face à une autre, le cercle passe par une infinité de
positions dans lesquelles le cercle est vide et tangent à ces deux sites. Si pour chaque position du cercle on trace le
segment qui relie les points de tangence du cercle avec les deux sites, on remarque que l’ensemble de ces segments
recouvre l’arête. Finalement on peut voir une arête d’une partition élémentaire de Delaunay comme une réunion de
segments inscriptibles dans des cercles vides.
Propriété 6.
Une arête de la partition élémentaire de Delaunay
P
de
S
est une réunion connexe de segments tels qu'il
existe pour chaque segment un cercle vide qui passe par ses extrémités.
Cette propriété permet de démontrer la dualité entre le diagramme de Voronoï de segments de
S
et la partition
élémentaire de Delaunay de
S
. Tout d'abord nous rappelons brièvement la définition du diagramme de Voronoï de
segments : la région de Voronoï d'un site de
S
est l'ensemble des points du plan plus proches de ce site que de tous les
autres sites de
S
. Le diagramme de Voronoï de
S
est la partition du plan formée par les régions de Voronoï des sites de
S
(figure 9a).
Théorème 2.
La partition élémentaire de Delaunay de
S
est duale du diagramme de Voronoï de segments de
S
.
Preuve.
Observons maintenant plus en détail une partie d’un diagramme de Voronoï de segments, et superposons le
avec la partition élémentaire de Delaunay correspondante (figure 9b). Un côté commun aux régions de Voronoï de deux
sites
t
et
u
de
S
est une partie connexe de la médiatrice de
t
et
u
qui est plus proche de
t
et
u
que de tous les autres sites
de
S
. Autrement dit, un point de ce côté est le centre d'un cercle vide tangent à
t
et
u
. D'après la propriété précédente, le
segment qui joint les points de tangence de ce cercle avec
t
et
u
fait partie de l'arête qui est adjacente à
t
et
u
dans la
partition élémentaire de Delaunay de
S
. Cela met en évidence la dualité entre les arêtes du diagramme de Voronoï de
segments et les arêtes de la partition élémentaire de Delaunay. La dualité entre les sommets de Voronoï et les faces de la
partition élémentaire de Delaunay est plus directe. Chaque sommet de Voronoï est équidistant de trois sites
t
,
u
et
v
de
S
, donc c'est le centre d'un cercle vide tangent aux sites
t
,
u
et
v
(figure 9b). Les points de tangence de ce cercle
correspondent aux sommets d'une face de la partition élémentaire de Delaunay de
S
qui s'appuie sur
t
,
u
et
v
.
(a)
(b)
Figure 9.
La partition élémentaire de Delaunay est le dual du diagramme de Voronoï de segments.
Remarque.
Le dual du diagramme de Voronoï de segments avait déjà été défini par Chew et Kedem dans le cadre de la
résolution d'un problème de placement d'un motif polygonal de taille maximale dans un environnement qui contient des
obstacles [CK89]. La partition élémentaire de Delaunay que nous avons définie correspond exactement à ce que Chew
et Kedem ont appelé la triangulation de Delaunay de segments.
5. CONCLUSIONS ET PERSPECTIVES
Nous avons généralisé la notion de triangulation et de triangulation de Delaunay à un ensemble de segments disjoints du
plan. Ces premiers résultats nous ont déjà permis de trouver un algorithme linéaire qui permet de déterminer si une
partition élémentaire quelconque a la même topologie que la partition élémentaire de Delaunay. Nous souhaitons
maintenant réaliser un algorithme dit « de flip » qui calcule la partition élémentaire de Delaunay de
S
à partir d'une
partition élémentaire quelconque de
S
par une suite de modifications locales. Par ailleurs il sera intéressant d'étendre
d’autres propriétés caractéristiques des triangulations de Delaunay de points, telles que l’équiangularité, aux partitions
élémentaires de Delaunay. Enfin il faudra étudier les possibilités d'extension de ces résultats à des ensembles de
segments non disjoints et à la dimension trois.
RÉFÉRENCES
[BE92]
M. Bern et D. Eppstein, “Mesh Generation and Optimal Triangulation” dans
Computing in Euclidean
Geometry
, édité par Ding-Zhu Du et Frank Hwang, World Scientific, Lecture Notes Series on Computing
Vol. 1, 1992.
[Ch89]
L. P. Chew,
Constrained Delaunay triangulations
, SCG '87: Proceedings of the third annual Symposium on
Computational Geometry, 1987.
[CK89]
L. P. Chew et K. Kedem,
Placing the Largest Similar Copy of a Convex Polygon Among Polygonal
Obstacles
, Symposium on Computational Geometry, 1989.
[Ed00]
H. Edelsbrunner,
Triangulations and meshes in computational geometry
, Acta Numerica (2000).
[La77]
C. L. Lawson,
Software for C
1
Surface Interpolation
, Mathematical Software, Vol.3, J.R. RICE Editor,
Academic Press, 1977.
[LL86]
D. T. Lee et A. K. Lin,
Generalized Delaunay Triangulation for Planar Graphs
, Discrete and Computational
Geometry 1:201-217 (1986).
