Reference documentation for deal.II version GIT 741a3088b8 2023-04-01 07:05:02+00:00
\(\newcommand{\dealvcentcolon}{\mathrel{\mathop{:}}}\) \(\newcommand{\dealcoloneq}{\dealvcentcolon\mathrel{\mkern-1.2mu}=}\) \(\newcommand{\jump}[1]{\left[\!\left[ #1 \right]\!\right]}\) \(\newcommand{\average}[1]{\left\{\!\left\{ #1 \right\}\!\right\}}\)
rtree.h
Go to the documentation of this file.
1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 2017 - 2022 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15 
16 #ifndef dealii_numerics_rtree_h
17 #define dealii_numerics_rtree_h
18 
19 #include <deal.II/base/config.h>
20 
21 #include <deal.II/base/point.h>
23 
27 
28 #include <boost/geometry/algorithms/distance.hpp>
29 #include <boost/geometry/index/rtree.hpp>
30 #include <boost/geometry/strategies/strategies.hpp>
31 
32 #include <memory>
33 
34 
36 
139 template <typename LeafType,
140  typename IndexType = boost::geometry::index::linear<16>,
141  typename IndexableGetter =
143 using RTree =
144  boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
145 
153 template <typename IndexType = boost::geometry::index::linear<16>,
154  typename LeafTypeIterator,
155  typename IndexableGetter = boost::geometry::index::indexable<
156  typename LeafTypeIterator::value_type>>
158 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
159 
170 template <typename IndexType = boost::geometry::index::linear<16>,
171  typename ContainerType,
172  typename IndexableGetter = boost::geometry::index::indexable<
173  typename ContainerType::value_type>>
175 pack_rtree(const ContainerType &container);
176 
195 template <typename Container>
197 {
198 public:
205 
209  using result_type = typename IndexableGetter::result_type;
210 
214  using size_t = typename Container::size_type;
215 
219  explicit IndexableGetterFromIndices(Container const &c)
220  : container(c)
221  {}
222 
227  operator()(size_t i) const
228  {
229  return getter(container[i]);
230  }
231 
232 private:
236  const Container &container;
237 
243 };
244 
275 template <typename IndexType = boost::geometry::index::linear<16>,
276  typename ContainerType>
278  IndexType,
280 pack_rtree_of_indices(const ContainerType &container);
281 
294 template <typename Value,
295  typename Options,
296  typename Translator,
297  typename Box,
298  typename Allocators>
300  : public boost::geometry::index::detail::rtree::visitor<
301  Value,
302  typename Options::parameters_type,
303  Box,
304  Allocators,
305  typename Options::node_tag,
306  true>::type
307 {
313  Translator const & translator,
314  const unsigned int target_level,
315  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes);
316 
320  using InternalNode =
321  typename boost::geometry::index::detail::rtree::internal_node<
322  Value,
323  typename Options::parameters_type,
324  Box,
325  Allocators,
326  typename Options::node_tag>::type;
327 
331  using Leaf = typename boost::geometry::index::detail::rtree::leaf<
332  Value,
333  typename Options::parameters_type,
334  Box,
335  Allocators,
336  typename Options::node_tag>::type;
337 
342  inline void
343  operator()(InternalNode const &node);
344 
348  inline void
349  operator()(Leaf const &);
350 
354  Translator const &translator;
355 
359  size_t level;
360 
364  const size_t target_level;
365 
369  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes;
370 };
371 
423 template <typename Rtree>
424 inline std::vector<BoundingBox<
425  boost::geometry::dimension<typename Rtree::indexable_type>::value>>
426 extract_rtree_level(const Rtree &tree, const unsigned int level);
427 
428 
429 
430 // Inline and template functions
431 #ifndef DOXYGEN
432 
433 template <typename IndexType,
434  typename LeafTypeIterator,
435  typename IndexableGetter>
437 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
438 {
439  return RTree<typename LeafTypeIterator::value_type,
440  IndexType,
441  IndexableGetter>(begin, end);
442 }
443 
444 
445 
446 template <typename IndexType, typename ContainerType, typename IndexableGetter>
448 pack_rtree(const ContainerType &container)
449 {
450  return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
451  container.begin(), container.end());
452 }
453 
454 
455 
456 template <typename IndexType, typename ContainerType>
458  IndexType,
460 pack_rtree_of_indices(const ContainerType &container)
461 {
463  typename ContainerType::size_type>
464  indices(0, container.size());
465  return RTree<typename ContainerType::size_type,
466  IndexType,
468  indices.begin(),
469  indices.end(),
470  IndexType(),
472 }
473 
474 
475 
476 template <typename Value,
477  typename Options,
478  typename Translator,
479  typename Box,
480  typename Allocators>
483  const Translator & translator,
484  const unsigned int target_level,
485  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
486  : translator(translator)
487  , level(0)
488  , target_level(target_level)
489  , boxes(boxes)
490 {}
491 
492 
493 
494 template <typename Value,
495  typename Options,
496  typename Translator,
497  typename Box,
498  typename Allocators>
499 void
502 {
503  using ElmentsType =
504  typename boost::geometry::index::detail::rtree::elements_type<
505  InternalNode>::type;
506 
507  const auto &elements = boost::geometry::index::detail::rtree::elements(node);
508 
509  if (level == target_level)
510  {
511  const auto offset = boxes.size();
512  boxes.resize(offset + elements.size());
513 
514  unsigned int i = offset;
515  for (typename ElmentsType::const_iterator it = elements.begin();
516  it != elements.end();
517  ++it)
518  {
519  boost::geometry::convert(it->first, boxes[i]);
520  ++i;
521  }
522  return;
523  }
524 
525  const size_t level_backup = level;
526  ++level;
527 
528  for (typename ElmentsType::const_iterator it = elements.begin();
529  it != elements.end();
530  ++it)
531  {
532  boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
533  }
534 
535  level = level_backup;
536 }
537 
538 template <typename Value,
539  typename Options,
540  typename Translator,
541  typename Box,
542  typename Allocators>
543 void
546 {}
547 
548 
549 
550 template <typename Rtree>
551 inline std::vector<BoundingBox<
552  boost::geometry::dimension<typename Rtree::indexable_type>::value>>
553 extract_rtree_level(const Rtree &tree, const unsigned int level)
554 {
555  constexpr unsigned int dim =
556  boost::geometry::dimension<typename Rtree::indexable_type>::value;
557 
558  using RtreeView =
559  boost::geometry::index::detail::rtree::utilities::view<Rtree>;
560  RtreeView rtv(tree);
561 
562  std::vector<BoundingBox<dim>> boxes;
563 
564  if (rtv.depth() == 0)
565  {
566  // The below algorithm does not work for `rtv.depth()==0`, which might
567  // happen if the number entries in the tree is too small.
568  // In this case, simply return a single bounding box.
569  boxes.resize(1);
570  boost::geometry::convert(tree.bounds(), boxes[0]);
571  }
572  else
573  {
574  const unsigned int target_level =
575  std::min<unsigned int>(level, rtv.depth() - 1);
576 
577  ExtractLevelVisitor<typename RtreeView::value_type,
578  typename RtreeView::options_type,
579  typename RtreeView::translator_type,
580  typename RtreeView::box_type,
581  typename RtreeView::allocators_type>
582  extract_level_visitor(rtv.translator(), target_level, boxes);
583  rtv.apply_visitor(extract_level_visitor);
584  }
585 
586  return boxes;
587 }
588 
589 
590 
591 template <class Rtree>
592 unsigned int
593 n_levels(const Rtree &tree)
594 {
595  boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
596  return rtv.depth();
597 }
598 
599 
600 
601 #endif
602 
604 
605 #endif
result_type operator()(size_t i) const
Definition: rtree.h:227
const Container & container
Definition: rtree.h:236
IndexableGetter getter
Definition: rtree.h:242
typename boost::geometry::index::indexable< typename Container::value_type > IndexableGetter
Definition: rtree.h:204
typename IndexableGetter::result_type result_type
Definition: rtree.h:209
IndexableGetterFromIndices(Container const &c)
Definition: rtree.h:219
#define DEAL_II_NAMESPACE_OPEN
Definition: config.h:474
#define DEAL_II_NAMESPACE_CLOSE
Definition: config.h:475
unsigned int level
Definition: grid_out.cc:4618
types::global_dof_index size_type
Definition: cuda_kernels.h:45
VectorType::value_type * begin(VectorType &V)
VectorType::value_type * end(VectorType &V)
boost::integer_range< IncrementableType > iota_view
Definition: iota_view.h:46
std::vector< BoundingBox< boost::geometry::dimension< typename Rtree::indexable_type >::value > > extract_rtree_level(const Rtree &tree, const unsigned int level)
RTree< typename ContainerType::size_type, IndexType, IndexableGetterFromIndices< ContainerType > > pack_rtree_of_indices(const ContainerType &container)
boost::geometry::index::rtree< LeafType, IndexType, IndexableGetter > RTree
Definition: rtree.h:144
RTree< typename LeafTypeIterator::value_type, IndexType, IndexableGetter > pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
Translator const & translator
Definition: rtree.h:354
std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > & boxes
Definition: rtree.h:369
void operator()(InternalNode const &node)
typename boost::geometry::index::detail::rtree::leaf< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type Leaf
Definition: rtree.h:336
const size_t target_level
Definition: rtree.h:364
typename boost::geometry::index::detail::rtree::internal_node< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type InternalNode
Definition: rtree.h:326
ExtractLevelVisitor(Translator const &translator, const unsigned int target_level, std::vector< BoundingBox< boost::geometry::dimension< Box >::value >> &boxes)
void operator()(Leaf const &)