CGAL 4.14  Intersecting Sequences of dD Isooriented Boxes

The function box_intersection_all_pairs_d()
computes the pairwise intersecting boxes between two sequences of isooriented boxes in arbitrary dimension.
It does so by comparing all possible pairs of boxes and is thus inferior to the fast box_intersection_d()
algorithm.
The sequences of boxes are given with two forward iterator ranges. The sequences are not modified. For each intersecting pair of boxes a callback
function object is called with the two intersecting boxes as argument; the first argument is a box from the first sequence, the second argument a box from the second sequence.
The algorithm is interface compatible with the box_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 isooriented box is defined as the Cartesian product of \( d\) intervals. We call the box halfopen if the \( d\) intervals \( \{ [lo_i,hi_i) \,\, 0 \leq i < d\}\) are halfopen 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 zerowidth boxes and they can intersect at their boundaries, while nonempty halfopen boxes always have a positive volume and they only intersect iff their interiors overlap. The distinction between closed or halfopen 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
.
In addition, a box has a unique id
number. Boxes with equal id
number are not reported since they obviously intersect trivially.
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.
An important special application of this algorithm is the test for selfintersections where the second box sequence is an identical copy of the first sequence including the preserved id
number. We offer a specialized implementation box_self_intersection_all_pairs_d()
for this application.
Requirements
ForwardIterator1
, and \( \ldots\) 2
, must meet the requirements of ForwardIterator
and both value types must be the same. We call this 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_self_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(nm)\) where \( n\) is the size of the first sequence and \( m\) is the size of the second sequence.
Functions  
template<class ForwardIterator1 , class ForwardIterator2 , class Callback >  
void  CGAL::box_intersection_all_pairs_d (ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, 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 ForwardIterator1 .  
template<class ForwardIterator1 , class ForwardIterator2 , class Callback , class BoxTraits >  
void  CGAL::box_intersection_all_pairs_d (ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, Callback callback, BoxTraits box_traits, CGAL::Box_intersection_d::Topology topology=CGAL::Box_intersection_d::CLOSED) 
Invocation with custom box traits.  