Half-edge data structure

A Half-Edge data structure or doubly connected edge list ( DCEL ) ( Engl. Double chained edge list) is a data structure for planar graphs . It consists of nodes , half-edges and surfaces. Each edge is represented by two opposing half-edges, each of which is assigned its start node, adjacent surface, other half-edges of the same edge and the next half-edge of the same surface. Conversely, nodes and surfaces also “know” their respective neighbors.

This structure enables neighborhood questions to be answered quickly and allows efficient iteration around areas and nodes, especially on unstructured grids. It is therefore particularly suitable for unstructured spatial data sets such as those used in finite element methods , as well as computer graphics and polygon networks in general.

construction

A half-edge data structure consists of nodes, half-edges and surfaces, each of which is stored in a list. At least some of its “neighbors” are stored for each of these elements. H. adjacent ( “incident” ) elements. For example, the area adjacent to each half edge is stored (or a pointer to this area).

Half edges

Section of a DCEL. An edge e, its successor next (e), its predecessor prev (e), and its twin twin (e) are shown as examples.

Characteristic and eponymous for the half-edge data structure is the fact that connections between two points are not represented by a single (“full”) edge, but consist of exactly two so-called half- edges. These are directed in opposite directions , i.e. H. the destination node of one half edge is the start node of the other half edge and vice versa. The advantage of this procedure is, among other things, that the predecessor, successor and adjacent area can be clearly assigned to each half-edge. Such relationships are explained in more detail in the next sections.

The gray arrows symbolize the link between the respective half-edge and its successor. A special case occurs at the bottom right: The successor of the half-edge is also its twin!

Up to three additional edges are assigned to each half edge, the English names are in brackets:

• Successor (“next half-edge”): the following edge that is incident on the same surface.
• Zwilling ("twin"): The other, opposite half-edge of the same edge.
• Predecessor ("previous half-edge"): The previous edge that was incident on the same surface.

The “next” edge is clearly defined as the edge that is encountered first when walking clockwise around the target node .

You can also imagine that the half-edges run counter- clockwise around the incident surface. However, it should be noted that this view of isolated subgraphs , which are in turn in another area (See section surfaces ) , may be counter-intuitive, since the outer edges of this half subgraphs apparently in the running direction.

The following are also saved for each edge:

• Start node ("origin", "source")
• Incident face ("face"): the face on the left side of the half-edge.

node

Since most of the connectivity information is already in the half-edges, there is only one node for each node

• Outgoing edge ("Incident Edge")

saved.

Since nodes are mostly points in a space, the coordinates are usually also saved.

Surfaces

Area F in light gray and its outer component and the, in this case two, inner components - each identified via a half-edge of the component that is incident to the area.

Surfaces are defined by the cycles of half-edges that border them. This can be several cycles if there are other components in the area itself . Instead of treating these connected components as a separate object, a half-edge of each of these cycles is simply saved.

• Outer component ("Outer Component"): Cycle that outlines the surface
• Inner Components ("Inner Components"): List of cycles that lie within the surface.

Combined inquiries or operations

Complex inquiries can be answered by combining the various relationships:

• Target node of a half edge = start node of the twin
• Neighboring surface along a half-edge = incident surface of the twin of the half-edge
• All half-edges incidental to a surface:
  • first half edge = outer component of the surface (inner components analogous)
  • Follow the successor until you are back at the first half-edge.
• All surfaces incident to a node: See sample code below.

Sample code

Sample code for iterating over all surfaces that are incident to a node. The algorithm corresponds to that for the iteration over all incident half-edges, with the difference that in each case the area of ​​the current half-edge has to be determined, with which something can then be done.

erste_halbkante = incidentEdge(knoten);
aktuelle_halbkante = erste_halbkante;
do {
    tue_irgendwas( incidentFace(aktuelle_halbkante));
    aktuelle_halbkante = next(twin(aktuelle_halbkante));
} while( aktuelle_halbkante != erste_halbkante)

See also polygon mesh # runtime comparison for further query classes and runtime comparisons.

Redundancy and implicit information

Even a data structure that only consists of half edges, the twin and the successor relation, already offers a large part of the range of functions! A traversal of the graph is already possible. Surfaces and nodes are already implicitly included. The cycle that results when you walk along the successors from a half-edge until you get back to the same edge, borders a surface. A slightly more complicated cycle, created by alternately walking along twin and successor, identifies a node.

Such minimalist solutions are in rare cases sufficient. For example, when the areas bordered by the edges do not play a practical role, as in the case of road networks or rivers.

Individual evidence

1. ↑ ^{a b c d} Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications . Springer-Verlag, Berlin / Heidelberg / New York 2000, ISBN 3-540-65620-0 , pp. 31-32
2. ^ Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications . Springer-Verlag, Berlin / Heidelberg / New York 2000, ISBN 3-540-65620-0 , p. 33