Reference documentation for deal.II version GIT 3a483e2de5 2022-11-28 08:40: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 
29 #include <boost/geometry/algorithms/distance.hpp>
30 #include <boost/geometry/index/rtree.hpp>
31 #include <boost/geometry/strategies/strategies.hpp>
33 
34 #include <memory>
35 
36 
38 
141 template <typename LeafType,
142  typename IndexType = boost::geometry::index::linear<16>,
143  typename IndexableGetter =
145 using RTree =
146  boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
147 
155 template <typename IndexType = boost::geometry::index::linear<16>,
156  typename LeafTypeIterator,
157  typename IndexableGetter = boost::geometry::index::indexable<
158  typename LeafTypeIterator::value_type>>
160 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
161 
172 template <typename IndexType = boost::geometry::index::linear<16>,
173  typename ContainerType,
174  typename IndexableGetter = boost::geometry::index::indexable<
175  typename ContainerType::value_type>>
177 pack_rtree(const ContainerType &container);
178 
197 template <typename Container>
199 {
200 public:
207 
211  using result_type = typename IndexableGetter::result_type;
212 
216  using size_t = typename Container::size_type;
217 
221  explicit IndexableGetterFromIndices(Container const &c)
222  : container(c)
223  {}
224 
229  operator()(size_t i) const
230  {
231  return getter(container[i]);
232  }
233 
234 private:
238  const Container &container;
239 
245 };
246 
277 template <typename IndexType = boost::geometry::index::linear<16>,
278  typename ContainerType>
280  IndexType,
282 pack_rtree_of_indices(const ContainerType &container);
283 
296 template <typename Value,
297  typename Options,
298  typename Translator,
299  typename Box,
300  typename Allocators>
302  : public boost::geometry::index::detail::rtree::visitor<
303  Value,
304  typename Options::parameters_type,
305  Box,
306  Allocators,
307  typename Options::node_tag,
308  true>::type
309 {
315  Translator const & translator,
316  const unsigned int target_level,
317  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes);
318 
322  using InternalNode =
323  typename boost::geometry::index::detail::rtree::internal_node<
324  Value,
325  typename Options::parameters_type,
326  Box,
327  Allocators,
328  typename Options::node_tag>::type;
329 
333  using Leaf = typename boost::geometry::index::detail::rtree::leaf<
334  Value,
335  typename Options::parameters_type,
336  Box,
337  Allocators,
338  typename Options::node_tag>::type;
339 
344  inline void
345  operator()(InternalNode const &node);
346 
350  inline void
351  operator()(Leaf const &);
352 
356  Translator const &translator;
357 
361  size_t level;
362 
366  const size_t target_level;
367 
371  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes;
372 };
373 
425 template <typename Rtree>
426 inline std::vector<BoundingBox<
427  boost::geometry::dimension<typename Rtree::indexable_type>::value>>
428 extract_rtree_level(const Rtree &tree, const unsigned int level);
429 
430 
431 
432 // Inline and template functions
433 #ifndef DOXYGEN
434 
435 template <typename IndexType,
436  typename LeafTypeIterator,
437  typename IndexableGetter>
439 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
440 {
441  return RTree<typename LeafTypeIterator::value_type,
442  IndexType,
443  IndexableGetter>(begin, end);
444 }
445 
446 
447 
448 template <typename IndexType, typename ContainerType, typename IndexableGetter>
450 pack_rtree(const ContainerType &container)
451 {
452  return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
453  container.begin(), container.end());
454 }
455 
456 
457 
458 template <typename IndexType, typename ContainerType>
460  IndexType,
462 pack_rtree_of_indices(const ContainerType &container)
463 {
465  typename ContainerType::size_type>
466  indices(0, container.size());
467  return RTree<typename ContainerType::size_type,
468  IndexType,
470  indices.begin(),
471  indices.end(),
472  IndexType(),
474 }
475 
476 
477 
478 template <typename Value,
479  typename Options,
480  typename Translator,
481  typename Box,
482  typename Allocators>
485  const Translator & translator,
486  const unsigned int target_level,
487  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
488  : translator(translator)
489  , level(0)
490  , target_level(target_level)
491  , boxes(boxes)
492 {}
493 
494 
495 
496 template <typename Value,
497  typename Options,
498  typename Translator,
499  typename Box,
500  typename Allocators>
501 void
504 {
505  using ElmentsType =
506  typename boost::geometry::index::detail::rtree::elements_type<
507  InternalNode>::type;
508 
509  const auto &elements = boost::geometry::index::detail::rtree::elements(node);
510 
511  if (level == target_level)
512  {
513  const auto offset = boxes.size();
514  boxes.resize(offset + elements.size());
515 
516  unsigned int i = offset;
517  for (typename ElmentsType::const_iterator it = elements.begin();
518  it != elements.end();
519  ++it)
520  {
521  boost::geometry::convert(it->first, boxes[i]);
522  ++i;
523  }
524  return;
525  }
526 
527  const size_t level_backup = level;
528  ++level;
529 
530  for (typename ElmentsType::const_iterator it = elements.begin();
531  it != elements.end();
532  ++it)
533  {
534  boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
535  }
536 
537  level = level_backup;
538 }
539 
540 template <typename Value,
541  typename Options,
542  typename Translator,
543  typename Box,
544  typename Allocators>
545 void
548 {}
549 
550 
551 
552 template <typename Rtree>
553 inline std::vector<BoundingBox<
554  boost::geometry::dimension<typename Rtree::indexable_type>::value>>
555 extract_rtree_level(const Rtree &tree, const unsigned int level)
556 {
557  constexpr unsigned int dim =
558  boost::geometry::dimension<typename Rtree::indexable_type>::value;
559 
560  using RtreeView =
561  boost::geometry::index::detail::rtree::utilities::view<Rtree>;
562  RtreeView rtv(tree);
563 
564  std::vector<BoundingBox<dim>> boxes;
565 
566  if (rtv.depth() == 0)
567  {
568  // The below algorithm does not work for `rtv.depth()==0`, which might
569  // happen if the number entries in the tree is too small.
570  // In this case, simply return a single bounding box.
571  boxes.resize(1);
572  boost::geometry::convert(tree.bounds(), boxes[0]);
573  }
574  else
575  {
576  const unsigned int target_level =
577  std::min<unsigned int>(level, rtv.depth() - 1);
578 
579  ExtractLevelVisitor<typename RtreeView::value_type,
580  typename RtreeView::options_type,
581  typename RtreeView::translator_type,
582  typename RtreeView::box_type,
583  typename RtreeView::allocators_type>
584  extract_level_visitor(rtv.translator(), target_level, boxes);
585  rtv.apply_visitor(extract_level_visitor);
586  }
587 
588  return boxes;
589 }
590 
591 
592 
593 template <class Rtree>
594 unsigned int
595 n_levels(const Rtree &tree)
596 {
597  boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
598  return rtv.depth();
599 }
600 
601 
602 
603 #endif
604 
606 
607 #endif
result_type operator()(size_t i) const
Definition: rtree.h:229
const Container & container
Definition: rtree.h:238
IndexableGetter getter
Definition: rtree.h:244
typename boost::geometry::index::indexable< typename Container::value_type > IndexableGetter
Definition: rtree.h:206
typename IndexableGetter::result_type result_type
Definition: rtree.h:211
IndexableGetterFromIndices(Container const &c)
Definition: rtree.h:221
#define DEAL_II_NAMESPACE_OPEN
Definition: config.h:458
#define DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
Definition: config.h:472
#define DEAL_II_NAMESPACE_CLOSE
Definition: config.h:459
#define DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
Definition: config.h:512
unsigned int level
Definition: grid_out.cc:4608
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:146
RTree< typename LeafTypeIterator::value_type, IndexType, IndexableGetter > pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
Translator const & translator
Definition: rtree.h:356
std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > & boxes
Definition: rtree.h:371
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:338
const size_t target_level
Definition: rtree.h:366
typename boost::geometry::index::detail::rtree::internal_node< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type InternalNode
Definition: rtree.h:328
ExtractLevelVisitor(Translator const &translator, const unsigned int target_level, std::vector< BoundingBox< boost::geometry::dimension< Box >::value >> &boxes)
void operator()(Leaf const &)