Class | Description |
---|---|
Edge<V extends Vertex<V,E,F>,E extends Edge<V,E,F>,F extends Face<V,E,F>> |
Abstract base class for classes representing edges of a
HalfEdgeDataStructure . |
Edge.Naked | |
Face<V extends Vertex<V,E,F>,E extends Edge<V,E,F>,F extends Face<V,E,F>> |
Abstract base class for classes representing faces of a
HalfEdgeDataStructure . |
Face.Naked |
A face class with no further properties or functionality.
|
HalfEdgeDataStructure<V extends Vertex<V,E,F>,E extends Edge<V,E,F>,F extends Face<V,E,F>> |
Class representing a half-edge data structure.
|
Node<V extends Vertex<V,E,F>,E extends Edge<V,E,F>,F extends Face<V,E,F>> |
The abstract base class for any vertex, edge and face class.
|
Vertex<V extends Vertex<V,E,F>,E extends Edge<V,E,F>,F extends Face<V,E,F>> |
Abstract base class for classes representing vertices of a
HalfEdgeDataStructure . |
Vertex.Naked |
A vertex class with no further properties or functionality.
|
Exception | Description |
---|---|
HalfedgeException |
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.
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.
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();