CGAL 4.7 - Intersecting Sequences of dD Iso-oriented Boxes: CGAL::box_intersection_all_pairs_d()

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Intersecting Sequences of dD Iso-oriented Boxes

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Functions
CGAL::box_intersection_all_pairs_d()
Intersecting Sequences of dD Iso-oriented Boxes Reference

##

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` for this application.

See Also
  `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.