CGAL 5.4.4  2D Envelopes

This concept defines the representation of an envelope diagram of a set of planar curve. The envelope diagram is a subdivision of the \( x\)axis into 0dimensional cells (vertices) and 1dimensional cells (edges), such that the identity of the curves that induce the lower envelope (or the upper envelope) over each cell is fixed.
A vertex in an envelope diagram is therefore associated with a point on the envelope, and corresponds to either a curve endpoint or to an intersection point of two (or more) curves. Therefore each vertex is associated with a set of \( x\)monotone curves that induce the envelope over this point. Each vertex is incident to two edges, one lying to its left and the other to its right.
An edge in the envelope diagram represents a continuous portion of the \( x\)axis, and is associated with a (possibly empty) set of curves that induce the envelope over this portion of the \( x\)axis. An edge may be bounded by two vertices, one to its left and the other to its right. However, the diagram contains two unbounded edges, its leftmost edge, representing the interval \( (\infty, x_l)\), and its rightmost edge, representing the interval \( (x_r, \infty)\), where \( x_l\) and \( x_r\) are the \( x\)coodinates of the leftmost and the rightmost vertices in the diagram, respectively. Note that a diagram may contain no vertices at all, in which case it comprises a single edge.
Note that any model of the EnvelopeDiagram_1
concept must define a geometric traits class, which in turn defines the Point_2
and X_monotone_curve_2
types defined with the diagram features.
Types  
typedef unspecified_type  Traits_2 
the geometric traits class.  
typedef Traits_2::Point_2  Point_2 
the point type.  
typedef Traits_2::X_monotone_curve_2  X_monotone_curve_2 
the \( x\)monotone curve type.  
typedef unspecified_type  Size 
the size type (convertible to size_t ).  
typedef unspecified_type  Curve_const_iterator 
an iterator for the \( x\)monotone curves that induce a diagram feature, with value type X_monotone_curve_2 .  
typedef unspecified_type  Vertex 
the vertex type, a model of the concept EnvelopeDiagramVertex .  
typedef unspecified_type  Edge 
the edge type, a model of the concept EnvelopeDiagramEdge .  
typedef unspecified_type  Vertex_handle 
a handle to a diagram vertex.  
typedef unspecified_type  Vertex_const_handle 
a nonmutable handle to a diagram vertex.  
typedef unspecified_type  Edge_handle 
a handle to a diagram edge.  
typedef unspecified_type  Edge_const_handle 
a nonmutable handle to a diagram edge.  
Creation  
EnvelopeDiagram_1 ()  
constructs an empty diagram containing one unbounded edge, which corresponds to the entire plane and has no \( x\)monotone curves that are associated with it.  
Envelope_diagram_1 (const Self &other)  
copy constructor.  
Access Functions  
Edge_const_handle  leftmost () const 
returns the leftmost edge of the diagram (a nonconst version is also available).  
Edge_const_handle  rightmost () const 
returns the rightmost edge of the diagram (a nonconst version is also available).  
Modifiers  
void  set_leftmost (Edge_const_handle e) 
sets the leftmost edge of the diagram to be e .  
void  set_rightmost (Edge_const_handle e) 
sets the rightmost edge of the diagram to be e .  
Vertex_handle  new_vertex (const Point_2 &p) 
creates a new diagram vertex, associated with the point p .  
Edge_handle  new_edge () 
creates a new diagram edge.  
void  delete_vertex (Vertex_handle v) 
deletes the given vertex v .  
void  delete_edge (Edge_handle e) 
deletes the given edge e .  