Lista de aristas doblemente conectadas

La lista de aristas doblemente conectadas ( DCEL ), también conocida como estructura de datos de media arista , es una estructura de datos que representa la incrustación de un grafo planar en el plano y politopos en 3D . Esta estructura de datos permite una manipulación eficiente de la información topológica asociada a los objetos en cuestión (vértices, aristas, caras). Se utiliza en numerosos algoritmos de geometría computacional para manejar subdivisiones poligonales del plano, comúnmente denominadas grafos planares de líneas rectas (PSLG). Por ejemplo, un diagrama de Voronoi se representa habitualmente mediante una DCEL dentro de un cuadro delimitador.

Esta estructura de datos fue propuesta originalmente por Muller y Preparata ^{[ 1 ]} para representaciones de poliedros convexos 3D . Las versiones simplificadas de la estructura de datos, como se describe aquí, solo consideran grafos conectados , pero la estructura DCEL puede extenderse para manejar también grafos desconectados mediante la introducción de aristas ficticias entre componentes desconectados. ^{[ 2 ]}

DCEL es más que una simple lista doblemente enlazada de aristas. En general, una DCEL contiene un registro para cada arista, vértice y cara de la subdivisión. Cada registro puede contener información adicional; por ejemplo, una cara puede contener el nombre del área. Cada arista suele delimitar dos caras, por lo que resulta conveniente considerarla como dos "semiaristas" (representadas por las dos aristas con direcciones opuestas, entre dos vértices, en la imagen de la derecha). Cada semiarista está "asociada" a una sola cara y, por lo tanto, tiene un puntero a esa cara. Todas las semiaristas asociadas a una cara tienen sentido horario o antihorario. Por ejemplo, en la imagen de la derecha, todas las semiaristas asociadas a la cara central (es decir, las semiaristas "internas") tienen sentido antihorario. Una semiarista tiene un puntero a la siguiente semiarista y a la anterior de la misma cara. Para llegar a la otra cara, podemos ir a la arista gemela de la semiarista y luego recorrer la otra cara. Cada media arista también tiene un puntero a su vértice de origen (el vértice de destino se puede obtener consultando el origen de su gemela o de la siguiente media arista).

Cada vértice contiene sus coordenadas y un puntero a una arista arbitraria cuyo origen es el vértice. Cada cara almacena un puntero a una semi-arista de su límite exterior (si la cara no tiene límites, el puntero es nulo). También contiene una lista de semi-aristas, una por cada agujero que pueda existir dentro de la cara. Si los vértices o las caras no contienen información relevante, no es necesario almacenarlos, lo que ahorra espacio y reduce la complejidad de la estructura de datos.

• Estructura de datos de cuatro aristas
• Lista de rostros doblemente vinculados
• borde alado
• Mapa combinatorio