This concept defines the minimal set of geometric predicates and
operations needed to compute the envelope of a set of arbitrary
surfaces in ℝ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.
|
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.
|
|
|
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.
|
|
|
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.
|
|
|
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 s1(p) and s2(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 s1 and s2, and that the surfaces do not intersect over
c. The functor should therefore return the comparison result of
s1(p') and s2(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
s1(p) and s2(p) for some planar point p ∈ ℝ2.
This operator is required iff the category tag Has_boundary_category
is defined as Tag_true.
|
|
|
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.
|
|
|
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.
|
