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 euclidien de dimension quelconque[1].

Il 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) en 1981[1],[2].

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]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bowyer–Watson algorithm » (voir la liste des auteurs).

  1. a et b (en) David F. Watson, « Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes », Comput. J., vol. 24, no 2,‎ , p. 167-172 (DOI 10.1093/comjnl/24.2.167).
  2. (en) Adrian Bowyer, « Computing Dirichlet tessellations », Comput. J., vol. 24, no 2,‎ , p. 162-166 (DOI 10.1093/comjnl/24.2.162).