Lista de aristas doblemente conectadas

Cada semiarista tiene exactamente una semiarista previa, una semiarista siguiente y una semiarista gemela

Una lista de aristas doblemente conectadas (DCEL por las iniciales de su nombre en inglés: doubly connected edge list), también conocida como estructura de datos de semiaristas, es una estructura de datos empleada para representar el embebido de un grafo plano en un plano, o en un politopo cuando se trata del espacio tridimensional. Esta estructura de datos facilita una manipulación eficiente de la información topológica asociada a los objetos en cuestión (vértices, aristas, caras). Se usa en muchos algoritmos de geometría computacional para manejar subdivisiones poligonales del plano, comúnmente llamadas grafo de línea recta plano (PSLG por las iniciales de su nombre en inglés: planar straight-line graph). Por ejemplo, los polígonos de Thiessen normalmente se representan mediante una DCEL dentro de un cuadro delimitador.

Esta estructura de datos fue sugerida originalmente por Muller y Preparata​ para representaciones de 3D de politopos convexos.

Más adelante se desarrolló una estructura de datos algo diferente, pero se mantuvo el nombre de "DCEL".

Por simplificar, solo se consideran grafos conexos, aunque la estructura DCEL también puede extenderse para manejar gráficos desconectados mediante la introducción de bordes ficticios entre componentes desconectados.​

Estructura de datos

Una DCEL es más que una lista doblemente enlazada de aristas. En el caso 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 valor de su área. Cada arista suele delimitar dos caras y, por lo tanto, es conveniente considerar cada arista como dos semiaristas (que están representadas por dos aristas con direcciones opuestas, entre dos vértices, en la imagen arriba a la derecha). Cada semiarista está asociada con una sola cara y, por lo tanto, tiene un puntero a esa cara. Todas las semiaristas asociadas con una cara están dadas en sentido horario o antihorario. Por ejemplo, en la imagen anterior, todas las semiaristas asociadas con la cara central (es decir, las semiaristas internas) están orientadas en el sentido contrario a las agujas del reloj. Una semiarista tiene un puntero a la semiarista siguiente y a la semiarista previa de la misma cara. Para llegar a la otra cara, se debe localizar la semiarista gemela y luego atravesar la otra cara. Cada semiarista 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 semiarista).

Cada vértice contiene las coordenadas del vértice y también almacena un puntero a una arista arbitraria que tiene el vértice como origen. Cada cara almacena un puntero a alguna semiarista de su límite exterior (si la cara no tiene límites, entonces el puntero es nulo). También dispone de una lista de semiaristas, una por cada hueco que pueda incidir en la cara. Si los vértices o las caras no contienen información interesante, no es necesario almacenarlos, ahorrando espacio y reduciendo la complejidad de la estructura de datos.

Véase también

• Estructura de datos de arista cuádruple
• Lista de caras doblemente enlazadas
• Arista alada
• Mapa combinatorio

Referencias

• Datos: Q1251544