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 peut être utilisé pour obtenir un diagramme de Voronoi des points, qui est le graphe dual de la triangulation de Delaunay.

L'algorithme de Bowyer-Watson est un algorithme incrémentiel. Il marche 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 contient le nouveau point sont détruits, laissant un trou polygonal étoilé qui est alors re-triangulé en utilisant le nouveau point.

L'algorithme est parfois appelé algorithme de Bowyer ou algorithme de Watson. Adrian Bowyer et David Watson y ont réfléchi indépendamment l'un de l'autre et ont publié leur algorithme dans le même journal The Computer Journal (en).

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