Fechando um polígono arbitrário por triângulos de ladrilhos

Question

Preciso encher um polígono arbitrário usando um azulejo quase uniforme de triângulos. Como eu faria isso? Você pode fornecer referências a algoritmos existentes ou mesmo simplesmente idéias ou dicas próprias.

Presume -se o seguinte:

• O polígono pode ser convexo (mas pontos de bônus se você criar um algoritmo que funcione para formas côncavas)
• O polígono tem um número arbitrário de bordas (3 ou mais)
• A quantidade de tessellação (de preferência o número de vértices adicionados pelo algoritmo) deve ser parametrizado
• As bordas do polígono podem ser divididas pelo algoritmo
• Os triângulos devem ser quase uniformes em tamanho e forma (ou seja, os cantos tendem a 60 graus)
• De preferência, as bordas do número em um vértice devem ser poucas e não muitas. Isso provavelmente seguirá do ponto anterior (ou seja, o algoritmo deve produzir uma "malha limpa").

Este não é um problema fácil de resolver e espero que uma solução "heurística" possa ser a mais eficiente ... (certo?)

Answer 1

Como Jason Orendorff apontou, você deve tentar usar o Triangle para gerar uma malha de qualidade. Ele tem muitas opções com as quais você pode brincar para tentar obter uma malha isotrópica. Em seguida, você pode tentar usar um algoritmo iterativo para criar uma triangulação bem centrada. Mais detalhes estão listados em esta página de publicações. Eu implementei o artigo de 2007 "triangulação planar bem centrada-uma abordagem iterativa" e fornece resultados decentes em malhas de tamanho médio. Uma triangulação bem centrada é aquela em que todos os circuncentros dos triângulos ficam dentro do respectivo triângulo. Como você deseja algo um pouco diferente, você pode simplesmente tentar alterar a métrica de erro envolvida. Você pode encontrar uma medida de "não-convenção" entre os triângulos e minimizar esse erro. Provavelmente, essa função de erro será não-convexa; portanto, a otimização do gradiente conjugado não linear descrita é o melhor que você pode fazer.

Answer 2

Faz Triângulo faça o que você quiser?

(As explicações dos algoritmos nesse site são melhores do que o que eu poderia criar.)

Answer 3

Na verdade, não parece tão complicado, algoritmicamente. Ou estou perdendo alguma coisa?

Algum pseudocódigo:

• Coloque um quadrado fechado alinhado ao eixo firmemente ao redor do seu polígono.
• Subdividir cada quadrado em quatro crianças (quadrilátero), onde o número de iterações determina sua "quantidade de tesellation".
• Cada quadrado resultante está de maneira limpa fora do seu polígono (= ignorar), de forma limpa dentro do seu polígono (= dividido em dois triângulos de teselação resultante ao longo da diagonal) ou cruza seu polígono.
• Os casos exatos para os quadrados de interseção são deixados como um exercício para o leitor. ;-) [Neste momento, pelo menos.

Mas dará triângulos com ângulos de 45 °/45 °/90 °. Se você quiser o mais próximo possível de 60 °, comece com a superfície do seu polígono com hexágonos (com o tamanho do hexágono sendo sua "quantidade de teselação") e depois checando cada um dos seis 60 °/60 ° /60 ° triângulos que compõem esses hexágonos. Para esses triângulos, você faz o mesmo com os quadrados no pseudocódigo acima, exceto pelo fato de você não precisar dividir os que limpas dentro do seu polígono, pois já são triângulos.

Isso é de alguma ajuda? Deve funcionar para qualquer polígono (convexo/côncavo/com orifícios neles), eu acho, dado que exatamente você faz para que se cruzam quadrados/triângulos lida com esses polígonos.

Answer 4

Isso pode ser feito para polígonos côncavos/convexos usando um método simples de corte de ouvido (assumindo que não precisamos suportar orifícios).

• Tesselle o polígono
  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291
• Gire as bordas entre os triângulos, onde a área dividida pelo perímetro é menor quando a borda é girada para o novo estado.

São 2 etapas, portanto, pode ser mais eficiente recarregar iterativamente o ouvido 'melhor' para obter mais resultados uniformes, para que você não precise reorganizar a topologia como uma segunda passagem (YMMV).
(Observe que as razões de duas etapas são usadas aqui é que o cálculo de mais distribuição ainda nem sempre é necessário).

---

Divulgação completa, eu mesmo encontrei esse problema, quando precisava de um Tessellator rápido para polígonos para um aplicativo de modelagem em tempo real.

Implementação de trabalho escrita em c,
que pegam e devolvem os de pods (float[2] Array, preenchendo um uint[3] variedade):

• polyfill2d.c (Tessellatos)

• polyfill2d_beautify.c (ajusta a topologia para obter mais resultados uniformes)

• também fez um Porto de polyfill2d.c enferrujar

(Observe que o recorte de ouvido é baseado no libgdx com otimizações espaciais para as verificações de interseção, para escalar até milhares de lados sem um desempenho tão significativo, já que o corte de todos os ouvidos estava verificando todos os outros pontos cada vez).