CGAL::box_intersection_d()

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.

Warning

The two sequences of boxes passed to box_intersection_d() can be ranges created from the same container, but these ranges must not contain any common element.

Requirements

• RandomAccessIterator1, and \( \ldots\) 2, must meet the requirements of RandomAccessIterator 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 .

Concurrency

The first template parameter of the function enables to choose whether the algorithm is to be run in parallel, if CGAL::Parallel_tag is specified and CGAL has been linked with the Intel TBB library, or sequentially, if CGAL::Sequential_tag - the default value - is specified. The parallelization of the algorithm is based on a divide-and-conquer approach: the two ranges are split in a number of smaller ranges, and all combinations of subranges are treated in parallel. It is thus recommended to use ranges of pointers to bounding boxes, to keep these copies light.

Warning

The parallel mode comes with a small overhead due to the duplication and splitting of the input ranges. It is an improvement for almost all inputs, but not all. A configuration where the two ranges are small and entirely disjoint might result in a slightly worse runtime when using the parallel version. Users should benchmark both versions to verify that their data does not fall in this (small) set of inputs.

When using the parallel mode, the callback function must be threadsafe.

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 ConcurrencyTag = CGAL::Sequential_tag, 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 ConcurrencyTag = CGAL::Sequential_tag, 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.