Exemplo de cálculo da triangulação de Delaunay diretamente, usando a abordagem incremental randomizada.

Inicialmente iremos criar um triângulo largo que deverá conter o conjunto de pontos P. Iremos adicionar pontos extras p-1 e p-2 que, juntos com o ponto de mais alta coordenada y P0 de P, formarão o triângulo que irá conter todos os demais pontos.

Isto significa que nós iremos agora computar a triangulação Delaunay de P∪{p−1, p−2} ao invés da triangulação de Delaunay de P. Depois descartaremos p-1 e p-2 juntamente com todas as arestas incidentes para obter a triangulação Delaunay de P.

Para este trabalho, temos que escolher p-1 e p-2 o mais distantes possível, para que não destruam nenhum triângulo de Delaunay de P. Devemos garantir também que eles não caiam em nenhum círculo definido por três pontos em P.

O algoritmo é randomizado incremental, de modo que adiciona os pontos em ordem aleatória e mantém uma triangulação de Delaunay do conjunto de pontos atual. Considere a adição de um ponto pr.
Primeiro, encontre o triângulo da triangulação atual que contém pr e adicione arestas de pr para os vértices deste triângulo.
Se acontecer de pr cair em uma aresta e da triangulação, temos que adicionar arestas de pr para os vértices opostos nos triângulos que compartilham e. A figura a seguir ilustra estes dois casos.

Agora temos uma triangulação, mas não necessariamente uma triangulação Delaunay. Isto porque a adição de pr pode ter tornado ilegais algumas das arestas existentes. Para resolver este problema, chamamos o procedimento LegalizeEDGE para cada aresta potencialmente ilegal. Este programa transforma arestas ilegais em arestas legais pela rotação de arestas.

Algoritmo de Triangulação Delaunay para um conjunto de pontos P de n+1 pontos

Em seguida, discutiremos os detalhes de transformar a triangulação chegarmos após a linha 9 (ou
linha 14) em uma triangulação Delaunay.

Sabemos do Teorema 9.8 que a triangulação é uma triangulação de Delaunay, se todas as suas bordas são legais. No espírito do algoritmo LEGALTRIANGULATION, nós, portanto, iremos trocar as bordas ilegais até a triangulação ser legal novamente.

A questão que permanece é que as extremidades podem tornar-se ilegais, devido à inserção de pr. Observe-se que uma aresta do pi pj que era legal antes só se torna ilegal se um dos triângulos incidentes for alterado.

Assim, apenas as arestas dos novos triângulos precisam ser verificadas. Isto é feito usando a rotina LegalizeEDGE, que testa e possivelmente rotaciona uma borda.

Se LegalizeEDGE vira uma aresta, outras arestas podem se tornar ilegal. Portanto LegalizeEDGE chama a si mesmo de forma recursiva para todas as potenciais arestas ilegais.