CGAL 6.2 - Intersecting Sequences of dD Iso-oriented Boxes

Loading...
Searching...
No Matches
User Manual

Authors
  Lutz Kettner, Andreas Meyer, and Afra Zomorodian

# Introduction

Simple questions on geometric primitives, such as intersection and distance computations, can themselves become quite expensive if the primitives are not so simple anymore, for example, three-dimensional triangles and facets of polyhedral surfaces. Thus algorithms operating on these primitives tend to be slow in practice. A common (heuristic) optimization approximates the geometric primitives with their axis-aligned bounding boxes, runs a suitable modification of the algorithm on the boxes, and whenever a pair of boxes has an interesting interaction Boxes represent volumes or point-sets. So, intersection means intersection of the point-set enclosed by the box and not only intersection of the boundary, of course., only then the exact answer is computed on the complicated geometric primitives contained in the boxes.

We provide an efficient algorithm [2] for finding all intersecting pairs for large numbers of iso-oriented boxes, i.e., typically these will be such bounding boxes of more complicated geometries. One immediate application of this algorithm is the detection of all intersections (and self-intersections) for polyhedral surfaces, i.e., applying the algorithm on a large set of triangles in space, we give an example program later in this chapter. Not so obvious applications are proximity queries and distance computations among such surfaces, see Section Example for Point Proximity Search with a Custom Traits Class for an example and [2] for more details.

# Definition

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 and half-open boxes does not require a different representation of boxes, just a different interpretation when comparing boxes, which is selected with the two possible values for the `topology` parameter:

- `Box_intersection_d::HALF_OPEN` and
- `Box_intersection_d::CLOSED`.

The number type of the interval boundaries must be one of the built-in types `int`, `unsigned int`, `double` or `float`.

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. Note that boxes with equal `id`-number are not reported since they obviously intersect trivially.

The box intersection algorithm comes in two flavors: One algorithm works on a single sequence of boxes and computes all pairwise intersections, which is called the complete case, and used, for example, in the self-intersection test. The other algorithm works on two sequences of boxes and computes the pairwise intersections between boxes from the first sequence with boxes from the second sequence, which is called the bipartite case. For each pairwise intersection found a callback function is called with two arguments; the first argument is a box from the first sequence and the second argument a box from the second sequence. In the complete case, the second argument is a box from an internal copy of the first sequence.

# Software Design

The box intersection algorithm is implemented as a family of generic functions; the functions for the complete case accept one iterator range, and the functions for the bipartite case accept two iterator ranges. The callback function for reporting the intersecting pairs is provided as a template parameter of the `BinaryFunction` concept. The two principle function calls utilizing all default arguments look as follows:

#include <CGAL/box_intersection_d.h>
template< class RandomAccessIterator, class Callback >
void box_intersection_d(RandomAccessIterator begin,
RandomAccessIterator end,
Callback callback);
template< class RandomAccessIterator1,
class RandomAccessIterator2,
class Callback >
void box_intersection_d(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
Callback callback);
RandomAccessIterator
CGAL::box_intersection_d
void 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_1,...

Additional parameters to the functions calls are a cutoff value to adjust performance trade-offs, and a topology parameter selecting between topologically closed boxes (the default) and topologically half-open boxes.

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 iterator ranges box handle. The box handle can either be our box type itself or a pointer (or const pointer) to the box type; these choices represent both options from above.

In general, the algorithms treat the box type as opaque type and just assume that they are models of the `Assignable` concept, so that the algorithms can modify the input sequences and reorder the boxes. The access to the box dimension and box coordinates is mediated with a traits class of the `BoxIntersectionTraits_d` concept. 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 (see the previous paragraph for the value versus pointer nature of the box handle).

Three implementations of iso-oriented boxes are provided; `Box_intersection_d::Box_d` as a plain box, and `Box_intersection_d::Box_with_info_d` and `Box_intersection_d::Box_with_handle_d` as a box plus respectively an info or a handle that can be used to point to the full geometry that is approximated by the box. Their implementations have template parameters for the number type used for the interval bounds, for the fixed dimension of the box, and for a policy class [1] selecting among several solutions for providing the `id`-number.

The function signatures for the bipartite case look as follows. The signatures for the complete case with the `box_self_intersection_d()` function look the same except for the single iterator range.

#include CGAL/box_intersection_d.h
template< class RandomAccessIterator1,
class RandomAccessIterator2,
class Callback >
void box_intersection_d(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
Callback callback, std::ptrdiff_t cutoff = 10,
Box_intersection_d::Topology topology = Box_intersection_d::CLOSED,
Box_intersection_d::Setting setting = Box_intersection_d::BIPARTITE);
template< class RandomAccessIterator1,
class RandomAccessIterator2,
class Callback, class BoxTraits >
void box_intersection_d(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
Callback callback, BoxTraits box_traits,
std::ptrdiff cutoff = 10,
Box_intersection_d::Topology topology = Box_intersection_d::CLOSED,
Box_intersection_d::Setting setting = Box_intersection_d::BIPARTITE);
CGAL::Box_intersection_d::Setting
Setting
Definition: Box_traits_d.h:52
CGAL::Box_intersection_d::Topology
Topology
Definition: Box_traits_d.h:57
CGAL::Box_intersection_d::BIPARTITE
@ BIPARTITE
Definition: Box_traits_d.h:52
CGAL::Box_intersection_d::CLOSED
@ CLOSED
Definition: Box_traits_d.h:57

We provide an example using boxes of different types to detect proximity between points and segments.

Example: Box_intersection_d/boxes_with_different_types.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
#include <CGAL/Box_intersection_d/Box_d.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
typedef CGAL::Box_intersection_d::Box_with_info_d<double,2,Point_2> Point_box;
typedef CGAL::Box_intersection_d::Box_with_info_d<double,2,Segment_2> Segment_box;
// 4 points of a grid
Point_box pts[4] = { Point_box( Point_2(0, 0).bbox(), Point_2(0, 0)),
Point_box( Point_2(0, 1).bbox(), Point_2(0, 1)),
Point_box( Point_2(1, 0).bbox(), Point_2(1, 0)),
Point_box( Point_2(1, 1).bbox(), Point_2(1, 1))};// upper
// 2 segment as query
Segment_2 seg1(Point_2(0.2,-0.2), Point_2(1.2, 0.8));
Segment_2 seg2(Point_2(-0.2,1.3), Point_2(1.2,-0.1));
Segment_box query[2] = { Segment_box(seg1.bbox(), seg1),
Segment_box(seg2.bbox(), seg2)};
void callback( const Point_box& a, const Segment_box& b ) {
std::cout << "box of point " << a.info() << " intersects box of segment " << b.info() << std::endl;
}
int main() {
CGAL::box_intersection_d( pts, pts+4, query, query+2, callback);
return 0;
}
CGAL::Box_intersection_d::Box_with_info_d
Box_with_info_d is a generic iso-oriented bounding box in dimension that stores additionally a varia...
Definition: Box_with_info_d.h:56
CGAL::Exact_predicates_inexact_constructions_kernel
Kernel::Point_2
Kernel::Segment_2
Kernel

# Minimal Example for Intersecting Boxes

The box implementation provided with `Box_intersection_d::Box_d<double,2>` has a dedicated constructor for the CGAL bounding box type `Bbox_2` (similar for dimension 3). We use this in our minimal example to create easily nine two-dimensional `boxes` in a grid layout of \( 3 \times 3\) boxes. 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, but it costs space that could potentially be avoided, see the example in the next section. We use the `id`-number in our callback function to report the result of the intersection algorithm. 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. See Section Example Using the Topology and the Cutoff Parameters for the change of the `topology` parameter and its effect.

Example: Box_intersection_d/minimal.cpp

Show / Hide
#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;
}
CGAL::Bbox_2
CGAL::Box_intersection_d::Box_d
Box_d is a generic iso-oriented bounding box in dimension .
Definition: Box_d.h:56

# Example for Finding Intersecting 3D Triangles

The conventional application of the axis-aligned box intersection algorithm will start from complex geometry, here 3D triangles, approximate them with their bounding box, compute the intersecting pairs of boxes, and check only for those if the original triangles intersect as well.

We start in the `main` function and create ten triangles with endpoints chosen randomly in a cube \( [-1,+1)^3\). We store the triangles in a vector called `triangles`.

Next we create a vector for the bounding boxes of the triangles called `boxes`. For the boxes we choose the type `Box_with_handle_d<double,3,Iterator>` that works nicely together with the CGAL bounding boxes of type `Bbox_3`. In addition, each box stores the iterator to the corresponding triangle.

The default policy of this box type uses for the `id`-number the address of the value of the iterator, i.e., the address of the triangle. This is a good choice that works correctly iff the boxes have unique iterators, i.e., there is a one-to-one mapping between boxes and approximated geometry, which is the case here. It saves us the extra space that was needed for the explicit `id`-number in the previous example.

We run the self intersection algorithm with the `report_inters()` function as callback. This callback reports the intersecting boxes. It uses the `handle` and the global `triangles` vector to calculate the triangle numbers. Then it checks the triangles themselves for intersection and reports if not only the boxes but also the triangles intersect. We take some precautions before the intersection test in order to avoid problems, although unlikely, with degenerate triangles that we might have created with the random process.

This example can be easily extended to test polyhedral surfaces of the `Polyhedron_3` class for (self-) intersections. The main difference are the numerous cases of incidences between triangles in the polyhedral surface that should not be reported as intersections, see the `examples/Polyhedron/polyhedron_self_intersection.cpp` example program in the CGAL distribution.

Example: Box_intersection_d/triangle_self_intersect.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
#include <vector>
#include <fstream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point_3;
typedef Kernel::Triangle_3 Triangle_3;
typedef std::vector<Triangle_3> Triangles;
typedef Triangles::iterator Iterator;
typedef CGAL::Box_intersection_d::Box_with_handle_d<double,3,Iterator> Box;
struct Report {
Triangles* triangles;
Report(Triangles& triangles)
: triangles(&triangles)
{}
// callback functor that reports all truly intersecting triangles
void operator()(const Box& a, const Box& b) const
{
std::cout << "Box " << (a.handle() - triangles->begin()) << " and "
<< (b.handle() - triangles->begin()) << " intersect";
if ( ! a.handle()->is_degenerate() && ! b.handle()->is_degenerate()
&& CGAL::do_intersect( *(a.handle()), *(b.handle()))) {
std::cout << ", and the triangles intersect also";
}
std::cout << '.' << std::endl;
}
};
int main(int argc, char*argv[])
{
std::ifstream in((argc>1)?argv[1]:CGAL::data_file_path("points_3/triangles.xyz"));
Triangles triangles;
Triangle_3 t;
while(in >> t){
triangles.push_back(t);
}
// Create the corresponding vector of bounding boxes
std::vector<Box> boxes;
for ( Iterator i = triangles.begin(); i != triangles.end(); ++i)
boxes.push_back( Box( i->bbox(), i));
// Run the self intersection algorithm with all defaults
CGAL::box_self_intersection_d( boxes.begin(), boxes.end(), Report(triangles));
return 0;
}
CGAL::Box_intersection_d::Box_with_handle_d
Box_with_handle_d is a generic iso-oriented bounding box in dimension that stores additionally a han...
Definition: Box_with_handle_d.h:67
Iterator
Kernel::Point_3
Kernel::Triangle_3
CGAL::box_self_intersection_d
void 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>,...
CGAL::do_intersect
bool do_intersect(Type1< Kernel > obj1, Type2< Kernel > obj2)

# Example for Using Pointers to Boxes

We modify the previous example, finding intersecting 3D triangles, and add an additional vector `ptr` that stores pointers to the bounding boxes, so that the intersection algorithm will work on a sequence of pointers and not on a sequence of boxes. The change just affects the preparation of the additional vector and the call of the box intersection function. The box intersection function (actually its default traits class) detects automatically that the value type of the iterators is a pointer type and not a class type.

// Create the corresponding vector of pointers to bounding boxes
std::vector<Box *> ptr;
for ( std::vector<Box>::iterator i = boxes.begin(); i != boxes.end(); ++i)
ptr.push_back( &*i);
// Run the self intersection algorithm with all defaults on the
// indirect pointers to bounding boxes. Avoids copying the boxes.
CGAL::box_self_intersection_d( ptr.begin(), ptr.end(), report_inters);

In addition, the callback function `report_inters()` needs to be changed to work with pointers to boxes. The full example program looks as follows:

Example: Box_intersection_d/triangle_self_intersect_pointers.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
#include <vector>
#include <fstream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point_3;
typedef Kernel::Triangle_3 Triangle_3;
typedef std::vector<Triangle_3> Triangles;
typedef Triangles::iterator Iterator;
typedef CGAL::Box_intersection_d::Box_with_handle_d<double,3,Iterator> Box;
struct Report {
Triangles* triangles;
Report(Triangles& triangles)
: triangles(&triangles)
{}
// callback functor that reports all truly intersecting triangles
void operator()(const Box* a, const Box* b) const
{
std::cout << "Box " << (a->handle() - triangles->begin()) << " and "
<< (b->handle() - triangles->begin()) << " intersect";
if ( ! a->handle()->is_degenerate() && ! b->handle()->is_degenerate()
&& CGAL::do_intersect( *(a->handle()), *(b->handle()))) {
std::cout << ", and the triangles intersect also";
}
std::cout << '.' << std::endl;
}
};
int main(int argc, char*argv[])
{
std::ifstream in((argc>1)?argv[1]:CGAL::data_file_path("points_3/triangles.xyz"));
Triangles triangles;
Triangle_3 t;
while(in >> t){
triangles.push_back(t);
}
// Create the corresponding vector of bounding boxes
std::vector<Box> boxes;
for ( Iterator i = triangles.begin(); i != triangles.end(); ++i)
boxes.push_back( Box( i->bbox(), i));
// Create the corresponding vector of pointers to bounding boxes
std::vector<Box *> ptr;
for ( std::vector<Box>::iterator i = boxes.begin(); i != boxes.end(); ++i)
ptr.push_back( &*i);
// Run the self intersection algorithm with all defaults on the
// indirect pointers to bounding boxes. Avoids copying the boxes.
CGAL::box_self_intersection_d( ptr.begin(), ptr.end(), Report(triangles));
return 0;
}

A note on performance: The algorithm sorts and partitions the input sequences. It is clearly costly to copy a large box compared to a simple pointer. However, the algorithm benefits from memory locality in the latter stages when it copies the boxes, while the pointers would refer to boxes that become wildly scattered in memory. These two effects, copying costs and memory locality, counteract each other. For small box sizes, i.e., small dimension, memory locality wins and one should work with boxes, while for larger box sizes one should work with pointers. The exact threshold depends on the memory hierarchy (caching) of the hardware platform and the size of the boxes, most notably the type used to represent the box coordinates. A concrete example; on a laptop with an Intel Mobile Pentium4 running at 1.80GHz with 512KB cache and 254MB main memory under Linux this version with pointers was 20% faster than the version above that copies the boxes for 10000 boxes, but the picture reversed for 100000 boxes, where the version above that copies the boxes becomes 300% faster.

Note that switching to the built-in type `float` is supported by the box intersection algorithm, but the interfacing with the CGAL bounding box `Bbox_3` would not be that easy. In particular, just converting from the `double` to the `float` representation incurs rounding that needs to be controlled properly, otherwise the box might shrink and one might miss intersections.

# Example Using the Topology and the Cutoff Parameters

Boxes can be interpreted by the box intersection algorithm as closed or as half-open boxes, see also Section Definition. Closed boxes support zero-width boxes and they can intersect at their boundaries, while half-open boxes always have a positive volume and they only intersect iff their interiors overlap. The choice between closed or half-open boxes is selected with the `topology` parameter and its two values:

- `Box_intersection_d::HALF_OPEN` and
- `Box_intersection_d::CLOSED`.

The example program uses a two-dimensional box with `int` coordinates and `id`-numbers that are by default explicitly stored. We create the same boxes as in the minimal example in Section Minimal Example for Intersecting Boxes. We create a \( 3 \times 3\) grid of `boxes`, and two boxes for the `query` sequence, namely the box at the center and the box from the upper-right corner of the grid.

We write a more involved callback function object `Report` that stores an output iterator and writes the `id`-number of the box in the first argument to the output iterator. We also provide a small helper function `report()` that simplifies the use of the function object.

We call the box intersection algorithm twice; once for the default `topology`, which is the closed box topology, and once for the half-open box topology. We sort the resulting output for better readability and verify its correctness with the `check1` and `check2` data. For the closed box topology, the center box in `query` intersects all `boxes`, and the upper-right box in `query` intersects the four boxes of the upper-right quadrant in `boxes`. Almost all intersections are with the box boundaries, thus, for the half-open topology only one intersection remains per `query` box, namely its corresponding box in `boxes`. So, the output of the algorithm will be:

    0 1 2 3 4 4 5 5 6 7 7 8 8
    4 8

For the second box intersection function call we have to specify the `cutoff` parameter explicitly. See the Section Runtime Performance below for a detailed discussion.

Example: Box_intersection_d/box_grid.cpp

Show / Hide
#include <CGAL/box_intersection_d.h>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cassert>
typedef CGAL::Box_intersection_d::Box_d<int,2> Box;
// coordinates for 9 boxes of a grid
int p[9*4] = { 0,0,1,1, 1,0,2,1, 2,0,3,1, // lower
0,1,1,2, 1,1,2,2, 2,1,3,2, // middle
0,2,1,3, 1,2,2,3, 2,2,3,3};// upper
// 9 boxes
Box boxes[9] = { Box( p, p+ 2), Box( p+ 4, p+ 6), Box( p+ 8, p+10),
Box( p+12, p+14), Box( p+16, p+18), Box( p+20, p+22),
Box( p+24, p+26), Box( p+28, p+30), Box( p+32, p+34)};
// 2 selected boxes as query; center and upper right
Box query[2] = { Box( p+16, p+18), Box( p+32, p+34)};
// callback function object writing results to an output iterator
template <class OutputIterator>
struct Report {
OutputIterator it;
Report( OutputIterator i) : it(i) {} // store iterator in object
// We write the id-number of box a to the output iterator assuming
// that box b (the query box) is not interesting in the result.
void operator()( const Box& a, const Box&) { *it++ = a.id(); }
};
template <class Iter> // helper function to create the function object
Report<Iter> report( Iter it) { return Report<Iter>(it); }
int main() {
// run the intersection algorithm and store results in a vector
std::vector<std::size_t> result;
CGAL::box_intersection_d( boxes, boxes+9, query, query+2,
report( std::back_inserter( result)));
// sort, check, and show result
std::sort( result.begin(), result.end());
std::size_t check1[13] = {0,1,2,3,4,4,5,5,6,7,7,8,8};
assert(result.size() == 13 && std::equal(check1,check1+13,result.begin()));
std::copy( result.begin(), result.end(),
std::ostream_iterator<std::size_t>( std::cout, " "));
std::cout << std::endl;
// run it again but for different cutoff value and half-open boxes
result.clear();
CGAL::box_intersection_d( boxes, boxes+9, query, query+2,
report( std::back_inserter( result)),
std::ptrdiff_t(1),
CGAL::Box_intersection_d::HALF_OPEN);
// sort, check, and show result
std::sort( result.begin(), result.end());
std::size_t check2[2] = {4,8};
assert(result.size() == 2 && std::equal(check2, check2+2, result.begin()));
std::copy( result.begin(), result.end(),
std::ostream_iterator<std::size_t>( std::cout, " "));
std::cout << std::endl;
return 0;
}
OutputIterator
CGAL::Box_intersection_d::HALF_OPEN
@ HALF_OPEN
Definition: Box_traits_d.h:57

# Runtime Performance

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.

To demonstrate that box intersection can be done quite fast, different box sequences are intersected in the range between 4 and 800000 boxes total. We use three-dimensional default boxes of closed topology with `float` coordinates and without additional data fields. The algorithm works directly on the boxes, not on pointer to boxes. Each box intersection is reported to an empty dummy callback.

For each box set, a near-optimal cutoff parameter is determined using an adaptive approximation. The runtime required for streaming is compared against usual scanning. Results on a Xeon 2.4GHz with 4GB main memory can be seen in Figure 102.1. For a small number of boxes, pure scanning is still faster than streaming with optimal cutoff, which would just delegate the box sets to the scanning algorithm. As there are more and more boxes, the overhead becomes less important.

Figure 102.1 Runtime comparison between the scanning and the streaming algorithm.

# Example Using a Custom Box Implementation

The example in the previous Section Example Using the Topology and the Cutoff Parameters uses an array to provide the coordinates and then creates another array for the boxes. In the following example we write our own box class `Box` that we can initialize directly with the four coordinates and create the array of boxes directly. We also omit the explicitly stored `id`-number and use the address of the box itself as `id`-number. This works only if the boxes do not change their position, i.e., we work with pointers to the boxes in the intersection algorithm.

We follow with our own box class `Box` the `BoxIntersectionBox_d` concept, which allows us to reuse the default traits implementation, i.e., we can use the same default function call to compute all intersections. See the example in the next section for a self-written traits class. So, in principle, the remainder of the example stays the same and we omit the part from the previous example for brevity that illustrates the half-open box topology.

The requirements for the box implementation are best studied on the reference manual page of `BoxIntersectionBox_d`. In a nutshell, we have to define the type `NT` for the box coordinates and the type `ID` for the `id`-number. Member functions give access to the coordinates and the `id`-number. A static member function returns the dimension.

Example: Box_intersection_d/custom_box_grid.cpp

Show / Hide
#include <CGAL/box_intersection_d.h>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cassert>
struct Box {
typedef int NT;
typedef std::ptrdiff_t ID;
int lo[2], hi[2];
Box( int lo0, int lo1, int hi0, int hi1) { lo[0]=lo0; lo[1]=lo1; hi[0]=hi0; hi[1]=hi1;}
static int dimension() { return 2; }
int min_coord(int dim) const { return lo[dim]; }
int max_coord(int dim) const { return hi[dim]; }
// id-function using address of current box,
// requires to work with pointers to boxes later
std::ptrdiff_t id() const { return (std::ptrdiff_t)(this); }
};
// 9 boxes of a grid
Box boxes[9] = { Box( 0,0,1,1), Box( 1,0,2,1), Box( 2,0,3,1), // low
Box( 0,1,1,2), Box( 1,1,2,2), Box( 2,1,3,2), // middle
Box( 0,2,1,3), Box( 1,2,2,3), Box( 2,2,3,3)};// upper
// 2 selected boxes as query; center and upper right
Box query[2] = { Box( 1,1,2,2), Box( 2,2,3,3)};
// With the special id-function we need to work on box pointers
Box* b_ptr[9] = { boxes, boxes+1, boxes+2, boxes+3, boxes+4, boxes+5,
boxes+6, boxes+7, boxes+8};
Box* q_ptr[2] = { query, query+1};
// callback function object writing results to an output iterator
template <class OutputIterator>
struct Report {
OutputIterator it;
Report( OutputIterator i) : it(i) {} // store iterator in object
// We write the position with respect to 'boxes' to the output iterator
// assuming that box b (the query box) is not interesting in the result.
void operator()( const Box* a, const Box*) {
*it++ = ( reinterpret_cast<Box*>(a->id()) - boxes);
}
};
template <class Iter> // helper function to create the function object
Report<Iter> report( Iter it) { return Report<Iter>(it); }
int main() {
// run the intersection algorithm and store results in a vector
std::vector<std::size_t> result;
CGAL::box_intersection_d( b_ptr, b_ptr+9, q_ptr, q_ptr+2,
report( std::back_inserter( result)),
std::ptrdiff_t(0));
// sort and check result
std::sort( result.begin(), result.end());
std::size_t chk[13] = {0,1,2,3,4,4,5,5,6,7,7,8,8};
assert( result.size()==13 && std::equal(chk,chk+13,result.begin()));
return 0;
}

# Example for Point Proximity Search with a Custom Traits Class

Given a set of 3D points, we want to find all pairs of points that are less than a certain distance apart. We use the box intersection algorithm to find good candidates, namely those that are less than this specified distance apart in the \( L_\infty\) norm, which is a good approximation of the Euclidean norm.

We use an unusual representation for the box, namely pointers to the 3D points themselves. We implement a special box traits class that interprets the point as a box of the dimensions \( [-\)`eps` \( ,+\)`eps` \( ]^3\) centered at this point. The value for `eps` is half the specified distance from above, i.e., points are reported if their distance is smaller than `2*eps`.

The requirements for the box traits class are best studied on the reference manual page of `BoxIntersectionTraits_d`. In a nutshell, we have to define the type `NT` for the box coordinates, the type `ID` for the `id`-number, and the type `Box_parameter` similar to the box handle, here `Point_3*` since we work with the pointers. All member functions in the traits class are static. Two functions give access to the max and min coordinates that we compute from the point coordinates plus or minus the `eps` value, respectively. For the `id`-number function the address of the point itself is sufficient, since the points stay stable. Another function returns the dimension.

The `report` callback function computes than the Euclidean distance and prints a message for points that are close enough.

Note that we need to reserve sufficient space in the `points` vector to avoid reallocations while we create the `points` vector and the `boxes` vector in parallel, since otherwise the `points` vector might reallocate and invalidate all pointers stored in the `boxes` so far.

Example: Box_intersection_d/proximity_custom_box_traits.cpp

Show / Hide
#include <CGAL/Simple_cartesian.h>
#include <CGAL/box_intersection_d.h>
#include <vector>
#include <fstream>
typedef CGAL::Simple_cartesian<float> Kernel;
typedef Kernel::Point_3 Point_3;
std::vector<Point_3> points;
std::vector<Point_3*> boxes; // boxes are just pointers to points
const float eps = 0.1f; // finds point pairs of distance < 2*eps
// Boxes are just pointers to 3d points. The traits class adds the
// +- eps size to each interval around the point, effectively building
// on the fly a box of size 2*eps centered at the point.
struct Traits {
typedef float NT;
typedef Point_3* Box_parameter;
typedef std::ptrdiff_t ID;
static int dimension() { return 3; }
static float coord( Box_parameter b, int d) {
return (d == 0) ? b->x() : ((d == 1) ? b->y() : b->z());
}
static float min_coord( Box_parameter b, int d) { return coord(b,d)-eps;}
static float max_coord( Box_parameter b, int d) { return coord(b,d)+eps;}
// id-function using address of current box,
// requires to work with pointers to boxes later
static std::ptrdiff_t id(Box_parameter b) { return (std::ptrdiff_t)(b); }
};
// callback function reports pairs in close proximity
void report( const Point_3* a, const Point_3* b) {
float dist = std::sqrt( CGAL::squared_distance( *a, *b));
if ( dist < 2*eps) {
std::cout << "Point " << (a - &(points.front())) << " and Point "
<< (b - &(points.front())) << " have distance " << dist
<< "." << std::endl;
}
}
int main(int argc, char*argv[]) {
std::ifstream in((argc>1)?argv[1]:CGAL::data_file_path("points_3/points.xyz"));
Point_3 p;
while(in >> p){
points.push_back(p);
}
for(std::size_t i = 0; i< points.size();++i) {
boxes.push_back( &points[i]);
}
// run the intersection algorithm and report proximity pairs
CGAL::box_self_intersection_d( boxes.begin(), boxes.end(),
report, Traits());
return 0;
}
CGAL::squared_distance
Kernel::FT squared_distance(Type1< Kernel > obj1, Type2< Kernel > obj2)
CGAL::Simple_cartesian

# Example for Polyline Intersection Test

Given two polylines we want to know if they intersect. This implementation creates a box for each segment of the polyline and creates two sets of boxes. The callback throws an exception as soon as an intersection is detected.

Example: Box_intersection_d/box_d_do_intersect_polylines.cpp

Show / Hide
#include <vector>
#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
template <typename Poly>
class Polylines_do_intersect
{
typedef typename Poly::const_iterator Iterator;
typedef typename std::iterator_traits<Iterator>::value_type Point_2;
typedef typename CGAL::Kernel_traits<Point_2>::Kernel::Segment_2 Segment_2;
typedef CGAL::Bbox_2 Bbox_2;
const Poly& pA, &pB;
struct Box : public CGAL::Box_intersection_d::Box_with_handle_d<double,2,Iterator> {
typedef CGAL::Box_intersection_d::Box_with_handle_d<double,2,Iterator> Base;
Box( const Bbox_2& b, Iterator it)
: Base(b,it)
{}
};
class FirstIntersection
{};
class Overlap {
const Poly& pA, &pB;
public:
Overlap(const Poly& pA, const Poly& pB)
: pA(pA), pB(pB)
{}
void operator()(const Box& a, const Box& b) {
Segment_2 sa(*(a.handle()), *(++(a.handle())));
Segment_2 sb(*(b.handle()), *(++(b.handle())));
if(CGAL::do_intersect(sa,sb)){
throw FirstIntersection();
}
}
};
public:
Polylines_do_intersect(const Poly& pA, const Poly& pB)
: pA(pA), pB(pB)
{}
bool operator()() const
{
std::vector<Box> bA, bB;
bA.reserve(pA.size() - 1 );
bB.reserve(pB.size() - 1 );
Iterator begin = pA.begin();
for(std::size_t j=0; j < pA.size()-1; j++){
Bbox_2 bb = pA[j].bbox() + pA[j+1].bbox();
bA.push_back(Box(bb, begin+j));
}
begin = pB.begin();
for(std::size_t j=0; j < pB.size()-1; j++){
Bbox_2 bb = pB[j].bbox() + pB[j+1].bbox();
bB.push_back(Box(bb, begin+j));
}
Overlap overlap(pA,pB);
try {
CGAL::box_intersection_d( bA.begin(), bA.end(), bB.begin(), bB.end(), overlap);
} catch(const FirstIntersection& ) {
return true;
}
return false;
}
};
template <typename Poly>
bool polylines_do_intersect(const Poly& pA,const Poly& pB)
{
Polylines_do_intersect<Poly> pdi(pA,pB);
return pdi();
}
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef std::vector<Point_2> CGAL_polyline;
int main()
{
CGAL_polyline pA = { Point_2(0,0), Point_2(1,0) };
CGAL_polyline pB = { Point_2(0,0), Point_2(0,1), Point_2(2,1) , Point_2(1,0)};
if(polylines_do_intersect(pA,pB)){
std::cout << "intersection" << std::endl;
} else {
std::cout << "no intersection" << std::endl;
}
return 0;
}
CGAL::Kernel_traits

# Design and Implementation History

Lutz Kettner and Andreas Meyer implemented the algorithms starting from the publication [2]. We had access to the original C implementation of Afra Zomorodian, which helped clarifying some questions, and we are grateful to the help of Afra Zomorodian in answering our questions during his visit. We thank Steve Robbins for an excellent review for this package. Steve Robbins provided an independent and earlier implementation of this algorithm, however, we learned too late about this implementation.