O que são polígonos degenerados?

O que são polígonos degenerados? Como se verifica se um determinado par de polígonos é degenerado ou não?

Um polígono é degenerado se alguns de seus vértices se encontrarem. por exemplo, o triângulo (0,0), (0,1), (0,0) é degenerado. Tem 3 lados e 3 vértices, mas dois deles se repetem. É possível repetir um vértice várias vezes (por exemplo (0,0), (0,0), (0,0) é outro triângulo degenerado). Por definição, verificar se um polígono é degenerado ou não é fácil.

Mas quais são os usos dos polígonos degenerados? Uma aplicação da aceleração gráfica (desenho 3D) é a seguinte:

No desenho 3D, as GPUs normalmente usam triangulação para renderizar imagens. A razão (simples) para o uso de triângulos é porque eles são objetos 2D possíveis mais simples, portanto não precisam de muito hardware.

Se queremos desenhar uma imagem 3D complexa, por essa limitação da GPU, temos que decompô-la em vários triângulos. Mas se chamarmos a GPU para renderizar cada triângulo separadamente, seria muito lento (devido ao número de chamadas). Portanto, a faixa triangular é usada para reduzir o número de chamadas para a GPU. Uma boa explicação sobre as tiras triangulares pode ser encontrada em Documentação da Microsoft: Tiras triangulares , também você pode ver o wiki de: Tira triangular .

Mas o problema surge quando queremos desenhar dois objetos separados em uma faixa. Neste caso, triângulos degenerados ajudam. A GPU pode detectar os triângulos degenerados e pular seus desenhos. Assim, podemos conectar duas tiras separadas com um triângulo degenerado.

$n$

Um polígono degenerado é aquele que tem área zero.

Como outros observaram, isso depende. De um modo geral, um polígono não é degenerado se não tiver pontos anômalos, mas isso apenas leva o problema de volta um passo; o que é "anômalo"?

A resposta real é que um polígono é degenerado se violar a especificação. A resposta um pouco grosseira é que um polígono é degenerado se for um caso de borda que seu algoritmo não pode lidar.

Aqui está um exemplo do mundo dos SIG. A especificação de recursos simples do OGC possui uma definição muito cuidadosa do que torna um polígono "válido". Citando a Seção 6.1.11.1:

As asserções para polígonos (as regras que definem polígonos válidos) são as seguintes:

a) Os polígonos são topologicamente fechados;

b) O limite de um polígono consiste em um conjunto de anéis lineares que compõem seus limites exterior e interior;

c) Não há dois anéis na cruz de limite e os anéis no limite de um polígono podem cruzar-se em um ponto, mas apenas como uma tangente, por exemplo

$$\begin{align*} & \forall P \in \hbox{Polygon}, \forall c_1, c_2 \in \hbox{P.Boundary}, c_1 \ne c_2,\\ & \forall p, q \in \hbox{Point},\,p,q \in c_1, p \ne q,\\ & \left[ p \in c_2 \right] \Rightarrow \left[ \exists \delta > 0 | \left[\left|p-q\right|<\delta\right]\ \Rightarrow \left[ q \not\in c_2 \right] \right] \end{align*}$$

Nota: Esta última condição diz que, em um ponto comum às duas curvas, os pontos próximos não podem ser comuns. Isso força cada ponto comum a ser um ponto de tangência.

$\forall P \in \hbox{Polygon}, P = \hbox{P.Interior.Closure}$

e) O interior de cada polígono é um conjunto de pontos conectados;

f) O exterior de um polígono com 1 ou mais orifícios não está conectado. Cada furo define um componente conectado do exterior.

Nas afirmações acima, interior, fechamento e exterior têm as definições topológicas padrão. A combinação de (a) e (c) faz de um polígono um conjunto regular de pontos fechado.