Skip navigation links
halfedge by
jTEM

Package de.jtem.halfedge

Provides the classes for a half-edge data structure.

See: Description

Package de.jtem.halfedge Description

Provides the classes for a half-edge data structure.

Cell decompositions of surfaces

Half-edge data structures are used primarily to represent cell decompositions of oriented surfaces.

We say "primarily" because half-edge data structures can be used to represent somewhat more general combinatorial structures, such as, for example, a checker board surface with white squares removed.

Here, surface means two-dimensional manifold, possibly with boundary; and a cell decomposition of a surface is a graph embedded in the surface such that the complement of the graph is (topologically) a disjoint union of open disks. The term map on a surface means the same. Thus, a cell decomposition decomposes a surface into vertices, edges, and faces.

Regular and strongly regular

A cell decomposition of a surface is called regular, if it has no loops (edges with the same vertex on both ends), and if the boundary of a face contains an edge or vertex at most once. It is called strongly regular if two edges have at most one vertex in common, and if two faces have at most one edge or one vertex in common. A strongly regular cell decomposition is usually called a mesh.

This half-edge data structure implementation

This half-edge data structure implementation consists of different types of objects representing vertices, half-edges, and faces. The term half-edge can and should be thought of as synonymous with oriented edge or directed edge.

Every half-edge object holds references to:

• its oppositely oriented companion edge
• the next edge in the boundary of the face on its left hand side
• the previous edge in the boundary of the face on its left hand side
• the face on its left hand side
• the vertex it points to.

The face and vertex objects hold back references to a half-edge referencing them.

Finally, there is the class HalfEdgeDataStructure representing a whole half-edge data structure. It acts as a container for (and sort of factory of) its vertices, edges, and faces.

Use of generics

Typically, one wants to equip vertices, edges, and faces with additional properties or functionality. For example, vertices may have coordinates associated with them, edges may have weights, and faces may have colors.

Our half-edge data structure facilitates this by using generic classes as abstract base classes for vertex, edge, and face types: The classes Vertex, Edge, Face are all parameterized with the associated vertex, edge, and face types.

Example. To create a half-edge data structure with vertices that have 2D coordinates, proceed as follows.

• Step 1. Define appropriate subclasses of Vertex, Edge, Face, for example:

public class MyVertex extends Vertex<MyVertex, MyEdge, MyFace> {public Point2D p;}
public class MyEdge extends Edge<MyVertex, MyEdge, MyFace> {}
public class MyFace extends Face<MyVertex, MyEdge, MyFace> {}

(Of course you might make the property p of MyEdge private and provide getter and setter methods, etc.) Note that you always have to subclass Vertex, Edge, and Face, even if you do not define any additional functionality or properties.

• Step 2. Instantiate a HalfEdgeDataStructure:

HalfEdgeDataStructure<MyVertex,MyEdge,MyFace> heds = new HalfEdgeDataStructure<MyVertex,MyEdge,MyFace>(MyVertex.class, MyEdge.class, MyFace.class);

The parameters of the constructor serve as run time type tokens.

• Step 3. Instantiate vertices, edges, and faces using addNewVertex(), addNewEdge(), and addNewFace(), like this:

MyVertex v = heds.addNewVertex();
MyEdge e = heds.addNewEdge();
MyFace f = heds.addNewFace();

Skip navigation links
halfedge by
jTEM

jTEM