Algorithme de Greiner-Hormann
L’algorithme de Greiner-Hormann est utilisé en infographie pour découper des polygones[1]. Il est plus performant que l’algorithme de Vatti, mais ne peut pas gérer d’éventuels cas dégénérés[2]. Il peut cependant être utilisé avec des polygones s’auto-intersectant et n'étant pas convexes. Il peut facilement être généralisé afin d’effectuer d’autres opérations booléennes sur les polygones, telles que l’union et la différence.
Description[modifier | modifier le code]
L’algorithme est basé sur la définition d’« intérieur » d’un polygone, elle-même basée sur la notion d’indice. Il considère les régions d’indice pair comme étant à l’intérieur du polygone : ceci est également connu sous le nom de règle du pair-impair. L’algorithme prend deux listes de polygones en entrée, chaque polygone étant lui-même représenté comme une liste de sommets reliés.
Dans sa formulation initiale, l’algorithme est divisé en trois phases :
- Dans la première phase, les intersections entre les côtés des polygones sont calculées. Des sommets sont rajoutés aux points d’intersection, et chacun est muni d’un pointeur vers son homologue situé dans l’autre polygone.
- Dans la deuxième phase, chaque intersection est marquée comme étant soit une intersection d’entrée, soit une intersection de sortie. Cette décision est prise en appliquant la règle du pair-impair au premier sommet, puis en traversant le polygone en alternant le marquage (à une intersection d’entrée doit suivre une intersection de sortie).
- Dans la troisième et dernière phase, le résultat est généré. L’algorithme démarre d’une intersection non traitée et choisit la direction du parcours du polygone, en fonction du marquage entrée/sortie : pour une intersection d’entrée, il le traverse vers l’avant, et pour une intersection de sortie, il traverse dans le sens inverse. Les sommets sont ajoutés au résultat jusqu’à ce qu’une autre intersection soit trouvée ; l’algorithme va alors regarder l’intersection correspondante dans l’autre polygone et va de nouveau choisir une direction de parcours, en suivant la même règle. Si l’intersection suivante a déjà été traitée, l’algorithme s’arrête pour cette partie de la sortie, et recommence pour les intersections non traitées. La sortie est entièrement déterminée lorsqu’il ne reste plus d’intersections non traitées.
L’algorithme n’est pas limité aux polygones, et peut aussi bien traiter des segments que des courbes paramétriques.
Un des inconvénients majeurs de l’algorithme original est le fait qu’il ne prenne pas en charge les cas dégénérés, tels que les doublons de sommets ou les auto-intersections ne s’effectuant que sur un sommet. La publication originale suggère de modifier certains sommets pour retirer les dégénérescences.
Références[modifier | modifier le code]
- Greiner, Günther; Kai Hormann (1998).
- Ionel Daniel Stroe.
Voir aussi[modifier | modifier le code]
Articles connexes[modifier | modifier le code]
- Algorithme de Vatti (en)
- Algorithme de Sutherland-Hodgman
- Algorithme de Weiler–Atherton
- Opérations booléennes sur les polygones
Liens externes[modifier | modifier le code]
- Geographic Clipping Describes the clipping algorithms in D3.js.
- https://github.com/helderco/univ-polyclip An implementation in Python and Java.
