¿Qué son los polígonos degenerados?

¿Qué son los polígonos degenerados? ¿Cómo se comprueba si un par de polígonos dado está degenerado o no?

Un polígono se degenera si algunos de sus vértices se encuentran entre sí. por ejemplo, el triángulo (0,0), (0,1), (0,0) está degenerado. Tiene 3 lados y 3 vértices, pero dos de los vértices se repiten. Es posible repetir un vértice varias veces (por ejemplo (0,0), (0,0), (0,0) es otro triángulo degenerado). Por definición, verificar si un polígono está degenerado o no es fácil.

¿Pero cuáles son los usos de los polígonos degenerados? Una aplicación de la aceleración gráfica (dibujo 3D) es la siguiente:

En el dibujo 3D, las GPU normalmente usan triangulación para renderizar imágenes. La razón (simple) para usar triángulos es porque son los objetos 2D más simples posibles, por lo que no necesitan mucho hardware.

Si queremos dibujar una imagen 3D compleja, por esta limitación de GPU, tenemos que descomponerla en múltiples triángulos. Pero si llamamos a la GPU para representar cada triángulo por separado, sería muy lento (debido a la cantidad de llamadas). Entonces, la tira triangular se usa para reducir la cantidad de llamadas a la GPU. Puede encontrar una buena explicación de las tiras triangulares en la documentación de Microsoft: Tiras triangulares , también puede ver la wiki de: Tiras triangulares .

Pero el problema surge cuando queremos dibujar dos objetos separados en una tira. En este caso, los triángulos degenerados ayudan. La GPU puede detectar los triángulos degenerados y omitir su dibujo. Entonces podemos conectar dos tiras separadas con un triángulo degenerado.

En general, si tenemos componentes diferentes, de modo que ya tenemos sus correspondientes tiras triangulares, podemos dibujarlos todos con solo una llamada a la GPU. Esto causa un uso adicional de memoria, pero es una compensación entre el número de llamadas a la GPU para renderizar y la sobrecarga de usar un triángulo degenerado adicional.$n$

Un polígono degenerado es uno que tiene área cero.

Como otros han notado, depende. En términos generales, un polígono no está degenerado si no tiene puntos anómalos, pero esto solo hace retroceder el problema un paso; ¿Qué es "anómalo"?

La respuesta real es que un polígono se degenera si viola la especificación. La respuesta ligeramente grosera es que un polígono se degenera si es un caso límite que su algoritmo no puede manejar.

Aquí hay un ejemplo del mundo de los SIG. La especificación de características simples de OGC tiene una definición muy cuidadosa de lo que hace que un polígono sea "válido". Citando de la Sección 6.1.11.1:

Las afirmaciones para los polígonos (las reglas que definen los polígonos válidos) son las siguientes:

a) Los polígonos están topológicamente cerrados;

b) El límite de un polígono consiste en un conjunto de anillos lineales que conforman sus límites exteriores e interiores;

c) No hay dos anillos en la cruz del límite y los anillos en el límite de un polígono pueden cruzarse en un punto, pero solo como una tangente, por ejemplo, ;

$$\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 condición dice que en un punto común a las dos curvas, los puntos cercanos no pueden ser comunes. Esto obliga a cada punto común a ser un punto de tangencia.

d) Un polígono puede no tener líneas de corte, puntas o perforaciones, por ejemplo: ;$\forall P \in \hbox{Polygon}, P = \hbox{P.Interior.Closure}$

e) El interior de cada Polígono es un conjunto de puntos conectados;

f) El exterior de un polígono con 1 o más agujeros no está conectado. Cada hoyo define un componente conectado del exterior.

En las afirmaciones anteriores, interior, cierre y exterior tienen las definiciones topológicas estándar. La combinación de (a) y (c) hace que un polígono sea un conjunto de puntos cerrados regular.