Estou implementando o algoritmo Bowyer-Watson, conforme apresentado emWikipedia. Na minha implementação, tudo funciona como eu esperaria até a última parte do pseudocódigo:

for each triangle in triangulation // done inserting points, now clean up
     if triangle contains a vertex from original super-triangle
        remove triangle from triangulation

Se eu seguir o pseudocódigo aqui literalmente, posso terminar com triângulos ausentes na minha triangulação em Delaunay.

Como exemplo, considere as imagens abaixo. Os sites que estou triangulando são renderizados em círculos azuis. Os triângulos são renderizados com linhas pretas (excluindo as bordas da imagem) e conectam sites ou vértices delimitadores / super triângulo. Os circuitos são renderizados em cinza e seus centros são renderizados em círculos vermelhos. As células Voronoi são pintadas com uma cor diferente para (espero) tornar o problema mais aparente.

Esta imagem mostra o estado da triangulação antes de executar as etapas listadas no pseudocódigo acima. Observe que dois dos vértices do super triângulo estão além da direita e da parte inferior da imagem.

Esta imagem mostra a etapa após remover quaisquer triângulos que contenham vértices de super triângulo sem nenhuma consideração adicional:

Os três vértices superiores devem ter um novo triângulo com um circuncentro no ponto em que as células esverdeadas / acastanhadas se encontram. O problema é que o vértice do canto que foi mostrado na imagem "antes" estava dentro desse circulo, portanto o processamento regular do algoritmo nunca gerou esse triângulo.

Como expresso esse caso de borda em pseudocódigo para que eu possa verificar e resolvê-lo? Eu gostaria de evitar um loop horrível "tente todas as combinações de sites que compartilham um triângulo com um super vértice do triângulo para circuncisão válida".

Li os jornais de Bowyer e Watson há alguns anos e os lerei novamente para minha resposta, se necessário. Eu esperava que (1) outra pessoa pudesse ter a resposta disponível e (2) eu poderia usar o Stack Overflow para procurar a resposta, se eu me deparar com essa pergunta novamente.

Editar

Então, eu encontrei uma solução alternativa relativamente barata, mas imperfeita. Meu super triângulo é programaticamente determinado a cercar a caixa delimitadora dos sites sem cruzar os lados. Essa ideia foi causada por todos os tipos de problemas frustrantes com Java, considerando que algumas das minhas coordenadas calculadas do circuncentro ou distâncias entre coordenadas eram infinitas. Essa cautela me levou a tornar meu super triângulo tão pequeno que seus vértices às vezes caíam em circunferência de triângulos válidos. Aumentar o tamanho do super triângulo fez o problema parecer desaparecer. No entanto, é possível que um triângulo no casco convexo possa ser tão obtuso que um dos vértices ainda possa cair dentro de um circulo-círculo válido.

Acho que isso significa que minha pergunta inicial ainda é válida diante das limitações de número de ponto flutuante. Existe uma maneira barata de garantir que o algoritmo de Bowyer-Watson gere uma triangulação válida?