Algorithme de Bowyer-Watson

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En géométrie algorithmique, l'algorithme de Bowyer-Watson est une méthode pour calculer la triangulation de Delaunay d'un ensemble fini de points dans un espace de dimension quelconque.

L'algorithme est parfois appelé algorithme de Bowyer ou algorithme de Watson, Adrian Bowyer et David Watson l'ayant indépendamment découvert et publié dans le même numéro du Computer Journal en 1981.

Description[modifier | modifier le code]

L'algorithme de Bowyer-Watson est un algorithme itératif. Il procède en ajoutant des points, un à la fois, à une triangulation de Delaunay valide du sous-ensemble des points. Après chaque insertion, tous les triangles dont le cercle circonscrit (en jaunes dans les figures ci-dessus) contient le nouveau point sont supprimés, laissant un trou polygonal « étoilé » (en rouge) qui est alors re-triangulé (en vert) en utilisant le point suivant.


Pseudo-code[modifier | modifier le code]

def delaunay_bowyer_watson( points ):
    supertri = supertriangle(points) # Un triangle contenant tous les points à trianguler.
    # Qui devient le premier triangle de la triangulation.
    triangles = [ supertri ]
    fait = { supertri: False }
    for sommet in points:
        # Tous les triangles dont le cercle circonscrit contient le sommet à ajouter sont identifiés,
        # l'ensemble de leurs arêtes forment un polygone englobant.
 
        # Démarrer avec un polygone englobant vide.
        englobant = []
        # Pour l'instant, il n'y a aucun triangle subdivisé y supprimer.
        à_supprimer = []
        for triangle in triangles:
            centre,rayon = cercle_circonscrit( triangle )
            # Si ce triangle respecte la condition de Delaunay.
            if x(centre) < x(sommet) and sqrt((x(sommet)-x(centre))**2) > radius:
                fait[triangle] = True # Le marquer comme traité.
            # Si le sommet courant est dans le cercle circonscrit du triangle courant,
            if dans_cercle( sommet, centre, rayon ):
                # ajouter les arêtes de ce triangle au polygone candidat,
                englobant += aretes( triangle )
                # préparer la suppression de ce triangle.
                à_supprimer += [ triangle ]
                fait.pop( triangle )
        # Effectue la suppression des triangles marqués précédemment.
        for triangle in à_supprimer:
             triangles.remove( triangle )
        # Créer de nouveaux triangles, en utilisant le sommet courant et le polygone englobant.
        for arête in englobant:
            point_A, point_B = arête
            # Ajoute un nouveau triangle à la triangulation.
            triangle = [ point_A, point_B, sommet ]
            triangles += [ triangle ]
            # Il faudra le considérer au prochain ajout de point.
            fait[triangle] = False
        # Supprime les triangles ayant au moins une arête en commun avec le super-triangle.
        triangulation = non_supertriangle( triangles )
    return triangulation


Voir aussi[modifier | modifier le code]

Cet algorithme peut être utilisé pour obtenir un diagramme de Voronoi des points, qui est le graphe dual de la triangulation de Delaunay.


Références[modifier | modifier le code]