\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.13 - 3D Envelopes
CGAL::Envelope_diagram_2< EnvTraits > Class Template Reference

#include <CGAL/envelope_3.h>

Inherits from

CGAL::Arrangement_2< EnvTraits >.


The class-template Envelope_diagram_2 represents the minimization diagram that corresponds to the lower envelope of a set of curves, or the maximization diagram that corresponds to their upper envelope.

It is parameterized by a traits class that must be a model of the EnvelopeTraits_3 concept, and is basically a planar arrangement of \( x\)-monotone curves, as defined by this traits class. These \( x\)-monotone curves are the projections of boundary curves of \( xy\)-monotone surfaces, or the intersection curves between such surfaces, onto the \( xy\)-plane. Thus, it is possible to traverse the envelope diagram using the methods inherited from the Arrangement_2 class.

The envelope diagram extends the arrangement features (namely the vertices, halfedges, and faces), such that each feature stores a container of originators - namely, the \( xy\)-monotone surfaces (instances of the type EnvTraits::Xy_monotone_surface_3) that induce the lower envelope (or the upper envelope, in case of a maximization diagram) over this feature. The envelope diagram provides access methods to these originators.

Envelope_3/envelope_planes.cpp, Envelope_3/envelope_spheres.cpp, and Envelope_3/envelope_triangles.cpp.


class  Face
class  Halfedge
class  Vertex


typedef Envelope_diagram_2< EnvTraits > Self
typedef Arrangement_2< EnvTraits > Base
typedef unspecified_type Surface_const_iterator
 an iterator for the \( xy\)-monotone surfaces that induce a diagram feature. More...


 Envelope_diagram_2 ()
 constructs an empty diagram containing one unbounded face, which corresponds to the entire plane and has no originators.
 Envelope_diagram_2 (const Self &other)
 copy constructor.
 Envelope_diagram_2 (EnvTraits *traits)
 constructs an empty diagram that uses the given traits instance for performing the geometric predicates.

Additional Inherited Members

- Public Types inherited from CGAL::Arrangement_2< EnvTraits >
typedef Arrangement_2< Traits_2, Dcel > Self
typedef Traits Traits_2
typedef Traits_2::Point_2 Point_2
typedef Traits_2::X_monotone_curve_2 X_monotone_curve_2
typedef Dcel::Size Size
typedef unspecified_type Vertex_handle
typedef unspecified_type Halfedge_handle
typedef unspecified_type Face_handle
typedef unspecified_type Vertex_iterator
typedef unspecified_type Halfedge_iterator
typedef unspecified_type Edge_iterator
typedef unspecified_type Face_iterator
typedef unspecified_type Unbounded_face_iterator
typedef unspecified_type Halfedge_around_vertex_circulator
typedef unspecified_type Ccb_halfedge_circulator
typedef unspecified_type Hole_iterator
typedef unspecified_type Isolated_vertex_iterator
- Public Member Functions inherited from CGAL::Arrangement_2< EnvTraits >
 Arrangement_2 ()
 Arrangement_2 (const Self &other)
 Arrangement_2 (const Traits_2 *traits)
Selfoperator= (other)
void assign (const Self &other)
void clear ()
Traits_2get_traits ()
bool is_empty () const
Size number_of_vertices () const
Size number_of_isolated_vertices () const
Vertex_iterator vertices_begin ()
Vertex_iterator vertices_end ()
unspecified_type vertex_handles ()
Size number_of_vertices_at_infinity () const
Size number_of_halfedges () const
Halfedge_iterator halfedges_begin ()
Halfedge_iterator halfedges_end ()
unspecified_type halfedge_handles ()
Size number_of_edges () const
Edge_iterator edges_begin ()
Edge_iterator edges_end ()
unspecified_type edge_handles ()
Face_handle unbounded_face ()
Size number_of_faces () const
Face_iterator faces_begin ()
Face_iterator faces_end ()
unspecified_type face_handles ()
Size number_of_unbounded_faces () const
Unbounded_face_iterator unbounded_faces_begin ()
Unbounded_face_iterator unbounded_faces_end ()
Face_handle fictitious_face ()
Vertex_handle non_const_handle (Vertex_const_handle v)
Halfedge_handle non_const_handle (Halfedge_const_handle e)
Face_handle non_const_handle (Face_const_handle f)
Vertex_handle insert_in_face_interior (const Point_2 &p, Face_handle f)
Halfedge_handle insert_in_face_interior (const X_monotone_curve_2 &c, Face_handle f)
Halfedge_handle insert_in_face_interior (const X_monotone_curve_2 &c, Halfedge_handle fict_pred1, Halfedge_handle fict_pred2=Halfedge_handle())
Halfedge_handle insert_from_left_vertex (const X_monotone_curve_2 &c, Vertex_handle v)
Halfedge_handle insert_from_left_vertex (const X_monotone_curve_2 &c, Halfedge_handle pred)
Halfedge_handle insert_from_left_vertex (const X_monotone_curve_2 &c, Halfedge_handle pred, Halfedge_handle fict_pred)
Halfedge_handle insert_from_right_vertex (const X_monotone_curve_2 &c, Vertex_handle v)
Halfedge_handle insert_from_right_vertex (const X_monotone_curve_2 &c, Halfedge_handle pred)
Halfedge_handle insert_from_right_vertex (const X_monotone_curve_2 &c, Halfedge_handle pred, Halfedge_handle fict_pred)
Halfedge_handle insert_at_vertices (const X_monotone_curve_2 &c, Vertex_handle v1, Vertex_handle v2)
Halfedge_handle insert_at_vertices (const X_monotone_curve_2 &c, Halfedge_handle pred1, Vertex_handle v2)
Halfedge_handle insert_at_vertices (const X_monotone_curve_2 &c, Halfedge_handle pred1, Halfedge_handle pred2)
Vertex_handle modify_vertex (Vertex_handle v, const Point_2 &p)
Face_handle remove_isolated_vertex (Vertex_handle v)
Halfedge_handle modify_edge (Halfedge_handle e, const X_monotone_curve_2 &c)
Halfedge_handle split_edge (Halfedge_handle e, const X_monotone_curve_2 &c1, const X_monotone_curve_2 &c2)
Halfedge_handle merge_edge (Halfedge_handle e1, Halfedge_handle e2, const X_monotone_curve_2 &c)
Face_handle remove_edge (Halfedge_handle e, bool remove_source=true, bool remove_target=true)
bool is_valid () const

Member Typedef Documentation

◆ Surface_const_iterator

template<typename EnvTraits >
typedef unspecified_type CGAL::Envelope_diagram_2< EnvTraits >::Surface_const_iterator

an iterator for the \( xy\)-monotone surfaces that induce a diagram feature.

Its value-type is EnvTraits::Xy_monotone_surface_3.