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

PropertyValue
dbpprop:abstract
  • 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). This data structure was originally suggested by Muller and Preparata 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.
  • 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 Algorithmische Geometrie verwendet.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • 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).
  • 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 Algorithmische Geometrie verwendet.
rdfs:label
  • Doubly-connected edge list
  • Doubly-connected edge list
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of