Algoritmo para criar triângulos adjacentes

14

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)

Exemplo de comportamento real e desejado

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:

insira a descrição da imagem aqui

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.)

Kylotan
fonte
Não é bom o suficiente olhar para os últimos 5 vértices colocados e selecionar os dois mais próximos do vértice recém-colocado? Eu apontaria os algoritmos para tiras de triângulo ( codercorner.com/Strips.htm ), mas esses geralmente usam apenas os dois últimos ou os três últimos pulando um.
Roy T.
1
O triângulo verde se sobrepõe ao magenta? Qual é o objetivo disso? O usuário precisa controlar onde e como os triângulos são criados ou a triangulação de uma nuvem de pontos seria aceitável?
bummzack
Para colocar isso em um contexto gráfico, basicamente você deseja conectar seus nós, sem nenhuma sobreposição de arestas? (Supondo que os triângulos magenta / verde compartilhem uma aresta)
Michaelhouse
Roy T: não - apenas escolher os 2 mais próximos está errado, como eu pensei que o exemplo mostra. Algo não está claro? Bummzack - O verde não se sobrepõe ao magenta. O objetivo é fazer uma malha ou gráfico desses triângulos. O usuário precisa de controle, sim. Byte56 - sim, nenhuma aresta deve cruzar-se.
Kylotan
2
O usuário verá realmente os triângulos individuais? Ou será uma superfície contínua?
bummzack

Respostas:

11

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).

Jeff Gates
fonte
3
+1 - esta é uma resposta muito mais direta ao IMHO do que as outras e com maior probabilidade de fornecer os resultados corretos. Também é fácil calcular a distância ao segmento com um esquema inteligente.
Steven Stadnicki
Concordado, este é um método mais limpo. Provavelmente o que eu teria chegado se tivesse pensado mais sobre isso: /
MichaelHouse
Ah, tão perto! Mas, como na resposta de Byte56 e no diagrama de Jimmy, às vezes existem duas arestas equidistantes, e uma delas viola as restrições. Eu atualizei minha pergunta.
Kylotan
@Kylotan Talvez nesse caso, simplesmente verificar qual se sobrepõe e escolher a outra opção faria? Procure triângulos compartilhando a aresta que você escolheu e verifique se seu novo triângulo está do mesmo lado dessa aresta que o existente.
22612 Kevin Reid
@Kylotan Você garante que seus triângulos sempre tenham o mesmo enrolamento? Se sim, você pode descartar a aresta que tem um apontamento normal para longe do seu novo vértice (usando produtos pontuais).
bummzack
6

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).

insira a descrição da imagem aqui

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:

triângulo ambíguo

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.

insira a descrição da imagem aqui

MichaelHouse
fonte
É possível ter uma situação em que duas das linhas não se intersectam com as bordas (quando X está mais perto de um vértice que é a borda)
Jimmy
@ Jimmy, você pode desenhar uma imagem dessa situação?
MichaelHouse
Ah sim, então você tem duas opções de onde colocar o triângulo! Qualquer um dos lados funcionaria. Talvez você possa empatar com o que tiver a menor distância do centro.
MichaelHouse
@Kylotan, esta solução não funciona? Você mencionou em um comentário a Jeff que a imagem de Jimmy tem dois casos e um viola as restrições, mas isso não é verdade. Na imagem de Jimmy, os dois casos produziriam triângulos válidos usando meu método.
MichaelHouse
1

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.

Dan
fonte
Isso parece bom, mas da maneira que você afirmou, parece assumir que existe apenas um triângulo existente. Como isso generalizaria para muitos?
Kylotan
Hum ... se seu X e seu triângulo ABC são fixos, acho que só existe um, não é?
Dan
O sistema cria um novo triângulo para cada nó após o segundo.
Kylotan
Desculpe, eu não entendi sua pergunta. Deixe-me ver como posso estender isso para muitos triângulos.
Dan
Bem, acho que você poderia procurar os dois vértices mais próximos de X que não cruzam nenhuma borda quando conectados a X?
bummzack
1

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.

Regiões Voronoi de um 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.)

John Calsbeek
fonte
Não está imediatamente claro para mim como isso se generaliza em vários triângulos na cena - especialmente se o recurso mais próximo for um vértice que pode ser compartilhado por mais de um triângulo.
Kylotan
@Kylotan Basta executar o algoritmo para todos os triângulos e escolher o recurso geral mais próximo. Você precisa de alguma lógica de desempate, não importa o quê. Se você acabar com o recurso mais próximo como um vértice compartilhado, deverá estar na região da aresta (# 1, # 2, # 3) para apenas um triângulo, então talvez você possa escolher isso?
31912 John Calsbeek