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

##

The function `box_self_intersection_d()` computes the pairwise intersecting boxes in a sequence of iso-oriented boxes in arbitrary dimension.

The sequence of boxes is given with as a random-access 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 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. This self-intersection function creates internally a second copy of the box sequence. The copying has to preserve the `id`-number of boxes. Note that this implies that the address of the box is not sufficient for the `id`-number if boxes are copied by value. Boxes of equal `id`-number are not reported as intersecting pairs since they are always intersecting 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.

Requirements

- `RandomAccessIterator` must be a mutable random-access 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`.
- 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_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 non-intuitive.

File Box_intersection_d/minimal_self.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
void callback( const Box& a, const Box& b ) {
std::cout << "box " << a.id() << " intersects box " << b.id() << std::endl;
}
int main() {
CGAL::box_self_intersection_d( boxes, boxes+9, callback);
return 0;
}

## 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.