CGAL 4.7 - Intersecting Sequences of dD Iso-oriented Boxes: CGAL::box_intersection_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_d()
Intersecting Sequences of dD Iso-oriented Boxes Reference

##

The function `box_intersection_d()` computes the pairwise intersecting boxes between two sequences of iso-oriented boxes in arbitrary dimension.

The sequences of boxes are given with two random-access iterator ranges and will be reordered in the course of the algorithm. 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 performance of the algorithm can be tuned with a `cutoff` parameter, see the implementation section below for more details.

The algorithm reorders the boxes in the course of the algorithm. Now, depending on the size of a box it can be faster to copy the boxes, or to work with pointers to boxes and copy only pointers. We offer automatic support for both options. To simplify the description, let us call the `value_type` of the iterators box handle. The box handle can either be our box type itself or a pointer (or const pointer) to the 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. It is used to order boxes consistently in each dimension even if boxes have identical coordinates. In consequence, the algorithm guarantees that a pair of intersecting boxes is reported only once. 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. Note that this implies that the address of the box is not sufficient for the `id`-number if boxes are copied by value. To ease the use of this special case we offer a simplified version of this function with one iterator range only, which then creates internally the second copy of the boxes, under the name `box_self_intersection_d()`.

In the general case, we distinguish between the bipartite case (the boxes are from different sequences) and the complete case (the boxes are from the same sequence, i.e., the self intersection case). The default is the bipartite case, since the complete case is typically handled with the simplified function call mentioned above. However, the general function call offers the `setting` parameter with the values `Box_intersection_d::COMPLETE` and `Box_intersection_d::BIPARTITE`.

Requirements

- `RandomAccessIterator1`, and \( \ldots\) `2`, must be mutable random-access iterators 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.

See Also
  `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 implemented algorithm is described in [2] as version two. Its performance depends on a `cutoff` parameter. When the size of both iterator ranges drops below the `cutoff` parameter the function switches from the streamed segment-tree algorithm to the two-way-scan algorithm, see [2] for the details.

The streamed segment-tree algorithm needs \( O(n \log^d (n) + k)\) worst-case running time and \( O(n)\) space, where \( n\) is the number of boxes in both input sequences, \( d\) the (constant) dimension of the boxes, and \( k\) the output complexity, i.e., the number of pairwise intersections of the boxes. The two-way-scan algorithm needs \( O(n \log (n) + l)\) worst-case running time and \( O(n)\) space, where \( l\) is the number of pairwise overlapping intervals in one dimensions (the dimension where the algorithm is used instead of the segment tree). Note that \( l\) is not necessarily related to \( k\) and using the two-way-scan algorithm is a heuristic.

Unfortunately, we have no general method to automatically determine an optimal cutoff parameter, since it depends on the used hardware, the runtime ratio between callback runtime and segment-tree runtime, and of course the number of boxes to be checked and their distribution. In cases where the callback runtime is dominant, it may be best to make the threshold parameter small. Otherwise a `cutoff` \( =\sqrt{n}\) can lead to acceptable results. For well distributed boxes the original paper [2] gives optimal cutoffs in the thousands. Anyway, for optimal runtime some experiments to compare different cutoff parameters are recommended. See also Section Runtime Performance .

Example

The box implementation provided with `Box_intersection_d::Box_d<double,2>` has a special constructor for the CGAL bounding box type `Bbox_2` (and similar for dimension 3). We use this in the example to create \( 3 \times 3\) `boxes` in a grid layout. Additionally we pick the center box and the box in the upper-right corner as our second box sequence `query`.

The default policy of the box type implements the `id`-number with an explicit counter in the boxes, which is the default choice since it always works. We use the `id`-number in our callback function to report the result of the intersection algorithm call. The result will be that the first `query` box intersects all nine `boxes` and the second `query` box intersects the four boxes in the upper-right quadrant.

File Box_intersection_d/minimal.cpp

#include <CGAL/box_intersection_d.h>
#include <CGAL/Bbox_2.h>
#include <iostream>
typedef CGAL::Box_intersection_d::Box_d<double,2> Box;
typedef CGAL::Bbox_2 Bbox;
// 9 boxes of a grid
Box boxes[9] = { Bbox( 0,0,1,1), Bbox( 1,0,2,1), Bbox( 2,0,3,1), // low
Bbox( 0,1,1,2), Bbox( 1,1,2,2), Bbox( 2,1,3,2), // middle
Bbox( 0,2,1,3), Bbox( 1,2,2,3), Bbox( 2,2,3,3)};// upper
// 2 selected boxes as query; center and upper right
Box query[2] = { Bbox( 1,1,2,2), Bbox( 2,2,3,3)};
void callback( const Box& a, const Box& b ) {
std::cout << "box " << a.id() << " intersects box " << b.id() << std::endl;
}
int main() {
CGAL::box_intersection_d( boxes, boxes+9, query, query+2, callback);
return 0;
}

## Functions

template<class RandomAccessIterator1 , class RandomAccessIterator2 , class Callback >
void | CGAL::box_intersection_d (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, Callback callback, std::ptrdiff_t cutoff=10, CGAL::Box_intersection_d::Topology topology=CGAL::Box_intersection_d::CLOSED, CGAL::Box_intersection_d::Setting setting=CGAL::Box_intersection_d::BIPARTITE)
| 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 `RandomAccessIterator1`.
template<class RandomAccessIterator1 , class RandomAccessIterator2 , class Callback , class BoxTraits >
void | CGAL::box_intersection_d (RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, Callback callback, BoxTraits box_traits, std::ptrdiff_t cutoff=10, CGAL::Box_intersection_d::Topology topology=CGAL::Box_intersection_d::CLOSED, CGAL::Box_intersection_d::Setting setting=CGAL::Box_intersection_d::BIPARTITE)
| Invocation with custom box traits.