Doubly-connected edge list

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 verwendet.

Inhaltsverzeichnis

Definition

Sei G = (V,E) ein planarer Graph, V = {v1,v2,...,vn} die Menge der Knoten, E = {e1,e2,...,em} die Menge der Kanten.

Die DCEL speichert für jede Kante ei des Graphens einen Eintrag mit den Daten (V1,V2,F1,F2,P1,P2):

  • V1: Startknoten der Kante ei
  • V2: Endknoten der Kante ei
  • F1: Name der Fläche auf der linken Seite der Kante
  • F2: Name der Fläche auf der rechten Seite der Kante
  • P1: Zeiger auf die erste Kante mit Knoten V1, auf die man trifft, wenn man die Kante ei gegen den Uhrzeigersinn um V1 dreht
  • P2: Analog zu P1, diesmal mit Knoten V2

Beispiel

Beispielgraph

Für den Graphen in der Abbildung werden folgende Einträge gespeichert:

V1 V2 F1 F2 P1 P2
e1 v1 v2 f1 f2 e6 e2
e2 v2 v3 f1 f2 e1 e3
e3 v3 v1 f3 f2 e4 e1
e4 v3 v4 f1 f3 e2 e6
e5 v4 v5 f1 f1 e4 e5
e6 v4 v1 f1 f3 e5 e3

Anwendungen und Sonstiges

Mit Hilfe der Verweise auf die Nachfolgekanten können effizient alle Kanten mit vorgegebenen Endpunkt bestimmt werden, ebenso alle Kanten auf dem Rand einer gegebenen Fläche.

Als Doubly-connected edge list wird ebenfalls die etwas anders aufgebaute Half-Edge-Datenstruktur bezeichnet. DCEL ist eine Variante der winged-edge-Datenstruktur.

Fügt man zusätzlich die Kanten ein, die man erhält, wenn man ei im Uhrzeigersinn um V1 und V2 dreht, erhält man die quad edge data structure (QEDS). Mit ihr lassen sich Ränder von Flächen und von einem Knoten ausgehende Kanten in beide Richtungen durchlaufen. Ein weiterer Vorteil ist, dass man die QEDS des dualen Graphen erhält, wenn jede Kante durch ihre jeweilige duale Kante ersetzt wird.[1]

Literatur

  • Franco P. Preparata, Michael Ian Shamos: Computational geometry: an introduction. New York : Springer-Verlag, c1985., ISBN 0387961313, S. 15
  • Dinesh P. Mehta, Sartaj Sahni: Handbook of data structures and applications CRC Press, 2004, ISBN 1584884355, S. 17-7
  • Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen. 2. Auflage. Springer, Berlin, Berlin [u.a.] 2005, ISBN 978-3-5402-0956-0., S. 19

Einzelnachweise

  1. Rolf Klein: Algorithmische Geometrie, 2005, S. 19–20.

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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 — 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… …   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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”