\( \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.11.3 - 3D Envelopes
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
EnvelopeTraits_3 Concept Reference
Concepts

Definition

This concept defines the minimal set of geometric predicates and operations needed to compute the envelope of a set of arbitrary surfaces in \( \mathbb{R}^3\). It refines the ArrangementXMonotoneTraits_2 concept. In addition to the Point_2 and X_monotone_curve_2 types and the Has_boundary_category category tag listed in the base concept, it also lists the Surface_3 and Xy_monotone_surface_3 types, which represent arbitrary surfaces and \( xy\)-monotone surfaces, respectively, and some constructions and predicates on these types. Note however, that these operations usually involve the projection of 3D objects onto the \( xy\)-plane.

Refines:
ArrangementXMonotoneTraits_2
Has Models:

CGAL::Env_triangle_traits_3<Kernel>

CGAL::Env_sphere_traits_3<ConicTraits>

CGAL::Env_plane_traits_3<Kernel>

CGAL::Env_surface_data_traits_3<Traits,XyData,SData,Cnv>

Types

typedef unspecified_type Surface_3
 represents an arbitrary surface in \( \mathbb{R}^3\).
 
typedef unspecified_type Xy_monotone_surface_3
 represents a weakly \( xy\)-monotone surface in \( \mathbb{R}^3\).
 

Functor Types

typedef unspecified_type Make_xy_monotone_3
 provides the operator (templated by the OutputIterator type) : More...
 
typedef unspecified_type Construct_projected_boundary_2
 provides the operator (templated by the OutputIterator type) : More...
 
typedef unspecified_type Construct_projected_intersections_2
 provides the operator (templated by the OutputIterator type) : More...
 
typedef unspecified_type Compare_z_at_xy_3
 provides the operators : More...
 
typedef unspecified_type Compare_z_at_xy_above_3
 provides the operator : More...
 
typedef unspecified_type Compare_z_at_xy_below_3
 provides the operator : More...
 

Creation

 EnvelopeTraits_3 ()
 default constructor.
 
 EnvelopeTraits_3 (EnvelopeTraits_3 other)
 copy constructor.
 
EnvelopeTraits_3 operator= (other)
 assignment operator.
 

Accessing Functor Objects

Make_xy_monotone_3 make_xy_monotone_3_object ()
 
Construct_projected_boundary_2 construct_projected_boundary_2_object ()
 
Construct_projected_intersections_2 construct_projected_intersections_2_object ()
 
Compare_z_at_xy_3 compare_z_at_xy_3_object ()
 
Compare_z_at_xy_above_3 compare_z_at_xy_above_3_object ()
 
Compare_z_at_xy_below_3 compare_z_at_xy_below_3_object ()
 

Member Typedef Documentation

typedef unspecified_type EnvelopeTraits_3::Compare_z_at_xy_3

provides the operators :

  • Comparison_result operator() (Point_2 p, Xy_monotone_surface_3 s1, Xy_monotone_surface_3 s2)
    which determines the relative \( z\)-order of the two given \( xy\)-monotone surfaces at the \( xy\)-coordinates of the point p, with the precondition that both surfaces are defined over p. Namely, it returns the comparison result of \( s_1(p)\) and \( s_2(p)\).
  • Comparison_result operator() (X_monotone_curve_2 c, Xy_monotone_surface_3 s1, Xy_monotone_surface_3 s2)
    which determines the relative \( z\)-order of the two given \( xy\)-monotone surfaces over the interior of a given \( x\)-monotone curve \( c\), with the precondition that \( c\) is fully contained in the \( xy\)-definition range of both \( s_1\) and \( s_2\), and that the surfaces do not intersect over \( c\). The functor should therefore return the comparison result of \( s_1(p')\) and \( s_2(p')\) for some point \( p'\) in the interior of \( c\).
  • Comparison_result operator() (Xy_monotone_surface_3 s1, Xy_monotone_surface_3 s2)
    which determines the relative \( z\)-order of the two given unbounded \( xy\)-monotone surfaces, which are defined over the entire \( xy\)-plane and have no boundary, with the precondition that the surfaces do not intersect at all. The functor should therefore return the comparison result of \( s_1(p)\) and \( s_2(p)\) for some planar point \( p \in\mathbb{R}^2\). This operator is required iff the category tag Has_boundary_category is defined as Tag_true.
typedef unspecified_type EnvelopeTraits_3::Compare_z_at_xy_above_3

provides the operator :

  • Comparison_result operator() (X_monotone_curve_2 c, Xy_monotone_surface_3 s1, Xy_monotone_surface_3 s2)
    which determines the relative \( z\)-order of the two given \( xy\)-monotone surfaces immediately above their projected intersection curve \( c\) (a planar point \( p\) is above an \( x\)-monotone curve \( c\) if it is in the \( x\)-range of \( c\), and lies to its left when the curve is traversed from its \( xy\)-lexicographically smaller endpoint to its larger endpoint). We have the precondition that both surfaces are defined "above" \( c\), and their relative \( z\)-order is the same for some small enough neighborhood of points above \( c\).
typedef unspecified_type EnvelopeTraits_3::Compare_z_at_xy_below_3

provides the operator :

  • Comparison_result operator() (X_monotone_curve_2 c, Xy_monotone_surface_3 s1, Xy_monotone_surface_3 s2)
    which determines the relative \( z\)-order of the two given \( xy\)-monotone surfaces immediately below their projected intersection curve \( c\) (a planar point \( p\) is below an \( x\)-monotone curve \( c\) if it is in the \( x\)-range of \( c\), and lies to its right when the curve is traversed from its \( xy\)-lexicographically smaller endpoint to its larger endpoint). We have the precondition that both surfaces are defined "below" \( c\), and their relative \( z\)-order is the same for some small enough neighborhood of points below \( c\).
typedef unspecified_type EnvelopeTraits_3::Construct_projected_boundary_2

provides the operator (templated by the OutputIterator type) :

  • OutputIterator operator() (Xy_monotone_surface_3 s, OutputIterator oi)
    which computes all planar \( x\)-monotone curves and possibly isolated planar points that form the projection of the boundary of the given \( xy\)-monotone surface \( s\) onto the \( xy\)-plane, and inserts them into the output iterator. The value-type of OutputIterator is Object, where Object wraps either a Point_2, or a pair<X_monotone_curve_2, Oriented_side>. In the former case, the object represents an isolated point of the projected boundary. In the latter, more general, case the object represents an \( x\)-monotone boundary curve along with an enumeration value which is either ON_NEGATIVE_SIDE or ON_POSITIVE_SIDE, indicating whether whether the projection of the surface onto the \( xy\)-plane lies below or above this \( x\)-monotone curve, respectively. In degenerate case, namely when the surface itself is vertical, and its projection onto the plane is \( 1\)-dimensional, the Oriented_side value is ON_ORIENTED_BOUNDARY. The operator returns a past-the-end iterator for the output sequence.
typedef unspecified_type EnvelopeTraits_3::Construct_projected_intersections_2

provides the operator (templated by the OutputIterator type) :

  • OutputIterator operator() (Xy_monotone_surface_3 s1, Xy_monotone_surface_3 s2, OutputIterator oi)
    which computes the projection of the intersections of the \( xy\)-monotone surfaces s1 and s2 onto the \( xy\)-plane, and inserts them into the output iterator. The value-type of OutputIterator is Object, where each Object either wraps a pair<X_monotone_curve_2,Multiplicity> instance, which represents a projected intersection curve with its multiplicity (in case the multiplicity is undefined or not known, it should be set to \( 0\)) or an Point_2 instance, representing the projected image of a degenerate intersection (the projection of an isolated intersection point, or of a vertical intersection curve). The operator returns a past-the-end iterator for the output sequence.
typedef unspecified_type EnvelopeTraits_3::Make_xy_monotone_3

provides the operator (templated by the OutputIterator type) :

  • OutputIterator operator() (Surface_3 S, bool is_lower, OutputIterator oi)
    which subdivides the given surface S into \( xy\)-monotone parts and inserts them into the output iterator. The value of is_lower indicates whether we compute the lower or the upper envelope, so that \( xy\)-monotone surfaces that are irrelevant to the lower-envelope (resp. upper-envelope) computation may be discarded. The value-type of OutputIterator is Xy_monotone_surface_3. The operator returns a past-the-end iterator for the output sequence.