Lista de aristas doblemente conectadas
La lista de aristas doblemente conectadas ( DCEL ), también conocida como estructura de datos de medio arista , es una estructura de datos para representar una incrustación de un gráfico plano en el plano y politopos en 3D . Esta estructura de datos proporciona una manipulación [ cuantificada ] eficiente de la información topológica asociada con los objetos en cuestión (vértices, aristas, caras). Se utiliza en muchos algoritmos de geometría computacional para manejar subdivisiones poligonales del plano, comúnmente llamados gráficos planos de línea recta.(PSLG). Por ejemplo, un diagrama de Voronoi suele representarse mediante un DCEL dentro de un cuadro delimitador.
Esta estructura de datos fue sugerida originalmente por Muller y Preparata [1] para representaciones de poliedros convexos en 3D .
Posteriormente, se sugirió una estructura de datos algo diferente [ cita requerida ] , pero se mantuvo el nombre "DCEL".
Para simplificar, solo se consideran gráficos conexos [ ¿por quién? ] , sin embargo, la estructura DCEL puede extenderse para manejar gráficos desconectados también mediante la introducción de bordes ficticios entre componentes desconectados. [2]
DCEL es más que una lista de aristas doblemente enlazada . En el caso general, un 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 y, por lo tanto, es conveniente considerar cada arista como dos "medias aristas" (que están representadas por las dos aristas con direcciones opuestas, entre dos vértices, en la imagen de la derecha). Cada medio borde está "asociado" con una sola cara y, por lo tanto, tiene un puntero a esa cara. Todolas semiaristas asociadas con una cara son en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj. Por ejemplo, en la imagen de la derecha, todos los medios bordes asociados con la cara central (es decir, los medios bordes "internos") están en el sentido contrario a las agujas del reloj. Un medio borde tiene un puntero al medio borde siguiente y al medio borde anterior de la misma cara. Para llegar a la otra cara, podemos ir al gemelo de la media arista 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 gemelo o de la siguiente media arista).
Cada vértice contiene las coordenadas del vértice y también almacena un puntero a un borde arbitrario que tiene el vértice como origen. Cada cara almacena un puntero a algún medio borde de su límite exterior (si la cara no tiene límites, entonces el puntero es nulo). También dispone de una lista de medias aristas, 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.
