borde alado

En gráficos por computadora , la estructura de datos de borde alado es una forma de representar mallas poligonales en la memoria de la computadora . Es un tipo de representación de límites y describe tanto la geometría como la topología de un modelo. Se utilizan tres tipos de registros: registros de vértices, registros de bordes y registros de caras. Dada una referencia a un registro de borde, se pueden responder varios tipos de consultas de adyacencia (consultas sobre bordes, vértices y caras vecinos) en tiempo constante . Este tipo de información de adyacencia es útil para algoritmos como la subdivisión de superficies . ^{[ 1 ]}

La estructura de datos de aristas aladas describe explícitamente la geometría y la topología de caras, aristas y vértices cuando tres o más superficies se unen y convergen en una arista común. El ordenamiento es tal que las superficies se ordenan en sentido antihorario con respecto a la orientación intrínseca de la arista de intersección. Además, esta representación permite situaciones numéricamente inestables como la que se muestra a continuación.

La estructura de datos de aristas aladas permite un recorrido rápido entre caras, aristas y vértices gracias a la estructura de red explícitamente vinculada. Realiza consultas de adyacencia en tiempo constante con un mínimo consumo de almacenamiento. Esta rica forma de especificar una cuadrícula no estructurada contrasta con las especificaciones más simples de mallas poligonales, como una lista de nodos y elementos, o la conectividad implícita de una cuadrícula regular . Una alternativa a la estructura de datos de aristas aladas es la estructura de datos de media arista .

Los registros de caras y vértices son relativamente sencillos, mientras que el registro de aristas es más complejo.

• Para cada vértice, su registro almacena únicamente la posición del vértice (por ejemplo, coordenadas) y una referencia a una arista incidente. Las demás aristas se pueden encontrar siguiendo las referencias adicionales en la arista.
• De forma similar, cada registro de cara solo almacena una referencia a una de las aristas que la rodean. No es necesario almacenar la dirección de la arista con respecto a la cara (en sentido antihorario o horario), ya que esta información se puede obtener fácilmente comparándola con las caras izquierda y derecha de la propia arista.
• Finalmente, la estructura del registro de aristas es la siguiente. Se asume que una arista es dirigida. El registro de aristas contiene dos referencias a los vértices que conforman los extremos de la arista, dos referencias a las caras a cada lado de la arista y cuatro referencias a las aristas anterior y siguiente que rodean las caras izquierda y derecha.

En resumen, el registro de arista tiene referencias a todos sus registros adyacentes, tanto al recorrer un vértice adyacente como al recorrer una cara adyacente.

Clase Edge { Vértice *vert_origin, *vert_destination; Cara *cara_izquierda, *cara_derecha; Borde *borde_izquierdo_cw, *borde_izquierdo_ccw, *borde_derecho_cw, *borde_derecho_en_dirección_justa; } clase Vértice { x, y, z flotantes; Borde *borde; } Cara de clase { Borde *borde; }

• Estructura de datos de cuatro aristas
• Mapas combinatorios
• Lista de aristas doblemente conectadas
• Lista de rostros doblemente vinculados
• Estructura de datos de media arista