CGAL 5.1.2 - Intersecting Sequences of dD Iso-oriented Boxes
|
The function box_self_intersection_all_pairs_d()
computes the pairwise intersecting boxes in a sequence of iso-oriented boxes in arbitrary dimension.
It does so by comparing all possible pairs of boxes and is thus inferior to the fast box_self_intersection_d()
algorithm.
The sequence of boxes is given with a forward iterator range. The sequence is not modified. For each intersecting pair of boxes a callback
function object is called with the two intersecting boxes as argument.
The algorithm is interface compatible with the box_self_intersection_d()
function. Similarly, we call the value_type
of the iterators the box handle, which is either our box type or a pointer type to our box type.
A \( d\)-dimensional iso-oriented box is defined as the Cartesian product of \( d\) intervals. We call the box half-open if the \( d\) intervals \( \{ [lo_i,hi_i) \,|\, 0 \leq i < d\}\) are half-open intervals, and we call the box closed if the \( d\) intervals \( \{ [lo_i,hi_i] \,|\, 0 \leq i < d\}\) are closed intervals. Note that closed boxes support zero-width boxes and they can intersect at their boundaries, while non-empty half-open boxes always have a positive volume and they only intersect iff their interiors overlap. The distinction between closed or half-open boxes does not require a different representation of boxes, just a different interpretation when comparing boxes, which is selected with the topology
parameter and its two values, Box_intersection_d::HALF_OPEN
and Box_intersection_d::CLOSED
.
The algorithm uses a traits class of the BoxIntersectionTraits_d
concept to access the boxes. A default traits class is provided that assumes that the box type is a model of the BoxIntersectionBox_d
concept and that the box handle, i.e., the iterators value type, is identical to the box type or a pointer to the box type.
Requirements
ForwardIter
must meet the requirements of ForwardIterator
. We call its value type Box_handle
in the following. Callback
must be of the BinaryFunction
concept. The Box_handle
must be convertible to both argument types. The return type is not used and can be void
. Box_handle
must be a model of the Assignable
concept. Box_handle
must be a class type T
or a pointer to a class type T
, where T
must be a model of the BoxIntersectionBox_d
concept. In both cases, the default box traits specializes to a suitable implementation. BoxTraits
must be of the BoxIntersectionTraits_d
concept. CGAL::box_intersection_d()
CGAL::box_self_intersection_d()
CGAL::box_intersection_all_pairs_d()
CGAL::Box_intersection_d::Box_traits_d<BoxHandle>
BoxIntersectionBox_d
BoxIntersectionTraits_d
Implementation
The algorithm is trivially testing all pairs and runs therefore in time \( O(n^2)\) where \( n\) is the size of the input sequence. This algorithm does not use the id-number of the boxes.
Functions | |
template<class ForwardIter , class Callback > | |
void | CGAL::box_self_intersection_all_pairs_d (ForwardIter begin, ForwardIter end, Callback callback, CGAL::Box_intersection_d::Topology topology=CGAL::Box_intersection_d::CLOSED) |
Invocation of box intersection with default box traits Box_intersection_d::Box_traits_d<Box_handle> , where Box_handle corresponds to the iterator value type of ForwardIter . | |
template<class ForwardIter , class Callback , class BoxTraits > | |
void | CGAL::box_self_intersection_all_pairs_d (ForwardIter begin, ForwardIter end, Callback callback, BoxTraits box_traits, CGAL::Box_intersection_d::Topology topology=CGAL::Box_intersection_d::CLOSED) |
Invocation with custom box traits. | |