Doubly-connected edge list
- Doubly-connected edge list
The doubly-connected edge list (DCEL) is a data structure to represent an embedding of a planar graph in the plane and polytopes in 3D. This data structure provide efficient manipulation of the topological information associated with the objects in question (vertices, edges, faces). It is used in many algorithms of computational geometry to handle polygonal subivisions of the plane, commonly called planar straight-line graphs (PSLG). [DCELs may be found in all major books in computational geometry.]
This data structure was originally suggested by Muller and Preparata [Muller, D. E. ; Preparata, F. P. "Finding the Intersection of Two Convex Polyhedra", Tech. Rept. UIUC, 1977, 38pp, also "Theoretical Computer Science", Vol. 7, 1978, 217-236 ] for representations of 3D convex polyhedra.
Later a somewhat different data structuring was suggested, but the name "DCEL" was retained.
For simplicity, only connected graphs are considered, however the DCEL structure may be extended to handle disconnected graphs as well.
References
Wikimedia Foundation.
2010.
Look at other dictionaries:
Doubly connected edge list — The doubly connected edge list (DCEL) is a data structure to represent an embedding of a planar graph in the plane and polytopes in 3D. This data structure provides efficient manipulation of the topological information associated with the objects … Wikipedia
Doubly-connected edge list — Die Doubly connected edge list (DCEL, doppelt verkettete Kantenliste) ist eine Datenstruktur, die einen zusammenhängenden planaren Graphen repräsentiert, der in die Ebene eingebettet ist. Die Datenstruktur wird in der algorithmischen Geometrie… … Deutsch Wikipedia
List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… … Wikipedia
Half-Edge-Datenstruktur — Eine Half Edge Datenstruktur oder auch Doubly Connected Edge List (DCEL) (engl. Doppelt verkette Kantenliste) ist eine Datenstruktur für planare Graphen. Sie besteht aus Knoten, Halbkanten (half edges) und Flächen. Dabei wird jede Kante durch… … Deutsch Wikipedia
Winged Edge — Zur Speicherung von Polygonen und polygonalen Netzen, wie sie in der 3D Computergrafik verwendet werden, gibt es eine Reihe bekannter Datenstrukturen. Die bekanntesten Strukturen sind die Knotenliste, Kantenliste, Winged Edge und die doppelt… … Deutsch Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
List of Pokémon (202–251) — Contents 1 Wobbuffet 2 Girafarig 3 Pineco 4 Forretress … Wikipedia
Linked list — In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the… … Wikipedia
Graph embedding — In topological graph theory, an embedding of a graph G on a surface Sigma; is a representation of G on Sigma; in which points of Sigma; are associated to vertices and simple arcs (homeomorphic images of [0,1] ) are associated to edges in such a… … Wikipedia
Planar straight-line graph — (PSLG) is a term used in computational geometry for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments. [cite book author = Franco P. Preparata and Michael Ian Shamos | title = Computational… … Wikipedia
