Debian Codegraph @

include/deal.II/numerics/rtree.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2018 - 2025 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_numerics_rtree_h
16 #define dealii_numerics_rtree_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/point.h>
21 #include <deal.II/base/std_cxx20/iota_view.h>
22
23 #include <deal.II/boost_adaptors/bounding_box.h>
24 #include <deal.II/boost_adaptors/point.h>
25 #include <deal.II/boost_adaptors/segment.h>
26
27 DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
28 #include <boost/geometry/algorithms/distance.hpp>
29 #include <boost/geometry/index/rtree.hpp>
30 #include <boost/geometry/strategies/strategies.hpp>
31 DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
32
33 #include <memory>
34
35
36 DEAL_II_NAMESPACE_OPEN
37
38 /**
39 * A wrapper for the boost::geometry::index::rtree class, implementing a
40 * self-balancing spatial index (the R-tree) capable of storing various types of
41 * values, using different balancing algorithms.
42 *
43 * From [Wikipedia](https://en.wikipedia.org/wiki/R-tree):
44 * <blockquote>
45 * R-trees are tree data structures used for spatial access methods, i.e., for
46 * indexing multi-dimensional information such as geographical coordinates,
47 * rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984
48 * and has found significant use in both theoretical and applied contexts. A
49 * common real-world usage for an R-tree might be to store spatial objects such
50 * as restaurant locations or the polygons that typical maps are made of:
51 * streets, buildings, outlines of lakes, coastlines, etc. and then find answers
52 * quickly to queries such as "Find all museums within 2 km of my current
53 * location", "retrieve all road segments within 2 km of my location" (to
54 * display them in a navigation system) or "find the nearest gas station"
55 * (although not taking roads into account). The R-tree can also accelerate
56 * nearest neighbor search for various distance metrics, including
57 * great-circle distance.
58 *
59 * The key idea of the data structure is to group nearby objects and represent
60 * them with their minimum bounding rectangle in the next higher level of the
61 * tree; the "R" in R-tree is for rectangle. Since all objects lie within this
62 * bounding rectangle, a query that does not intersect the bounding rectangle
63 * also cannot intersect any of the contained objects. At the leaf level, each
64 * rectangle describes a single object; at higher levels the aggregation of an
65 * increasing number of objects. This can also be seen as an increasingly coarse
66 * approximation of the data set.
67 *
68 * The key difficulty of R-tree is to build an efficient tree that on one hand
69 * is balanced (so the leaf nodes are at the same height) on the other hand the
70 * rectangles do not cover too much empty space and do not overlap too much (so
71 * that during search, fewer subtrees need to be processed). For example, the
72 * original idea for inserting elements to obtain an efficient tree is to always
73 * insert into the subtree that requires least enlargement of its bounding box.
74 * Once that page is full, the data is split into two sets that should cover the
75 * minimal area each. Most of the research and improvements for R-trees aims at
76 * improving the way the tree is built and can be grouped into two objectives:
77 * building an efficient tree from scratch (known as bulk-loading) and
78 * performing changes on an existing tree (insertion and deletion).
79 * </blockquote>
80 *
81 * An RTree may store any type of @p LeafType as long as it is possible to extract
82 * an @p Indexable that the RTree can handle and compare values. An @p Indexable
83 * is a type adapted to the Point, BoundingBox or Segment concept, for which
84 * distance and equality comparison are implemented. The deal.II Point, Segment,
85 * and BoundingBox classes satisfy this requirement, but you can mix in any
86 * geometry object that boost::geometry accepts as indexable.
87 *
88 * In particular, given an @p Indexable type (for example a Point, a BoundingBox,
89 * or a Segment), @p LeafType can by any of @p Indexable, `std::pair<Indexable, T>`,
90 * `boost::tuple<Indexable, ...>` or `std::tuple<Indexable, ...>`.
91 *
92 * The optional argument @p IndexType is used only when adding elements to the
93 * tree one by one. If a range insertion is used, then the tree is built using
94 * the packing algorithm.
95 *
96 * Linear, quadratic, and rstar algorithms are available if one wants to
97 * construct the tree sequentially. However, none of these is very efficient,
98 * and users should use the packing algorithm when possible.
99 *
100 * The packing algorithm constructs the tree all at once, and may be used when
101 * you have all the leaves at your disposal.
102 *
103 * This class is usually used in combination with one of the two helper
104 * functions pack_rtree(), that takes a container or a range of iterators to
105 * construct the RTree using the packing algorithm.
106 *
107 * An example usage is the following:
108 *
109 * @code
110 * std::vector<Point<2>> points = generate_some_points();
111 * auto tree = pack_rtree(points.begin(), points.end());
112 * // or, equivalently:
113 * // auto tree = pack_rtree(points);
114 * @endcode
115 *
116 * The tree is accessed by using [`boost::geometry::index`
117 * queries](https://www.boost.org/doc/libs/1_68_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html).
118 * For example, after constructing the tree with the snippet above, one can ask
119 * for the closest points to a segment in the following way:
120 *
121 * @code
122 * namespace bgi = boost::geometry::index;
123 *
124 * Segment<2> segment(Point<2>(0,0), Point<2>(1,1));
125 *
126 * std::vector<Point<2>> intersection;
127 * tree.query(bgi::nearest(segment,3), std::back_inserter(intersection));
128 * // Returns the 3 closest points to the Segment defined above.
129 * @endcode
130 *
131 * In general, a tree does not need to store the actual objects, as long as it
132 * knows how to access a const reference to an indexable type. This is
133 * achieved by passing the optional template argument @p IndexableGetter, that
134 * extracts a const reference to one of the possible indexable types given an
135 * object of type @p LeafType. As an example, one may store points in a container,
136 * and only create a tree of the indices within the container, using the
137 * IndexableGetterFromIndices class defined below, and the function
138 * pack_rtree_of_indices().
139 */
140 template <typename LeafType,
141 typename IndexType = boost::geometry::index::linear<16>,
142 typename IndexableGetter =
143 boost::geometry::index::indexable<LeafType>>
144 using RTree =
145 boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
146
147 /**
148 * Construct the correct RTree object by passing an iterator range.
149 *
150 * Notice that the order of the parameters is the opposite with respect to the
151 * RTree class, since we can automatically infer the @p LeafType from the
152 * arguments.
153 */
154 template <typename IndexType = boost::geometry::index::linear<16>,
155 typename LeafTypeIterator,
156 typename IndexableGetter = boost::geometry::index::indexable<
157 typename LeafTypeIterator::value_type>>
158 RTree<typename LeafTypeIterator::value_type, IndexType, IndexableGetter>
159 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
160
161 /**
162 * Construct an RTree object by passing an STL container type.
163 * This function is used in step-70.
164 *
165 * Notice that the order of the template parameters is the opposite with respect
166 * to the
167 * RTree class, since we can automatically infer the @p LeafType from the
168 * arguments, and we only need to specify the @p IndexType if the default is not
169 * adequate.
170 */
171 template <typename IndexType = boost::geometry::index::linear<16>,
172 typename ContainerType,
173 typename IndexableGetter = boost::geometry::index::indexable<
174 typename ContainerType::value_type>>
175 RTree<typename ContainerType::value_type, IndexType, IndexableGetter>
176 pack_rtree(const ContainerType &container);
177
178 /**
179 * A class that may be used as an @p IndexableGetter template argument for an
180 * RTree that stores indices to entries in a @p Container type.
181 *
182 * This class may be used as a proxy to extract an indexable type from
183 * compatible containers. For example:
184 * @code
185 * std::vector<std::pair<Point<dim>, double> > point_temperature = fill();
186 * IndexableGetterFromIndices<decltype(point_temperature)>
187 * getter(point_temperature);
188 *
189 * const Point<dim> &p = getter(i); // returns point_temperature[i].first;
190 * @endcode
191 *
192 * This class is used by the pack_rtree_of_indices() function to construct an
193 * RTree where the leaves are indices pointing to the entries of the container
194 * passed to this class.
195 */
196 template <typename Container>
197 class IndexableGetterFromIndices
198 {
199 public:
200 /**
201 * An alias for the boost type that is used to extract a Point, Segment, or
202 * BoundingBox from compatible types (pairs, tuples, etc.).
203 */
204 using IndexableGetter =
205 typename boost::geometry::index::indexable<typename Container::value_type>;
206
207 /**
208 * An alias to the actual geometrical type.
209 */
210 using result_type = typename IndexableGetter::result_type;
211
212 /**
213 * An alias to the index type.
214 */
215 using size_t = typename Container::size_type;
216
217 /**
218 * Constructor. Store a const reference to a container.
219 */
220 explicit IndexableGetterFromIndices(const Container &c)
221 : container(c)
222 {}
223
224 /**
225 * Implements the @p IndexableGetter requirements of the rtree class.
226 */
227 result_type
228 operator()(size_t i) const
229 {
230 return getter(container[i]);
231 }
232
233 private:
234 /**
235 * A const reference to the container.
236 */
237 const Container &container;
238
239 /**
240 * An instantiation of the getter that allows easy translation from the
241 * container @p value_type and the actual indexable type.
242 */
243 IndexableGetter getter;
244 };
245
246 /**
247 * Construct a RTree object that stores the indices of an existing container of
248 * indexable types. The only requirement on the container is that it supports
249 * operator[] for any index between 0 and the size of the container (i.e., a
250 * std::vector, or an std::array will do, however an std::map won't).
251 *
252 * Differently from the object created by the pack_rtree() function, in this
253 * case we don't store the actual geometrical types, but just their indices:
254 *
255 * @code
256 * namespace bgi = boost::geometry::index;
257 * std::vector<Point<dim>> some_points = fill();
258 * auto tree = pack_rtree(points); // the tree contains a copy of the points
259 * auto index_tree = pack_rtree_of_indices(points); // the tree contains only
260 * // the indices of the
261 * // points
262 * BoundingBox<dim> box = build_a_box();
263 *
264 * for(const auto &p: tree | bgi::adaptors::queried(bgi::intersects(box)))
265 * std::cout << "Point p: " << p << std::endl;
266 *
267 * for(const auto &i: index_tree | bgi::adaptors::queried(bgi::intersects(box)))
268 * std::cout << "Point p: " << some_points[i] << std::endl;
269 * @endcode
270 *
271 * The leaves stored in the tree are the indices of the corresponding entry in
272 * the container. A reference to the external container is stored internally,
273 * but keep in mind that if you change the container, you should rebuild the
274 * tree.
275 *
276 * @warning This function does not work on Windows. As an alternative,
277 * build a tree with pairs of point and id. For instance to
278 * create an intersection between `BoundingBox<dim> box` and
279 * `std::vector<BoundingBox<dim>> boxes`, don't write:
280 * @code
281 * const auto tree = pack_rtree_of_indices(boxes);
282 *
283 * for (const auto &i : tree | bgi::adaptors::queried(bgi::intersects(box)))
284 * std::cout << i << " " << boxes[i] << std::endl;
285 * @endcode
286 * but instead:
287 * @code
288 * std::vector<std::pair<BoundingBox<dim>, unsigned int>> boxes_and_ids;
289 *
290 * for(unsigned int i = 0; i < boxes.size(); ++i)
291 * boxes_and_ids.emplace_back(boxes[i], i);
292 *
293 * const auto tree = pack_rtree(boxes_and_ids);
294 *
295 * for (const auto &i : tree | bgi::adaptors::queried(bgi::intersects(box)))
296 * std::cout << i->second << " " << boxes[i->second] << std::endl;
297 * @endcode
298 *
299 */
300 template <typename IndexType = boost::geometry::index::linear<16>,
301 typename ContainerType>
302 RTree<typename ContainerType::size_type,
303 IndexType,
304 IndexableGetterFromIndices<ContainerType>>
305 pack_rtree_of_indices(const ContainerType &container);
306
307 /**
308 * Helper structure that allows one to extract a level from an RTree as a vector
309 * of BoundingBox objects.
310 *
311 * This structure implements a boost::geometry::index::detail::rtree::visitor
312 * object, allowing one to visit any existing RTree object, and return the
313 * vector of bounding boxes associated to a specific target level of the tree.
314 *
315 * Although possible, direct usage of this structure is cumbersome. The
316 * suggested usage of this class is through the helper function
317 * extract_rtree_level().
318 */
319 template <typename Value,
320 typename Options,
321 typename Translator,
322 typename Box,
323 typename Allocators>
324 struct ExtractLevelVisitor
325 : public boost::geometry::index::detail::rtree::visitor<
326 Value,
327 typename Options::parameters_type,
328 Box,
329 Allocators,
330 typename Options::node_tag,
331 true>::type
332 {
333 /**
334 * Construct a vector @p boxes of BoundingBox objects corresponding to the
335 * @p target_level of the tree.
336 */
337 inline ExtractLevelVisitor(
338 const Translator &translator,
339 const unsigned int target_level,
340 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes);
341
342 /**
343 * An alias that identifies an InternalNode of the tree.
344 */
345 using InternalNode =
346 typename boost::geometry::index::detail::rtree::internal_node<
347 Value,
348 typename Options::parameters_type,
349 Box,
350 Allocators,
351 typename Options::node_tag>::type;
352
353 /**
354 * An alias that identifies a Leaf of the tree.
355 */
356 using Leaf = typename boost::geometry::index::detail::rtree::leaf<
357 Value,
358 typename Options::parameters_type,
359 Box,
360 Allocators,
361 typename Options::node_tag>::type;
362
363 /**
364 * Implements the visitor interface for InternalNode objects. If the node
365 * belongs to the @p target_level, then fill the bounding box vector.
366 */
367 inline void
368 operator()(const InternalNode &node);
369
370 /**
371 * Implements the visitor interface for Leaf objects.
372 */
373 inline void
374 operator()(const Leaf &);
375
376 /**
377 * Translator interface, required by the boost implementation of the rtree.
378 */
379 const Translator &translator;
380
381 /**
382 * Store the level we are currently visiting.
383 */
384 std::size_t level;
385
386 /**
387 * The level we want to extract from the RTree object.
388 */
389 const std::size_t target_level;
390
391 /**
392 * A reference to the input vector of BoundingBox objects.
393 */
394 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes;
395 };
396
397 /**
398 * Given a RTree object @p rtree, and a target level @p level, return a vector
399 * of BoundingBox objects containing all the bounding boxes that make the given
400 * @p level of the @p rtree. This function is a convenient wrapper around the
401 * ExtractLevelVisitor class. It is used in step-70.
402 *
403 * Since an RTree object is a balanced tree, you can expect each entry of the
404 * resulting vector to contain roughly the same number of children, and
405 * ultimately, the same number of leaf objects. If you request for a level that
406 * is not present in the RTree, the last level is returned.
407 *
408 * A typical usage of this function is in the context of
409 * parallel::distributed::Triangulation objects, where one would like to
410 * construct a rough representation of the area which is covered by the locally
411 * owned cells of the active process, and exchange this information with other
412 * processes. The finest level of information is given by the leaves, which in
413 * this context would be the collection of all the bounding boxes associated
414 * to the locally owned cells of the triangulation. Exchanging this information
415 * with all participating processes would defeat the purpose of parallel
416 * computations. If however one constructs an RTree containing these bounding
417 * boxes (for example, by calling
418 * GridTools::Cache::get_cell_bounding_boxes_rtree()), and then extracts one of
419 * the first levels of the RTree, only a handful of BoundingBox objects would be
420 * returned, allowing the user to have a very efficient description of the
421 * geometry of the domain, and of its distribution among processes.
422 *
423 * An example usage is given by the following snippet of code:
424 * @code
425 * parallel::distributed::Triangulation<2> tria(MPI_COMM_WORLD);
426 * GridGenerator::hyper_ball(tria);
427 * tria.refine_global(4);
428 *
429 * std::vector<BoundingBox<2>> all_boxes(tria.n_locally_owned_active_cells());
430 * unsigned int i = 0;
431 * for (const auto &cell : tria.active_cell_iterators())
432 * if (cell->is_locally_owned())
433 * all_boxes[i++] = cell->bounding_box();
434 *
435 * const auto tree = pack_rtree(all_boxes);
436 * const auto boxes = extract_rtree_level(tree, 1);
437 * @endcode
438 *
439 * When run on three processes, the complete set of the BoundingBox objects
440 * surrounding only the locally owned cells and the second level of the rtree
441 * constructed with those boxes would look like in the following pictures (one
442 * image per process):
443 *
444 * @image html rtree-process-0.png
445 * @image html rtree-process-1.png
446 * @image html rtree-process-2.png
447 */
448 template <typename Rtree>
449 inline std::vector<BoundingBox<
450 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
451 extract_rtree_level(const Rtree &tree, const unsigned int level);
452
453
454
455 /**
456 * Given an Rtree object @p tree and a target level @p level, this function returns
457 * the bounding boxes associated to the children on level l+1 and stores them in
458 * a vector. The resulting type is hence a vector of vectors of BoundingBox
459 * objects.
460 * If @p v is such a vector, then @p v has the following property:
461 * @p v[i] is a vector with all of the bounding boxes associated to the children
462 * of the i-th node of the tree.
463 */
464 template <typename Rtree>
465 std::vector<std::vector<BoundingBox<
466 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
467 extract_children_of_level(const Rtree &tree, const unsigned int level);
468
469
470
471 // Inline and template functions
472 #ifndef DOXYGEN
473
474 template <typename IndexType,
475 typename LeafTypeIterator,
476 typename IndexableGetter>
477 RTree<typename LeafTypeIterator::value_type, IndexType, IndexableGetter>
478 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
479 {
480 return RTree<typename LeafTypeIterator::value_type,
481 IndexType,
482 IndexableGetter>(begin, end);
483 }
484
485
486
487 template <typename IndexType, typename ContainerType, typename IndexableGetter>
488 RTree<typename ContainerType::value_type, IndexType, IndexableGetter>
489 pack_rtree(const ContainerType &container)
490 {
491 return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
492 container.begin(), container.end());
493 }
494
495
496
497 template <typename IndexType, typename ContainerType>
498 RTree<typename ContainerType::size_type,
499 IndexType,
500 IndexableGetterFromIndices<ContainerType>>
501 pack_rtree_of_indices(const ContainerType &container)
502 {
503 // We need an array that holds the indices we want to pack. The rtree
504 // implementation in BOOST, for reasons not entirely clear, insists
505 // on using a reference to the elements of the range. This is fine if
506 // the indices are stored in a container, so that's what we do.
507 // (It would be nice if we could just pass a std::ranges::iota_view
508 // instead, but that has no nested 'reference' type, and this then
509 // trips up BOOST rtree.)
510 std::vector<typename ContainerType::size_type> indices(container.size());
511 for (typename ContainerType::size_type i = 0; i < container.size(); ++i)
512 indices[i] = i;
513
514 return RTree<typename ContainerType::size_type,
515 IndexType,
516 IndexableGetterFromIndices<ContainerType>>(
517 indices.begin(),
518 indices.end(),
519 IndexType(),
520 IndexableGetterFromIndices<ContainerType>(container));
521 }
522
523
524
525 template <typename Value,
526 typename Options,
527 typename Translator,
528 typename Box,
529 typename Allocators>
530 ExtractLevelVisitor<Value, Options, Translator, Box, Allocators>::
531 ExtractLevelVisitor(
532 const Translator &translator,
533 const unsigned int target_level,
534 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
535 : translator(translator)
536 , level(0)
537 , target_level(target_level)
538 , boxes(boxes)
539 {}
540
541
542
543 template <typename Value,
544 typename Options,
545 typename Translator,
546 typename Box,
547 typename Allocators>
548 void
549 ExtractLevelVisitor<Value, Options, Translator, Box, Allocators>::operator()(
550 const ExtractLevelVisitor::InternalNode &node)
551 {
552 using ElementsType =
553 typename boost::geometry::index::detail::rtree::elements_type<
554 InternalNode>::type;
555
556 const auto &elements = boost::geometry::index::detail::rtree::elements(node);
557
558 if (level == target_level)
559 {
560 const auto offset = boxes.size();
561 boxes.resize(offset + elements.size());
562
563 unsigned int i = offset;
564 for (typename ElementsType::const_iterator it = elements.begin();
565 it != elements.end();
566 ++it)
567 {
568 boost::geometry::convert(it->first, boxes[i]);
569 ++i;
570 }
571 return;
572 }
573
574 const std::size_t level_backup = level;
575 ++level;
576
577 for (typename ElementsType::const_iterator it = elements.begin();
578 it != elements.end();
579 ++it)
580 {
581 boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
582 }
583
584 level = level_backup;
585 }
586
587 template <typename Value,
588 typename Options,
589 typename Translator,
590 typename Box,
591 typename Allocators>
592 void
593 ExtractLevelVisitor<Value, Options, Translator, Box, Allocators>::operator()(
594 const ExtractLevelVisitor::Leaf &)
595 {}
596
597
598
599 template <typename Rtree>
600 inline std::vector<BoundingBox<
601 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
602 extract_rtree_level(const Rtree &tree, const unsigned int level)
603 {
604 constexpr unsigned int dim =
605 boost::geometry::dimension<typename Rtree::indexable_type>::value;
606
607 using RtreeView =
608 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
609 RtreeView rtv(tree);
610
611 std::vector<BoundingBox<dim>> boxes;
612
613 if (rtv.depth() == 0)
614 {
615 // The below algorithm does not work for `rtv.depth()==0`, which might
616 // happen if the number entries in the tree is too small.
617 // In this case, simply return a single bounding box.
618 boxes.resize(1);
619 boost::geometry::convert(tree.bounds(), boxes[0]);
620 }
621 else
622 {
623 const unsigned int target_level =
624 std::min<unsigned int>(level, rtv.depth() - 1);
625
626 ExtractLevelVisitor<typename RtreeView::value_type,
627 typename RtreeView::options_type,
628 typename RtreeView::translator_type,
629 typename RtreeView::box_type,
630 typename RtreeView::allocators_type>
631 extract_level_visitor(rtv.translator(), target_level, boxes);
632 rtv.apply_visitor(extract_level_visitor);
633 }
634
635 return boxes;
636 }
637
638
639
640 template <class Rtree>
641 unsigned int
642 n_levels(const Rtree &tree)
643 {
644 boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
645 return rtv.depth();
646 }
647
648
649 template <typename Value,
650 typename Options,
651 typename Translator,
652 typename Box,
653 typename Allocators>
654 struct NodeVisitor : public boost::geometry::index::detail::rtree::visitor<
655 Value,
656 typename Options::parameters_type,
657 Box,
658 Allocators,
659 typename Options::node_tag,
660 true>::type
661 {
662 inline NodeVisitor(
663 const Translator &translator,
664 unsigned int target_level,
665 std::vector<
666 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>> &boxes);
667
668
669 /**
670 * An alias that identifies an InternalNode of the tree.
671 */
672 using InternalNode =
673 typename boost::geometry::index::detail::rtree::internal_node<
674 Value,
675 typename Options::parameters_type,
676 Box,
677 Allocators,
678 typename Options::node_tag>::type;
679
680 /**
681 * An alias that identifies a Leaf of the tree.
682 */
683 using Leaf = typename boost::geometry::index::detail::rtree::leaf<
684 Value,
685 typename Options::parameters_type,
686 Box,
687 Allocators,
688 typename Options::node_tag>::type;
689
690 /**
691 * Implements the visitor interface for InternalNode objects. If the node
692 * belongs to the level next to @p target_level, then fill the bounding box vector for that node.
693 */
694 inline void
695 operator()(const InternalNode &node);
696
697 /**
698 * Implements the visitor interface for Leaf objects.
699 */
700 inline void
701 operator()(const Leaf &);
702
703 /**
704 * Translator interface, required by the boost implementation of the rtree.
705 */
706 const Translator &translator;
707
708 /**
709 * Store the level we are currently visiting.
710 */
711 std::size_t level;
712
713 /**
714 * Index used to keep track of the number of different visited nodes during
715 * recursion/
716 */
717 std::size_t node_counter;
718
719 /**
720 * The level where children are living.
721 * Before: "we want to extract from the RTree object."
722 */
723 const std::size_t target_level;
724
725 /**
726 * A reference to the input vector of vector of BoundingBox objects. This
727 * vector v has the following property: v[i] = vector with all
728 * of the BoundingBox bounded by the i-th node of the Rtree.
729 */
730 std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>>
731 &boxes_in_boxes;
732 };
733
734
735
736 template <typename Value,
737 typename Options,
738 typename Translator,
739 typename Box,
740 typename Allocators>
741 NodeVisitor<Value, Options, Translator, Box, Allocators>::NodeVisitor(
742 const Translator &translator,
743 const unsigned int target_level,
744 std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>>
745 &bb_in_boxes)
746 : translator(translator)
747 , level(0)
748 , node_counter(0)
749 , target_level(target_level)
750 , boxes_in_boxes(bb_in_boxes)
751 {}
752
753
754
755 template <typename Value,
756 typename Options,
757 typename Translator,
758 typename Box,
759 typename Allocators>
760 void
761 NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
762 const NodeVisitor::InternalNode &node)
763 {
764 using elements_type =
765 typename boost::geometry::index::detail::rtree::elements_type<
766 InternalNode>::type; // pairs of bounding box and pointer to child node
767 const elements_type &elements =
768 boost::geometry::index::detail::rtree::elements(node);
769
770 if (level == target_level)
771 {
772 const unsigned int n_children = elements.size();
773 const auto offset = boxes_in_boxes.size();
774 boxes_in_boxes.resize(offset + n_children);
775 }
776
777 if (level == target_level + 1)
778 {
779 // I have now access to children of level target_level
780 boxes_in_boxes[node_counter].resize(elements.size()); // number of bboxes
781 unsigned int i = 0;
782 for (typename elements_type::const_iterator it = elements.begin();
783 it != elements.end();
784 ++it)
785 {
786 boost::geometry::convert(it->first, boxes_in_boxes[node_counter][i]);
787 ++i;
788 }
789 // Children have been stored, go to the next parent.
790 ++node_counter;
791 return;
792 }
793
794 std::size_t level_backup = level;
795 ++level;
796
797 for (typename elements_type::const_iterator it = elements.begin();
798 it != elements.end();
799 ++it)
800 {
801 boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
802 }
803
804 level = level_backup;
805 }
806
807
808
809 template <typename Value,
810 typename Options,
811 typename Translator,
812 typename Box,
813 typename Allocators>
814 void
815 NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
816 const NodeVisitor::Leaf &)
817 {
818 // No children for leaf nodes.
819 boxes_in_boxes.clear();
820 }
821
822 template <typename Rtree>
823 inline std::vector<std::vector<BoundingBox<
824 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
825 extract_children_of_level(const Rtree &tree, const unsigned int level)
826 {
827 constexpr unsigned int dim =
828 boost::geometry::dimension<typename Rtree::indexable_type>::value;
829
830 using RtreeView =
831 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
832 RtreeView rtv(tree);
833
834 std::vector<std::vector<BoundingBox<dim>>> boxes_in_boxes;
835
836 if (rtv.depth() == 0)
837 {
838 // The below algorithm does not work for `rtv.depth()==0`, which might
839 // happen if the number entries in the tree is too small.
840 // In this case, simply return a single bounding box.
841 boxes_in_boxes.resize(1);
842 boxes_in_boxes[0].resize(1);
843 boost::geometry::convert(tree.bounds(), boxes_in_boxes[0][0]);
844 }
845 else
846 {
847 const unsigned int target_level =
848 std::min<unsigned int>(level, rtv.depth() - 1);
849
850 NodeVisitor<typename RtreeView::value_type,
851 typename RtreeView::options_type,
852 typename RtreeView::translator_type,
853 typename RtreeView::box_type,
854 typename RtreeView::allocators_type>
855 node_visitor(rtv.translator(), target_level, boxes_in_boxes);
856 rtv.apply_visitor(node_visitor);
857 }
858
859 return boxes_in_boxes;
860 }
861
862
863
864 #endif
865
866 DEAL_II_NAMESPACE_CLOSE
867
868 #endif