"Fossies" - the Fresh Open Source Software Archive

Member "doc_html/Box_intersection_d/group__PkgBoxIntersectionD__box__self__intersection__all__pairs__d.html" (8 Nov 2019, 16778 Bytes) of package /linux/misc/CGAL-4.14.2-doc_html.tar.xz:

Caution: In this restricted "Fossies" environment the current HTML page may not be correctly presentated and may have some non-functional links. You can here alternatively try to browse the pure source code or just view or download the uninterpreted raw source code. If the rendering is insufficient you may try to find and view the page on the CGAL-4.14.2-doc_html.tar.xz project site itself.

\( \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.14.2 - Intersecting Sequences of dD Iso-oriented Boxes

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

It does so by comparing all possible pairs of boxes and is thus inferior to the fast box_self_intersection_d() algorithm.

The sequence of boxes is given with a forward iterator range. The sequence is not modified. For each intersecting pair of boxes a callback function object is called with the two intersecting boxes as argument.

The algorithm is interface compatible with the box_self_intersection_d() function. Similarly, we call the value_type of the iterators the box handle, which is either our box type or a pointer type to our 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.

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.


See also


The algorithm is trivially testing all pairs and runs therefore in time \( O(n^2)\) where \( n\) is the size of the input sequence. This algorithm does not use the id-number of the boxes.


template<class ForwardIter , class Callback >
void CGAL::box_self_intersection_all_pairs_d (ForwardIter begin, ForwardIter end, Callback callback, 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 ForwardIter.
template<class ForwardIter , class Callback , class BoxTraits >
void CGAL::box_self_intersection_all_pairs_d (ForwardIter begin, ForwardIter end, Callback callback, BoxTraits box_traits, CGAL::Box_intersection_d::Topology topology=CGAL::Box_intersection_d::CLOSED)
 Invocation with custom box traits.