On maintient à jour une liste de triangle qui à tout instant forme une triangulation du rectangle. Celle-ci est formée au départ des 2 triangles obtenus en divisant le rectangle par une de ses diagonales.
On prend les points un par un dans l'ordre de leur numéro. Deux cas possibles:
Ou bien le nouveau point est interne à l'un des triangles Tk de la liste ou bien il est sur la frontière de 2 triangles Ti,Tj de la liste.
Dans le premier cas, retirer Tk de la liste et rajouter à la liste les 3 triangles obtenus en divisant Tk par les droites joignant le point au 3 sommets de Tk.
Dans le deuxième cas retirer Ti et Tj de la liste et rajouter les 4 triangles obtenus en divisant Ti par le nouveau point et le sommet opposé et de même pour Tj.