Una estructura de datos de cuatro aristas es una representación informática de la topología de un mapa bidimensional o tridimensional , es decir, un gráfico dibujado sobre una superficie (cerrada) . Fue descrita por primera vez por Jorge Stolfi y Leonidas J. Guibas . [1] Es una variante de la estructura de datos de aristas aladas anterior .
La idea fundamental detrás de la estructura de cuatro bordes es el reconocimiento de que un solo borde, en una topología de malla poligonal cerrada, se encuentra entre exactamente dos caras y exactamente dos vértices.
La estructura de datos de aristas cuádruples representa una arista, junto con las aristas a las que está conectada alrededor de los vértices y caras adyacentes para codificar la topología del gráfico. A continuación se muestra un ejemplo de implementación del tipo de datos de aristas cuádruples
tipodef estructura { quadedge_ref e [ 4 ]; } quadedge ; typedef struct { quadedge * next ; int sin signo rot ; } quadedge_ref ; Cada arista cuádruple contiene cuatro referencias a aristas cuádruples adyacentes. Cada una de las cuatro referencias apunta a la siguiente arista en sentido antihorario alrededor de un vértice o una cara. Cada una de estas referencias representa el vértice de origen de la arista, la cara derecha, el vértice de destino o la cara izquierda. Cada referencia de arista cuádruple apunta a una arista cuádruple y a la rotación (de 0 a 3) del "brazo" al que apunta.
Debido a esta representación, el borde cuádruple:
La estructura de cuatro aristas recibe su nombre del mecanismo general por el que se almacenan. Una estructura de una sola arista almacena conceptualmente referencias a hasta dos caras, dos vértices y 4 aristas. Las cuatro aristas almacenadas son las aristas que comienzan con los dos vértices que están unidos a las dos caras almacenadas.
Al igual que Winged Edge , las estructuras de cuatro aristas se utilizan en programas para almacenar la topología de una malla poligonal 2D o 3D . No es necesario cerrar la malla en sí para formar una estructura de cuatro aristas válida.
Si se utiliza una estructura de cuatro aristas, es bastante fácil iterar a través de la topología. A menudo, la interfaz con las topologías de cuatro aristas se realiza a través de aristas dirigidas. Esto permite que los dos vértices tengan nombres explícitos (inicio y fin), y también da nombres explícitos a las caras (izquierda y derecha, en relación con una persona parada en el inicio y mirando en la dirección del fin). Las cuatro aristas también reciben nombres, en función de los vértices y las caras: inicio-izquierda, inicio-derecha, fin-izquierda y fin-derecha. Una arista dirigida se puede invertir para generar la arista en la dirección opuesta.
Iterar alrededor de una cara particular solo requiere tener un único borde dirigido al cual esa cara está a la izquierda (por convención) y luego caminar a través de todos los bordes iniciales izquierdos hasta que se alcanza el borde original.