Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Requirements for a Halfedge_data_structure

Definition

A Halfedge_data_structure consists of vertices V, edges E, facets F and an incidence relation on them. Each edge is represented by two halfedges with opposite orientations. Vertices and facets are optional. See Figure  reference arrow for the incidences stored and the mandatory or optional member functions possible for vertices, halfedges and facets.

Class Diagram
Figure: The three classes Vertex, Halfedge, and Facet of the halfedge data structure. Member functions with shaded background are mandatory. The others are optionally supported.

A model for the Halfedge_data_structure concept must provide the following types and operations. In addition, the local types Vertex, Halfedge and Facet must fulfill the requirements listed in the Sections reference to reference.

Types

Halfedge_data_structure::Vertex
vertex type.

Halfedge_data_structure::Halfedge
halfedge type.

Halfedge_data_structure::Facet
facet type.

Halfedge_data_structure::Size
type for size values.

Halfedge_data_structure::Difference
type for difference values.


Halfedge_data_structure::Point
type for the (optionally) associated geometry for vertices. If no point geometry is supported, the type is void*.

For the following iterators exist appropriate const iterators too.

Halfedge_data_structure::Vertex_iterator
iterator over all vertices.

Halfedge_data_structure::Halfedge_iterator
iterator over all halfedges.

Halfedge_data_structure::Facet_iterator
iterator over all facets.

Halfedge_data_structure::iterator_category
category for all iterators.

Creation

Halfedge_data_structure hds;
the empty data structure hds.


Halfedge_data_structure hds ( Size v, Size h, Size f);
a data structure hds with storage reserved for v vertices, h halfedges, and f facets. The reservation sizes are a hint for optimizing storage allocation.

void hds.reserve ( Size v, Size h, Size f)
reserves storage for v vertices, h halfedges, and f facets. The reservation sizes are a hint for optimizing storage allocation. If the capacity() is already greater than the requested size nothing happens. If the capacity changes all iterators and circulators might be invalidated.

Access Member Functions

Size hds.size_of_vertices () const
number of vertices.
Size hds.size_of_halfedges () const
number of halfedges.
Size hds.size_of_facets () const
number of facets.
Size hds.capacity_of_vertices () const
space reserved for vertices.
Size hds.capacity_of_halfedges () const
space reserved for halfedges.
Size hds.capacity_of_facets () const
space reserved for facets.
std::size_t hds.bytes () const bytes used for hds.
std::size_t hds.bytes_reserved () const
bytes reserved for hds.

The following member functions return the non-mutable iterator or non-mutable circulator respectively if the halfedge data structure will be declared const.

Vertex_iterator hds.vertices_begin ()
iterator over all vertices.
Vertex_iterator hds.vertices_end ()
Halfedge_iterator hds.halfedges_begin ()
iterator over all halfedges
Halfedge_iterator hds.halfedges_end ()
Facet_iterator hds.facets_begin ()
iterator over all facets.
Facet_iterator hds.facets_end ()

Insertion

The following operations allocate a new element of the named item. Halfedges are always allocated in pairs of opposite halfedges. The opposite pointers are automatically set. Note that new_vertex() and new_facet() might not be present for halfedge data structures that do not support vertices or facets respectively.

Vertex* hds.new_vertex () creates a default vertex.
Vertex* hds.new_vertex ( const Vertex* v)
creates a copy of v.
Vertex* hds.new_vertex ( const Point& p)
creates a new vertex initialized to p.
Halfedge* hds.new_edge () creates a new pair of opposite halfedges.
Halfedge* hds.new_edge ( const Halfedge* h)
creates a copy of the two halfedges h and h->opposite().
Facet* hds.new_facet () creates a default facet.
Facet* hds.new_facet ( const Facet* f)
creates a copy of f.

Removal

The following operations erase an element referenced by a pointer. Halfedges are always deallocated in pairs of opposite halfedges, however, the halfedge pointer might denote any of the two possible halfedges. Erasing single elements is optional and indicated with the type tag Supports_removal. The pop_back member functions, which remove the element that was created last, and the deletion of all items are mandatory, if the corresponding item is supported.

void hds.delete_vertex ( Vertex* v)
deletes the vertex v.
void hds.delete_edge ( Halfedge* h)
deletes the pair of opposite halfedges h.
void hds.delete_facet ( Facet* f)
deletes the facet f.

void hds.vertex_pop_back ()
removes last vertex. Mandatory.
void hds.edge_pop_back ()
removes last pair of halfedges. Mandatory.
void hds.facet_pop_back ()
removes last facet. Mandatory.
void hds.delete_all () deletes all elements. Mandatory.

Operations with Border Halfedges


begin of advanced section

The following notion of border halfedges is particularly useful where the halfedge data structure is used to model surfaces with a border. The halfedge data structure does not support holes within a facet, but the surface can have open regions. Halfedges at the border of the surface are called border halfedges. A halfedge is a border edge if the halfedge itself or its opposite halfedge are border halfedges. The only requirement to work with border halfedges is that the Halfedge class provides a member function is_border() returning a bool. Usually, the halfedge data structure supports facets and a NULL facet pointer will indicate a border halfedge, but this is not the only possibility. The is_border() predicate divides the edges into two classes, the border edges and the non-border edges. The following normalization reorganizes the sequential storage of the edges such that the non-border edges precede the border edges, and that for each border edge the latter of the two halfedges is a border halfedge (the first one might be a border halfedge too). The normalization stores the number of border halfedges, as well as the halfedge iterator where the border edges start at, within the halfedge data structure. Halfedge insertion or removal and changing the border status of a halfedge may invalidate these values, which are not automatically updated.

void hds.normalize_border ()
sorts halfedges such that the non-border edges precede the border edges. For each border edge that is incident to a facet, the halfedge iterator will reference the halfedge incident to the facet right before the halfedge that is not incident to a facet.

Size hds.size_of_border_halfedges () const
number of border halfedges. An edge with no incident facet counts as two border halfedges.
Precondition: normalize_border() has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then.

Size hds.size_of_border_edges () const
number of border edges. If size_of_border_edges() is equal to size_of_border_halfedges() all border edges are incident to a facet on one side and to no facet on the other side.
Precondition: normalize_border() has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then.

Halfedge_iterator hds.border_halfedges_begin ()
halfedge iterator starting with the border edges. The range [halfedges_begin(), border_halfedges_begin()) denotes all non-border edges. The range [border_halfedges_begin(), halfedges_end()) denotes all border edges.
Precondition: normalize_border() has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then.


end of advanced section

Types for Tagging Optional Features


begin of advanced section

The nested types below are either equal to Tag_true or Tag_false, depending on whether the named member function is supported or not. Those related to vertices, halfedges and facets are identical to the definitions for the local vertex, halfedge or facet class respectively.

Halfedge_data_structure::Supports_vertex_halfedge
Vertex::halfedge().

Halfedge_data_structure::Supports_vertex_point
Vertex::point().

Halfedge_data_structure::Supports_halfedge_prev
Halfedge::prev().

Halfedge_data_structure::Supports_halfedge_vertex
Halfedge::vertex().

Halfedge_data_structure::Supports_halfedge_facet
Halfedge::facet().

Halfedge_data_structure::Supports_facet_halfedge
Facet::halfedge().


Halfedge_data_structure::Supports_removal
the halfedge data structure supports the removal of individual elements of a surface, i.e. delete_edge(), delete_vertex() if vertices are supported, and delete_facet() if facets are supported.

The following dependencies among these options must be regarded:

Vertices are supported Supports_halfedge_vertex Tag_true.
Facets are supported Supports_halfedge_facet Tag_true.
Supports_vertex_halfedge Tag_true Supports_halfedge_vertex Tag_true.
Supports_vertex_point Tag_true Supports_halfedge_vertex Tag_true.
Supports_facet_halfedge Tag_true Supports_halfedge_facet Tag_true.


end of advanced section

See Also

Halfedge_data_structure_decorator in Section reference. Polyhedron_3 in Chapter reference.


Next: Class declaration of Vertex
Navigation: Up, Table of Contents, Bibliography, Index, Title Page
The GALIA project. Jan 18, 2000.