The half-edge structure is a data structure for efficiently storing and manipulating a restricted set of finite 2-dimensional cell-complexes.
An open (closed) cell is a topological space which is homeomorphic to an open (closed) ball in , for some . A cell is either an open cell or a closed cell. Given a cell, its associated is called its dimension; then a cell is called an -cell. Let be a topological space. A cell-decomposition of is a partition of into open cells, such that if is an open -cell, with , then there exists a continuous map, called a characteristic map, from some closed -cell into , which restricts to a homeomorphism from the interior of onto , and maps the boundary of into the union of all open cells, of the cell-decomposition, of dimensions less than . The dimension of a cell-decomposition is the supremum of the dimensions of its open cells. A cell-complex is a Hausdorff space , together with a cell-decomposition of .
The half-edge structure is a finite 2-dimensional cell-complex, with the added requirement that the boundary of each open -cell in the cell-decomposition, for , be a union of lower-dimensional open cells. The 0-cells, 1-cells, and 2-cells, of the half-edge structure, are called vertices , edges, and polygons, respectively.
In addition to the cells, the half-edge structure also includes half-edges, which encode most of the information in the cell-decomposition. The half-edges are directed edges of which there are 2 for each edge, oriented oppositely. Given a half-edge H, the oppositely oriented half-edge is called the pair of H. Every half-edge has an origin vertex and a destination vertex. If a half-edge has A and B as origin and destination, respectively, then its pair has B and A as origin and destination, respectively. Every half-edge has a successor and a predecessor. These links form a loop, and thus each half-edge is associated to some loop, dividing the set of half-edges into equivalence classes. Each loop can contain a polygon. However, the loop can also be empty, representing a hole.
HalfMeshHalfEdgeThe half-edge structure implementation in Pastel has the following properties:
| Task / Property | Complexity |
|---|---|
| Insert / remove an isolated vertex. | |
| Insert an edge from vertex u to vertex v. | |
| Insert / remove a polygon specified with edges. | |
| Insert a polygon specified with vertices . | |
| Find a half-edge connected to a given vertex / edge / polygon. | |
| Find the pair / successor / origin / polygon of a half-edge. | |
| Space |
Here is the number of vertices, is the number of edges, and is the number of polygons in the half-edge structure. In addition, is the number of edges incident to vertex . Combining the above, it follows that the predecessor / destination of a half-edge can also be found in time.
The half-edge structure can solve the following problems efficiently (in linear time over the number of elements in the neighborhood):
Finally, the half-edge structure allows efficient manipulation of the cell-decomposition, including joining and splitting cells.
The half-edge structure can represent
Introduction to Topological Manifolds, 2nd edition, John Lee, Graduate Texts in Mathematics, Springer, 2010.