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  for the incidences stored and the mandatory or optional member functions possible for vertices, halfedges and facets.

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  to .

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

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.

Types for Tagging Optional Features

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.

See Also

Halfedge_data_structure_decorator in Section . Polyhedron_3 in Chapter .