EnvelopeTraits_3 Concept Reference

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, ArrLinearTraits>

CGAL::Env_sphere_traits_3<ConicTraits>

CGAL::Env_plane_traits_3<Kernel, ArrLinearTraits>

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) :
typedef unspecified_type	Construct_projected_boundary_2
	provides the operator (templated by the OutputIterator type) :
typedef unspecified_type	Construct_projected_intersections_2
	provides the operator (templated by the OutputIterator type) :
typedef unspecified_type	Compare_z_at_xy_3
	provides the operators :
typedef unspecified_type	Compare_z_at_xy_above_3
	provides the operator :
typedef unspecified_type	Compare_z_at_xy_below_3
	provides the operator :

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

Compare_z_at_xy_3

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.

Compare_z_at_xy_above_3

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\).

Compare_z_at_xy_below_3

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\).

Construct_projected_boundary_2

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.

Construct_projected_intersections_2

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.

Make_xy_monotone_3

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.