The doubly connected edge list (DCEL), also known as half-edge data structure, 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 in question (vertices, edges, faces). It is used in many algorithms of computational geometry to handle polygonal subdivisions of the plane, commonly called planar straight-line graphs (PSLG). For example, a Voronoi diagram is commonly represented by a DCEL inside a bounding box.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Doubly-connected edge list (de)
- Lista de aristas doblemente conectadas (es)
- Doubly connected edge list (en)
- Двусвязный список рёбер (ru)
- Подвійно зв'язаний список ребер (uk)
|
| rdfs:comment
| - 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. (de)
- The doubly connected edge list (DCEL), also known as half-edge data structure, 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 in question (vertices, edges, faces). It is used in many algorithms of computational geometry to handle polygonal subdivisions of the plane, commonly called planar straight-line graphs (PSLG). For example, a Voronoi diagram is commonly represented by a DCEL inside a bounding box. (en)
- Una lista de aristas doblemente conectadas (DCEL por las iniciales de su nombre en inglés: doubly connected edge list), también conocida como estructura de datos de semiaristas, es una estructura de datos empleada para representar el embebido de un grafo plano en un plano, o en un politopo cuando se trata del espacio tridimensional. Esta estructura de datos facilita una manipulación eficiente de la información topológica asociada a los objetos en cuestión (vértices, aristas, caras). Se usa en muchos algoritmos de geometría computacional para manejar subdivisiones poligonales del plano, comúnmente llamadas (PSLG por las iniciales de su nombre en inglés: planar straight-line graph). Por ejemplo, los polígonos de Thiessen normalmente se representan mediante una DCEL dentro de un cuadro delim (es)
- Двусвязный список рёбер (англ. doubly connected edge list) другое название — полурёберная структура данных (англ. half-edge data structure) — это структура данных, которая представляет планарный граф на плоскости или многогранник в пространстве. Эта структура обеспечивает эффективную работу с топологической информацией, связанной с рассматриваемыми объектами (вершинами, рёбрами, гранями). Её часто применяют в различных алгоритмах вычислительной геометрии для обработки разбиений плоскости на многоугольники, таких как . Например, диаграмму Вороного обычно представляют в виде DCEL внутри ограничивающего прямоугольника. (ru)
- Подвійно зв'язаний список ребер (англ. doubly connected edge list) або півреберна структура даних (англ. half-edge data structure) — це структура даних, що представляє вкладення планарного графу на площину або багатогранник у 3D. Ця структура даних забезпечує дієву маніпуляцію топологічною інформацією пов'язаною з об'єктами, що розглядаються (вершини, ребра, грані). Її використовують багато алгоритмів обчислювальної геометрії для обробки полігонального розбиття площини, часто згадуваних як планарні прямолінійні графи. Наприклад, діаграму Вороного зазвичай представляють як ПЗСР всередині обмежувального прямокутника. (uk)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| date
| |
| show
| |
| has abstract
| - 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. (de)
- The doubly connected edge list (DCEL), also known as half-edge data structure, 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 in question (vertices, edges, faces). It is used in many algorithms of computational geometry to handle polygonal subdivisions of the plane, commonly called planar straight-line graphs (PSLG). For example, a Voronoi diagram is commonly represented by a DCEL inside a bounding box. This data structure was originally suggested by Muller and Preparata for representations of 3D convex polyhedra. Later, a somewhat different data structure 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 by introducing dummy edges between disconnected components. (en)
- Una lista de aristas doblemente conectadas (DCEL por las iniciales de su nombre en inglés: doubly connected edge list), también conocida como estructura de datos de semiaristas, es una estructura de datos empleada para representar el embebido de un grafo plano en un plano, o en un politopo cuando se trata del espacio tridimensional. Esta estructura de datos facilita una manipulación eficiente de la información topológica asociada a los objetos en cuestión (vértices, aristas, caras). Se usa en muchos algoritmos de geometría computacional para manejar subdivisiones poligonales del plano, comúnmente llamadas (PSLG por las iniciales de su nombre en inglés: planar straight-line graph). Por ejemplo, los polígonos de Thiessen normalmente se representan mediante una DCEL dentro de un cuadro delimitador. Esta estructura de datos fue sugerida originalmente por Muller y Preparata para representaciones de 3D de politopos convexos. Más adelante se desarrolló una estructura de datos algo diferente, pero se mantuvo el nombre de "DCEL". Por simplificar, solo se consideran grafos conexos, aunque la estructura DCEL también puede extenderse para manejar gráficos desconectados mediante la introducción de bordes ficticios entre componentes desconectados. (es)
- Двусвязный список рёбер (англ. doubly connected edge list) другое название — полурёберная структура данных (англ. half-edge data structure) — это структура данных, которая представляет планарный граф на плоскости или многогранник в пространстве. Эта структура обеспечивает эффективную работу с топологической информацией, связанной с рассматриваемыми объектами (вершинами, рёбрами, гранями). Её часто применяют в различных алгоритмах вычислительной геометрии для обработки разбиений плоскости на многоугольники, таких как . Например, диаграмму Вороного обычно представляют в виде DCEL внутри ограничивающего прямоугольника. Эту структуру данных впервые предложили Мюллер и Препарата для представления выпуклого многогранника. Позже распространение получили изменённые варианты структуры, но название осталось. Изначально структура создавалась для представления связных графов, однако DCEL можно использовать и для представления несвязных графов. (ru)
- Подвійно зв'язаний список ребер (англ. doubly connected edge list) або півреберна структура даних (англ. half-edge data structure) — це структура даних, що представляє вкладення планарного графу на площину або багатогранник у 3D. Ця структура даних забезпечує дієву маніпуляцію топологічною інформацією пов'язаною з об'єктами, що розглядаються (вершини, ребра, грані). Її використовують багато алгоритмів обчислювальної геометрії для обробки полігонального розбиття площини, часто згадуваних як планарні прямолінійні графи. Наприклад, діаграму Вороного зазвичай представляють як ПЗСР всередині обмежувального прямокутника. Цю структуру даних вперше представили Мюллер і Препарата для представлення тривимірного опуклого політопа. Пізніше набули поширення змінені варіанти структури, але назва залишилась. Звичайно структуру використовують для зв'язних графів, однак ПЗСР можна використовувати і для незв'язних графів також. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
