Un
algorithme simple de découpage d’un polygone connexe par une polyligne
Considérons un polygone connexe et une polyligne.
Chacun des deux objets est défini par la liste ordonnée des points qui
constituent les sommets. Nous proposons dans le présent document un algorithme
simple permettant de découper le polygone à l’aide de la polyligne.
1. Cas particulier
Nous considérons ici le cas particulier (Figure 1) où :
1. le premier sommet
de la polyligne est situé sur la frontière du polygone,
2. le dernier sommet
de la polyligne est situé sur la frontière du polygone,
3. tous les sommets
intermédiaires présents entre le second sommet et l’avant-dernier sommet sont
situés strictement à l’intérieur du polygone.
Une polyligne vérifiant ces conditions
découpe le polygone en deux sous-polygones que nous pouvons calculer de la
manière suivante :
Considérons l’un après l’autre, dans
l’ordre, les côtés du polygone, afin d’identifier le premier côté du polygone
qui réalise une intersection avec le dernier sommet de la polyligne (qui se trouve, rappelons-le, sur la
frontière du polygone) (Figure 2). Le
dernier sommet de la polyligne peut d’ailleurs être confondu avec l’un ou
l’autre des deux sommets du côté identifié.
Figure 1
Figure 2
Nous allons stocker dans une liste L le
deuxième sommet du côté du polygone identifié qui entre en intersection avec le
dernier sommet de la polyligne.
Ensuite nous passons en
revue les côtés successifs du polygone, dans l'ordre, à partir du côté du
polygone que nous venons d'identifier. Si le côté courant du polygone ne réalise
aucune intersection avec le premier sommet de la polyligne, nous notons, dans
l’ordre, les deux sommets du côté courant du polygone dans la liste L. Si le côté courant du polygone réalise une
intersection avec le premier sommet de la polyligne, nous notons seulement le
premier sommet du côté courant du polygone dans la liste L (Figure 3).
Figure 3
Il suffit alors d’ajouter à la liste L la
liste ordonnée des sommets de la polyligne pour obtenir le premier des deux
polygones issus du découpage.
Le second polygone issu du découpage s’obtient simplement en lançant une
nouvelle fois l’opération après avoir inversé le sens de parcours des sommets
du polygone.
2. Algorithme général
2.1. Conditions de découpage du
polygone
Il convient de s’assurer en premier lieu
que la polyligne découpe le polygone, c'est-à-dire que la polyligne :
1. a son premier
sommet à l’extérieur (au sens large) du polygone
2. a son dernier
sommet à l’extérieur (au sens large) du polygone
3. réalise au moins
une intersection traversante avec le polygone, c'est-à-dire (dans notre cas)
possède au moins un sommet qui se trouve strictement à l’intérieur du polygone.
Si la polyligne vérifie ces conditions,
nous pouvons poursuivre.
2.2. Constitution de la liste des
sous-polylignes utiles
Nous allons examiner les sommets de la
polyligne à partir de son premier sommet S0 jusqu’à trouver le premier sommet Si
situé à l’intérieur (au sens strict) du polygone. Un tel sommet existe
nécessairement d’après la condition 3 énoncée précédemment et vérifiée par la
polyligne. Le point d’intersection X
(situé sur la frontière du polygone) associé à cette première intersection
traversante peut, ou non, être confondu avec le sommet précédant le sommet Si.
S’il ne l’est pas, il est ajouté à la liste des sommets, et devient le sommet
précédant le sommet Si.
Nous continuons alors à parcourir les
sommets qui suivent Si jusqu’à trouver le premier sommet Se qui se trouve à l’extérieur (au sens large)
du polygone. Un tel sommet existe nécessairement d’après la condition 2 énoncée
initialement et vérifiée par la polyligne. Soit Sj le sommet précédant Se . Le point
d’intersection Y associé à
l’intersection de la frontière du polygone avec le segment de droite Sj Se peut, ou non, être confondu avec
le sommet Se. S’il ne l’est pas, il est ajouté à la liste des sommets, et
devient le sommet précédant le sommet Se. La polyligne ∏1 défini par la
sous-liste des sommets allant du point X
au point Y est stockée dans une
liste de polygones Λ.
Nous continuons alors à passer en revue les
sommets de la polyligne à partir du sommet suivant Se, jusqu’à essayer
d’identifier un sommet Σi situé strictement à l’intérieur du
polygone. S’il n’en existe aucun, nous avons terminé. Sinon, il existera
nécessairement un sommet ultérieur Σe
situé à l’extérieur (au sens large) du polygone, grâce à la condition 2
précédemment énoncée et vérifiée par la polyligne. Comme précédemment, les
points d’intersection avec la frontière du polygone ξi et ξe attachés
à Σi et Σe
définissent une polyligne ∏2 intérieure au polygone que nous stockons dans la liste Λ avant de réitérer la procédure
jusqu’à épuisement des polylignes intérieures (Figure 4).
Figure 4
2.3. Calcul des polygones par
découpage
Nous considérons tour à tour chacun des
polylignes présents dans la liste Λ
.
La première polyligne de la liste Λ vérifie les conditions de l’algorithme décrit dans le cas particulier et découpera le polygone en deux
sous-polygones, qui définissent une liste de polygones Г.
Considérons maintenant la seconde polyligne
de la liste Λ ; nous
devrons nous assurer que cette polyligne vérifie les conditions de découpage de
polygone décrites en 2.1 pour chacun des polygones de la liste Г issus de
l’étape précédente. A chaque fois que ces conditions seront satisfaites,
l’algorithme général sera appliqué et le découpage par cette polyligne du
polygone courant de la liste Г donnera naissance à deux nouveaux
sous-polygones qui remplaceront le polygone courant dans la liste Г.
Le traitement se poursuivra avec la
polyligne qui suit dans la liste Λ.
Remarque :
l’algorithme général est susceptible de s’appeler lui-même récursivement. Au
bout d’un nombre fini d’opérations, l’algorithme particulier décrit en 1
s’appliquera toujours car le nombre de sommets de la polyligne initial est
fini.
Auteur
: Christophe Faivre Duboz
Date
: 14 avril 1998