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
.
| |
vertex type.
| |
| |
halfedge type.
| |
| |
facet type.
| |
| |
type for size values.
| |
| |
type for difference values.
| |
| |
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.
| |
iterator over all vertices.
| |
| |
iterator over all halfedges.
| |
| |
iterator over all facets.
| |
| |
category for all iterators.
|
| |
the empty data structure hds.
| |
| |
a data structure hds with storage reserved for
vertices, halfedges, and
facets. The reservation sizes are a hint for
optimizing storage allocation.
|
|
| |
reserve storage for vertices, halfedges, and 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. |
|
| |
number of vertices. | ||
|
| |
number of halfedges. | ||
|
| |
number of facets. | ||
|
| |
space reserved for vertices. | ||
|
| |
space reserved for halfedges. | ||
|
| |
space reserved for facets. | ||
|
| bytes used for the polyhedron. |
|
| |
bytes reserved for the polyhedron. |
The following member functions return the non-mutable iterator or non-mutable circulator respectively if the halfedge data structure will be declared const.
|
| |
iterator over all vertices. | ||
|
| |
|
| |
iterator over all halfedges | ||
|
| |
|
| |
iterator over all facets (excluding holes). | ||
|
|
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.
|
| creates a default vertex. |
|
| |
creates a copy of . | ||
|
| |
creates a new vertex initialized to . | ||
|
| creates a new pair of opposite halfedges. |
|
| |
creates a copy of the two halfedges and h->opposite(). | ||
|
| creates a default facet. |
|
| |
creates a copy of . |
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 and the deletion of all items are mandatory, if the item is supported.
|
| |
deletes the vertex . | ||
|
| |
deletes the pair of opposite halfedges . | ||
|
| |
deletes the facet . | ||
|
| |
removes last vertex. Mandatory. | ||
|
| |
removes last pair of halfedges. Mandatory. | ||
|
| |
removes last facet. Mandatory. | ||
|
| deletes all elements. Mandatory. |
The following notion of border halfedges is particular useful where the halfedge data structure is used to model surfaces that might contain holes. Halfedges incident to an hole 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.
|
| |
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 incident to the hole. | ||
|
| |
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. | ||
|
| |
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 a hole 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 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. |
The nested types below are either equal to CGAL_Tag_true or CGAL_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.
| |
Vertex::halfedge().
| |
| |
Vertex::point().
| |
| |
Halfedge::prev().
| |
| |
Halfedge::vertex().
| |
| |
Halfedge::facet().
| |
| |
Facet::halfedge().
| |
| |
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 CGAL_Tag_true.
Facets are supported
Supports_halfedge_facet CGAL_Tag_true.
Supports_vertex_halfedge CGAL_Tag_true
Supports_halfedge_vertex
CGAL_Tag_true.
Supports_vertex_point
CGAL_Tag_true Supports_halfedge_vertex
CGAL_Tag_true.
Supports_facet_halfedge
CGAL_Tag_true
Supports_halfedge_facet CGAL_Tag_true.