L'algorithme employé

Dans ce nouveau mailleur, d'autres techniques de maillage automatique sont utilisées principalement pour des raisons de vitesse de calcul.

D'abords le maillage initial n'est pas construit en plongeant le tout dans un grand rectangle mais en gérant l'envelope convex C de l'ensemble des points donnés.

• Les points étant donnés dans un ordre quelconque, au départ C est un triangle formé des 3 premiers points.
• Pour chaque nouveau point on teste s'il est à l'interieur de C ou non. Ceci se fait triangle par triangle de C.
• S'il est à l'intérieur de C on divise le(s) triangle(s) en 3 (2 fois 2).
• Sinon on ajoute à C les triangles extérieurs obtenus en joignant ce nouveau point aux points du bords de C qui sont intérieur au nouveau convex obtenu avec ce nouveau point et C.

Pour calculer rapidement si un point est intérieur à un triangle on utilise la technique des Quadtrees.

Enfin pour forcer les arêtes du bords à être des arêtes du maillage et pouvoir ainsi retirer les triangles inutiles on utilise l'algorithme aléatoire de Bourouchaki:

• Faire une boucle sur les arêtes e du bords qui ne sont pas des arêtes du maillage.
• Pour chaque e, trouver l'ensemble des arêtes du maillage qui coupent e. (Partir d'une extémitée de e et utiliser les triangles ayant ce point pour sommet pour trouver la première arête, puis marcher en utilisant le triangle à gauche ou à droite de cette arête et ainsi de suite.)
• Pour chaque quadrilatère formé par les 2 triangles adjacents à une arête qui coupe e échanger aléatoirement de diagonale jusqu'a ce qu'aucune des ces arêtes ne coupent e.

L'algorithme converge nécessairement car l'aléatoire explore nécessairement toutes les configurations or on sait que les configurations viables existent.