Doubly connected edge listThe 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).
Carte combinatoireUne carte combinatoire est un objet combinatoire qui intervient dans la modélisation de structures topologiques subdivisées en objets. La version la plus simple en est la carte planaire, structure combinatoire pour la représentation de graphes planaires dans le plan. Le concept de carte combinatoire a été introduit de manière informelle au début des années 1960 par Jack Edmonds pour la modélisation de surfaces polyédriques.
Quad-edgeA quad-edge data structure is a computer representation of the topology of a two-dimensional or three-dimensional map, that is, a graph drawn on a (closed) surface. It was first described by Jorge Stolfi and Leonidas J. Guibas. It is a variant of the earlier winged edge data structure. The fundamental idea behind the quad-edge structure is the recognition that a single edge, in a closed polygonal mesh topology, sits between exactly two faces and exactly two vertices.
Mesh (objet)Un en ou maillage est un objet tridimensionnel constitué de sommets, d'arêtes et de faces organisés en polygones sous forme de fil de fer dans une infographie tridimensionnelle. Les faces se composent généralement de triangles, de quadrilatères ou d'autres polygones convexes simples, car cela simplifie le rendu. Les faces peuvent être combinées pour former des polygones concaves plus complexes, ou des polygones avec des trous. L'étude des en fait partie importante de l'infographie tridimensionnelle.
