Decorator for Halfedge Data Structures

The class Halfedge_data_structure_decorator<HDS> provides additional functions to examine and to modify a halfedge data structure. All these functions take care of the different capabilities a certain halfedge data structure may have or may not have. The functions evaluate the support type tags of the halfedge data structure to decide on the actions. If the feature is not supported nothing is done. Note that for example the creation of new halfedges is mandatory for all halfedge data structures and will not appear here again.

#include <CGAL/Halfedge_data_structure_decorator.h>

Types

Halfedge_data_structure_decorator<HDS>::HDS
	the type of the halfedge data structure.
Halfedge_data_structure_decorator<HDS>::Vertex
	the vertex type of the halfedge data structure.
Halfedge_data_structure_decorator<HDS>::Halfedge
	the halfedge type of the halfedge data structure.
Halfedge_data_structure_decorator<HDS>::Facet
	the facet type of the halfedge data structure.
Halfedge_data_structure_decorator<HDS>::Point
	the point type used in the vertex if points are supported.

Creation

Halfedge_data_structure_decorator<HDS> D;

Access Functions

Halfedge*	D.get_vertex_halfedge ( Vertex* v)
		returns the incident halfedge of $$v if supported, NULL otherwise.
Vertex*	D.get_vertex ( Halfedge* h)
		returns the incident vertex of $$h if supported, NULL otherwise.
Halfedge*	D.get_prev ( Halfedge* h)
		returns the previous halfedge of $$h if supported, NULL otherwise.
Halfedge*	D.find_prev ( Halfedge* h)
		returns the previous halfedge of $$h. Uses the prev() method if supported or performs a search around the facet using next().
Facet*	D.get_facet ( Halfedge* h)
		returns the incident facet of $$h if supported, NULL otherwise.
Halfedge*	D.get_facet_halfedge ( Facet* f)
		returns the incident halfedge of $$f if supported, NULL otherwise.

Creation of New Primitives

Vertex*	D.new_vertex ( HDS& hds)
		returns a new vertex from hds if vertices are supported, NULL otherwise.
Vertex*	D.new_vertex ( HDS& hds, const Vertex* v)
		returns a copy of $$v from hds if vertices are supported, NULL otherwise.
Vertex*	D.new_vertex ( HDS& hds, Point p)
		returns a new vertex from hds initialized to $$p if vertices and points are supported, NULL otherwise.
Facet*	D.new_facet ( HDS& hds)
		returns a new facet from poly if facets are supported, NULL otherwise.
Facet*	D.new_facet ( HDS& hds, const Facet* f)
		returns a copy of $$f from hds if facets are supported, NULL otherwise.

Creation of New Composed Items

Halfedge*	D.create_loop ( HDS& hds)
		returns a halfedge from a newly created loop in hds consisting of a single closed edge, one vertex and two facets (if supported respectively).
Halfedge*	D.create_segment ( HDS& hds)
		returns a halfedge from a newly created segment in hds consisting of a single open edge, two vertices and one facet (if supported respectively).

Removal of Elements

void	D.delete_vertex ( HDS& hds, Vertex* v)
		removes the vertex $$v if vertices are supported.
void	D.delete_facet ( HDS& hds, Facet* f)
		removes the facet $$f if facets are supported.
void	D.erase_facet ( HDS& hds, Halfedge* h)
		removes the facet incident to h from hds and changes all halfedges incident to the facet into border edges or removes them from the hds if they were already border edges, i.e. if there remains no facet incident to this edge after removing the facet. See make_hole(h) for a more specialized variant. Precondition: h != NULL. If facets are supported, Supports_removal must be equivalent to Tag_true.
void	D.erase_connected_component ( HDS& hds, Halfedge* h)
		removes the vertices, halfedges, and facets that belong to the connected component of $$h. Precondition: Supports_removal must be equivalent to Tag_true. For all halfedges $$g in the connected component g.next() != NULL.

Modifying Functions (Composed)

void	D.close_tip ( Halfedge* h)
		makes h->opposite() the successor of $$h.
void	D.close_tip ( Halfedge* h, Vertex* v)
		makes h->opposite() the successor of $$h and sets the incident vertex of $$h to $$v.
void	D.insert_tip ( Halfedge* h, Halfedge* v)
		inserts the tip of the edge $$h into the halfedges around the vertex pointed to by $$v. Halfedge h->opposite() is the new successor of $$v and h->next() will be set to v->next(). The vertex of $$h will be the one $$v points to if vertices are supported.
void	D.remove_tip ( Halfedge* h)
		removes the edge h->next()->opposite() from the halfedge cycle around the vertex pointed to by $$h. The new successor halfedge of $$h will be h->next()->opposite()->next().
void	D.insert_halfedge ( Halfedge* h, Halfedge* f)
		inserts the halfedge $$h between $$f and f->next(). The facet of $$h will be the one $$f points to if facets are supported.
void	D.remove_halfedge ( Halfedge* h)
		removes edge h->next() from the halfedge cycle around the facet pointed to by $$h. The new successor of $$h will be h->next()->next().
void	D.set_vertex_in_vertex_loop ( Halfedge* h, Vertex* v)
		loops around the vertex incident to $$h and sets all vertex pointers to $$v. Precondition: h != NULL.
void	D.set_facet_in_facet_loop ( Halfedge* h, Facet* f)
		loops around the facet incident to $$h and sets all facet pointers to $$f. Precondition: h != NULL.
Halfedge*	D.flip_edge ( Halfedge* h)
		performs an edge flip, i.e. Delaunay flip. It returns $$h after rotating the edge $$h one vertex in the direction the facet orientation points to. Precondition: h != NULL and the facet cycles on both sides of $$h are triangles.

Modifying Functions (For Border Halfedges)

Halfedge*	D.make_hole ( HDS& hds, Halfedge* h)
		removes the facet incident to h from hds and creates a hole. Precondition: h != NULL and !(h->is_border()). If facets are supported, Supports_removal must be equivalent to Tag_true.
Halfedge*	D.fill_hole ( HDS& hds, Halfedge* h)
		creates a new facet from hds and fills the hole incident to h. Precondition: h != NULL and h->is_border().
Halfedge*	D.add_facet_to_border ( HDS& hds, Halfedge* h, Halfedge* g)
		creates a new facet from hds within the hole incident to $$h and $$g by connecting the tip of $$g with the tip of $$h with a new halfedge from hds and filling this separated part of the hole with a new facet from hds, such that the new facet is incident to $$g. Returns the halfedge of the new edge that is incident to the new facet. Precondition: h != NULL, g != NULL, h->is_border(), g->is_border() and $$g can be reached along the same hole starting with $$h.

Modifying Functions (Euler Operators)

The following Euler operations modify consistently the combinatorial structure of the halfedge data structure. The geometry remains unchanged. Note that well known graph operations are also captured with these Euler operators, for example an edge contraction is equal to an join_vertex() operation, or an edge removal to join_facet().

Given a halfedge data structure hds and a halfedge pointer $$h four special applications of the Euler operators are: split_vertex(h,h) results in an antenna emanating from the tip of h. split_vertex(h,h->next()->opposite()) results in an edge split of the halfedge h->next with a new vertex in-between. split_facet(h,h) results in a loop directly following h. split_facet(h,h->next()) results in a bridge parallel to the halfedge h->next with a new facet in-between.

Halfedge*	D.split_facet ( HDS& hds, Halfedge* h, Halfedge* g)
		splits the facet incident to h and g into two facets with a new diagonal between the two vertices denoted by h and g respectively. The second (new) facet obtained from hds is a copy of the first facet. The new diagonal is returned. The time is proportional to the distance from h to g around the facet. Precondition: g must be reachable from h around the facet.
Halfedge*	D.join_facet ( HDS& hds, Halfedge* h)
		joins the two facets incident to $$h. The facet incident to h->opposite() gets removed by hds. Both facets might be holes. Returns the predecessor of $$h around the facet. The invariant join_facet( split_facet( h, g)) returns $$h and keeps the data structure unchanged. The time is proportional to the size of the facet removed and the time to compute h->prev(). Precondition: HDS supports removal of halfedges and facets.

Halfedge*	D.split_vertex ( HDS& hds, Halfedge* h, Halfedge* g)
		splits the vertex incident to h and g into two vertices and connects them with a new edge. The second (new) vertex obtained from hds is a copy of the first vertex. The new edge is returned. The time is proportional to the distance from h to g around the vertex. Precondition: g must be reachable from h around the vertex.
Halfedge*	D.join_vertex ( HDS& hds, Halfedge* h)
		joins the two vertices incident to $$h. The vertex denoted by h->opposite() gets removed by hds. Returns the predecessor of $$h around the vertex. The invariant join_vertex( split_vertex( h, g)) returns $$h and keeps hds unchanged. The time is proportional to the degree of the vertex removed and the time to compute h->prev(). Precondition: HDS supports removal of vertices and halfedges.

Halfedge*	D.split_loop ( HDS& hds, Halfedge* h, Halfedge* i, Halfedge* j)
		cuts the halfedge data structure into two parts along the cycle $$(h,i,j). Three new vertices (one copy for each vertex in the cycle) and three new halfedges (one copy for each halfedge in the cycle), and two new triangles will be created. $$h,i,j will be incident to the first new triangle. The return value will be a halfedge denoting the new halfedge of the second new triangle which was h-opposite() beforehand. Precondition: $$h,i,j are distinct, consecutive vertices of the halfedge data structure and form a cycle: i.e. h->vertex() == i->opposite()->vertex(), ..., j->vertex() == h->opposite()->vertex().
Halfedge*	D.join_loop ( HDS& hds, Halfedge* h, Halfedge* g)
		glues the boundary of two facets together. Both facets and the vertices of the facet loop $$g gets removed. Returns $$h. Both facets might be holes. The invariant join_loop( h, split_loop( h, i, j)) returns $$h and keeps the data structure unchanged. Precondition: HDS supports removal of vertices, halfedges, and facets. The facets denoted by $$h and $$g are different and have an equal degree (i.e. number of edges).

Modifying Functions (Primitives)

void	D.set_point ( Vertex* v, Point p)
		sets the point of $$v to $$p.
void	D.set_point ( Halfedge* h, Point p)
		sets the point of the vertex incident to $$h to $$p.
void	D.set_vertex_halfedge ( Vertex* v, Halfedge* g)
		sets the incident halfedge of $$v to $$g.
void	D.set_vertex_halfedge ( Halfedge* h)
		sets the incident halfedge of the vertex incident to $$h to $$h.
void	D.set_vertex ( Halfedge* h, Vertex* v)
		sets the incident vertex of $$h to $$v.
void	D.set_prev ( Halfedge* h, Halfedge* g)
		sets the previous link of $$h to $$g.
void	D.set_facet ( Halfedge* h, Facet* f)
		sets the incident facet of $$h to $$f.
void	D.set_facet_halfedge ( Facet* f, Halfedge* g)
		sets the incident halfedge of $$f to $$g.
void	D.set_facet_halfedge ( Halfedge* h)
		sets the incident halfedge of the facet incident to $$h to $$h.

Miscellaneous

bool	D.is_valid ( HDS hds, bool verbose = false, int level = 0)
		returns true if the halfedge data structure hds is valid with respect to the level value. If verbose is true, statistics are printed to cerr. A halfedge data structure has no definition of validness of its own, but a useful set of tests is defined with the following levels: Level 0: The number of halfedges is even. All pointers except the facet pointer for border halfedges are unequal to NULL. For all halfedges $$h: The opposite halfedge is different from $$h and the opposite of the opposite is equal to $$h. The next of the previous halfedge is equal to $$h. For all vertices $$v: the incident vertex of the incident halfedge of $$v is equal to $$v. The halfedges around $$v starting with the incident halfedge of $$v form a cycle. For all facets $$f: the incident facet of the incident halfedge of $$f is equal to $$f. The halfedges around $$f starting with the incident halfedge of $$f form a cycle. Some checks that redundancies among internal variables holds, e.g. that the iterators enumerate as many items as the related size value indicates. Level 1: All tests of level 0. For all halfedges $$h: The incident vertex of $$h is equal to the incident vertex of the opposite of the next halfedge. The incident facet of $$h is equal to the incident facet of the next halfedge. Level 2: All tests of level 1. The sum of all halfedges that can be reached through the vertices must be equal to the number of all halfedges, i.e. all halfedges incident to a vertex must form a single cycle. Level 3: All tests of level 2. The sum of all halfedges that can be reached through the facets must be equal to the number of all halfedges, i.e. all halfedges surrounding a facet must form a single cycle (no holes in facets). Level 4: All tests of level 3 and normalized_border_is_valid.
bool	D.normalized_border_is_valid ( HDS hds, bool verbose = false)
		returns true if the border halfedges are in normalized representation, which is when enumerating all halfedges with the iterator: The non-border edges precede the border edges. For border edges, the second halfedge is a border halfedge. (The first halfedge may or may not be a border halfedge.) The halfedge iterator border_halfedges_begin() denotes the first border edge. If verbose is true, statistics are printed to cerr.