CGAL 5.0 - 3D Envelopes
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>

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 ()

## ◆ 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

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

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

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

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

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.