 CGAL 5.1 - Intersecting Sequences of dD Iso-oriented Boxes

The function box_intersection_all_pairs_d() computes the pairwise intersecting boxes between two sequences 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_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 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.

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 self-intersections 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.
• The Box_handle must be a model of the Assignable concept.
• In addition, if the default box traits is used the 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.