Algoritmo para criar triângulos adjacentes

Eu tenho um sistema onde você pode clicar uma vez para colocar um nó em uma cena. Quando você coloca 3 nós, ele forma um triângulo. Quando você coloca quaisquer nós futuros, ele cria um novo triângulo unindo esse nó aos 2 nós existentes mais próximos.

Isso funciona bem na maioria das vezes, mas apresenta falhas quando usado perto de triângulos com ângulos muito agudos, porque um dos 2 nós mais próximos geralmente não é aquele que deve ser usado.

Por exemplo, veja a imagem abaixo. O triângulo magenta é o primeiro colocado. Se eu clicar na posição marcada X, o que recebo é um novo triângulo onde está a sobreposição azul. O que eu quero é um novo triângulo onde está a sobreposição verde. (isto é, simétrico ao magenta, neste exemplo. Esclarecimento: Os triângulos verde e magenta não se sobrepõem - o verde se estende sob o azul ao nó mais à esquerda)

Como posso determinar quais 2 vértices existentes usar ao criar novos triângulos para que os triângulos não sejam sobrepostos dessa maneira?

EDIT : A busca pela borda mais próxima fornece melhores resultados, mas não os perfeitos. Considere esta situação:

O teste da 'aresta mais próxima' é ambíguo e pode retornar AB ou AC (como o ponto mais próximo de X para ambos é em A). O resultado desejado seria AC, para formar o triângulo ACX, sem arestas sobrepostas. Como eu poderia garantir esse resultado? (Prefiro não ter que executar testes individuais de sobreposição de arestas como desempatador, se possível, pois estou preocupado que o teste de aresta mais próximo não necessariamente identifique os 2 como exatamente equidistantes, dados problemas de precisão de ponto flutuante.)

Em vez de encontrar a distância mínima para os nós, encontre a distância mínima para a aresta (ou seja, o segmento de linha definido pelos nós).

Então, se o ponto mais próximo for um vértice (que você precisará usar algum teste epsilon de ponto flutuante **), compare o ângulo entre a linha do novo ponto ao vértice e cada uma das arestas conectadas a esse vértice. Escolha aquele com o ângulo absoluto mínimo:

MinAngle(newPoint, vertex, edge1, edge2)
{
   newEdgeUnit = norm(newPoint - vertex); // don't actually need to normalize this
   edge1Unit = norm(edge1 - vertex);      // you probably have these from your dist to line tests
   edge2Unit = norm(edge2 - vertex);

   edge1Dot = dot(edge1Unit, newEdgeUnit);
   edge2Dot = dot(edge2Unit, newEdgeUnit);

   // you can simply compare dot products to find the minimum absolute angle
   if (edge1Dot > edge2Dot) return edge1;     // set up this way so you can generalize to an array
   return edge2;
}

** Para evitar a adição de triângulos degenerados, o que pode atrapalhar o teste epsilon, você pode colocar uma região em torno de cada vértice em que a adição de pontos não é permitida (algo como pontos proibidos em alguns múltiplos do epsilon usado acima).

Após o primeiro triângulo ser colocado, ao colocar um novo vértice, você sempre gerará duas novas arestas. A terceira aresta do novo triângulo sempre será uma aresta compartilhada com um triângulo anterior. Se você pudesse encontrar uma maneira de determinar a borda compartilhada, saberia a quais vértices se conectar, mas essa é a parte mais difícil. Acredito que de uma maneira você possa fazer isso desenhando uma linha do seu novo vértice até o centro de cada uma das três últimas arestas geradas (ou provavelmente as três arestas mais próximas).

Se a linha do seu vértice até o centro da aresta não cruzar nenhuma das outras duas arestas, você terá sua aresta compartilhada. A borda compartilhada informará em quais dois vértices você deve conectar seu novo vértice.

Jimmy levantou o argumento de um ponto ambíguo a respeito de onde o novo triângulo seria assim:

Isso daria a você a oportunidade de escolher entre dois triângulos válidos. Talvez o empate seja o ponto central mais próximo.

Considerando sua atualização, embora mais complexa, minha solução só resultará em empate quando você tiver dois triângulos válidos. Usando esse método, sua segunda imagem de exemplo produziria o resultado desejado.

Tendo seu triângulo magenta ABC, você incorpora um novo vértice X. Acho óbvio que haverá duas linhas começando em D que não se cruzarão entre nenhuma das arestas do triângulo ABC.

Essas duas linhas podem ser AX e BX, BX e CX ou AX e CX. Você pode então tratar seu problema como o problema clássico de "duas linhas se cruzam"? Você pode então verificar qual desses pares de linhas não cruza com nenhuma das arestas do triângulo ABC, seguindo, por exemplo, qualquer um dos métodos desta pergunta . Portanto, você terá as duas novas arestas do novo triângulo.

Descobrir se você está em uma das regiões inequívocas (1, 2, 3 abaixo) é bastante fácil: trate cada extremidade do seu triângulo como um plano 2D e teste em que lado do plano está o seu novo ponto. Se você estiver dentro de dois deles, mas fora de um, ele corresponderá à aresta do triângulo que contribui com dois vértices para o seu novo triângulo.

Se você estiver dentro de um e fora de dois, estará no caso ambíguo em que a parte mais próxima do triângulo ao seu novo ponto é um canto. Nesse caso, você pode formar um plano 2D a partir do ponto médio da aresta oposta (a que você está dentro) e o vértice mais próximo (aquele compartilhado pelos dois planos dos quais você está fora). Você pode escolher uma aresta, dependendo do lado deste plano em que está o seu novo ponto.

Observe que um teste de plano em 2D funciona da mesma maneira que em 3D: coloque um vetor de qualquer lugar no plano para o seu ponto com o normal do plano (em 2D, essa é a perpendicular da linha).

(Aliás, as regiões delimitadas por magenta nesta imagem são chamadas regiões de Voronoi; são as áreas do espaço que contêm pontos mais próximos de uma característica específica - aresta ou vértice - do triângulo. Edit: Minha terminologia aqui não é realmente bastante correto, essas não são exatamente as regiões de Voronoi.)