The function box_intersection_d computes the pairwise intersecting boxes between two sequences of isooriented boxes in arbitrary dimension. The sequences of boxes are given with two randomaccess 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 $$ddimensional 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 i < d} are halfopen intervals, and we call the box closed if the $$d intervals $${ [lo_{i},hi_{i}]  0 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, CGAL::Box_intersection_d::HALF_OPEN and CGAL::Box_intersection_d::CLOSED.
In addition, a box has an unique idnumber. 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 idnumber 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 idnumber. Note that this implies that the address of the box is not sufficient for the idnumber 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 CGAL::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 CGAL::Box_intersection_d::COMPLETE and CGAL::Box_intersection_d::BIPARTITE.
#include <CGAL/box_intersection_d.h>
 

 
Invocation of box intersection with default box traits CGAL::Box_intersection_d::Box_traits_d<Box_handle>, where Box_handle corresponds to the iterator value type of RandomAccessIterator1.  
 

 
Invocation with custom box traits. 
CGAL::box_self_intersection_d
CGAL::box_intersection_all_pairs_d
CGAL::Box_intersection_d::Box_traits_d<BoxHandle>
BoxIntersectionBox_d
BoxIntersectionTraits_d
The implemented algorithm is described in [ZE02] 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 segmenttree algorithm to the twowayscan algorithm, see [ZE02] for the details.
The streamed segmenttree algorithm needs $$O(n log$$^{d} (n) + k) worstcase 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 twowayscan algorithm needs $$O(n log$$(n) + l) worstcase 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 twowayscan 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 segmenttree 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 [ZE02] gives optimal cutoffs in the thousands. Anyway, for optimal runtime some experiments to compare different cutoff parameters are recommended. See also Section .
The box implementation provided with CGAL::Box_intersection_d::Box_d<double,2> has a special constructor for the CGAL bounding box type CGAL::Bbox_2 (and similar for dimension 3). We use this in the example to create $$3 × 3 boxes in a grid layout. Additionally we pick the center box and the box in the upperright corner as our second box sequence query.
The default policy of the box type implements the idnumber with an explicit counter in the boxes, which is the default choice since it always works. We use the idnumber 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 upperright quadrant.
// file: examples/Box_intersection_d/minimal.C #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; }