CGAL 4.14  Intersecting Sequences of dD Isooriented Boxes

The function box_self_intersection_d()
computes the pairwise intersecting boxes in a sequence of isooriented boxes in arbitrary dimension.
The sequence of boxes is given with as a randomaccess iterator range 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 sequence, the second argument is a copy of a box from the sequence. The performance of the algorithm can be tuned with a cutoff
parameter, see the implementation section of the box_intersection_d()
function.
The algorithm creates a second copy of the boxes and 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 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 \leq i < d\}\) are halfopen 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 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, 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 of equal id
number are not reported as intersecting pairs since they are always intersecting trivially.
id
number based on the address of the box is not acceptable if boxes are copied by value and one must either pass boxes by pointer or use another type of box id
number such as ID_EXPLICIT
.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.
Requirements
RandomAccessIterator
must be a mutable randomaccess iterator. We call its 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
. Box_handle
must be a model of the Assignable
concept. 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_all_pairs_d()
CGAL::Box_intersection_d::Box_traits_d<BoxHandle>
BoxIntersectionBox_d
BoxIntersectionTraits_d
Implementation
See the implementation section of the box_intersection_d()
function.
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.
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 20 pairwise intersections, but the order in which they are reported is nonintuitive.
File Box_intersection_d/minimal_self.cpp
Functions  
template<class RandomAccessIterator , class Callback >  
void  CGAL::box_self_intersection_d (RandomAccessIterator begin, RandomAccessIterator end, Callback callback, std::ptrdiff_t cutoff=10, 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 RandomAccessIterator .  
template<class RandomAccessIterator , class Callback , class BoxTraits >  
void  CGAL::box_self_intersection_d (RandomAccessIterator begin, RandomAccessIterator end, Callback callback, BoxTraits box_traits, std::ptrdiff_t cutoff=10, CGAL::Box_intersection_d::Topology topology=CGAL::Box_intersection_d::CLOSED) 
Invocation with custom box traits.  