Una lista de aristas doblemente conectadas , otro nombre es una estructura de datos de medio arista , es una estructura de datos que representa un gráfico plano en un plano o un poliedro en el espacio. Esta estructura proporciona un trabajo eficiente con información topológica asociada a los objetos considerados (vértices, aristas, caras). A menudo se usa en varios algoritmos de geometría computacional para procesar particiones poligonales de un plano, como un gráfico de líneas planas . Por ejemplo, un diagrama de Voronoi generalmente se representa como un DCEL dentro de un cuadro delimitador.
Esta estructura de datos fue propuesta por primera vez por Müller y Preparata [1] para representar un poliedro convexo .
Más tarde, las versiones modificadas de la estructura se generalizaron, pero el nombre permaneció.
La estructura se diseñó originalmente para representar gráficos conectados , pero DCEL también se puede usar para representar gráficos desconectados.
Una lista de aristas doblemente enlazada consta de tipos de objeto como vértice, arista y cara. Estos objetos contienen punteros a otros objetos. Estos pueden ser punteros C/C++ que contienen una dirección en la memoria, o índices de estos objetos en una matriz, o cualquier otro tipo de direccionamiento. Una propiedad indispensable es la capacidad de acceder directamente al objeto al que se hace referencia, sin buscarlo. Cada uno de los objetos también puede contener información adicional, por ejemplo, una cara puede contener información de color o nombre.
Un vértice contiene un solo puntero a cualquier medio borde saliente de ese vértice. También contiene información sobre sus coordenadas.
Una media arista contiene un puntero al vértice que es su origen, un puntero a la cara situada a la izquierda de la arista, así como punteros a la siguiente media arista, la media arista anterior y la media arista del gemelo. borde. El borde se encuentra a la izquierda, por lo que el medio borde gemelo describe el lado derecho del borde, completándolo así en su totalidad.
Una cara contiene un puntero a cualquier semiarista que forma su límite. También puede contener una lista de medias aristas de todos sus agujeros, una media arista por agujero.
Un ejemplo simple de implementación de DCEL en C++.
estructura vértice ; estructura Half_edge ; estructura Cara ; // Estructura de vértice Vértice { doble x , y ; mitad_arista * mitad_arista ; }; // Estructura de medio borde Half_edge { Half_edge * siguiente , * gemelo , * anterior ; Vértice * origen ; cara * cara ; }; // Cara con agujeros struct Cara { medio_borde * límite ; Half_edge ** agujeros ; unsigned long int count_of_holes ; };