Reference documentation for deal.II version Git e3a3ec7800 2020-08-07 14:08:19 +0200
\(\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 - 2020 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/index/rtree.hpp>
30 #include <boost/geometry/strategies/strategies.hpp>
32 
33 #include <memory>
34 
35 
37 
140 template <typename LeafType,
141  typename IndexType = boost::geometry::index::linear<16>,
142  typename IndexableGetter =
144 using RTree =
145  boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
146 
154 template <typename IndexType = boost::geometry::index::linear<16>,
155  typename LeafTypeIterator,
156  typename IndexableGetter = boost::geometry::index::indexable<
157  typename LeafTypeIterator::value_type>>
159 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
160 
171 template <typename IndexType = boost::geometry::index::linear<16>,
172  typename ContainerType,
173  typename IndexableGetter = boost::geometry::index::indexable<
174  typename ContainerType::value_type>>
176 pack_rtree(const ContainerType &container);
177 
196 template <typename Container>
198 {
199 public:
204  using IndexableGetter =
206 
210  using result_type = typename IndexableGetter::result_type;
211 
215  using size_t = typename Container::size_type;
216 
220  explicit IndexableGetterFromIndices(Container const &c)
221  : container(c)
222  {}
223 
228  operator()(size_t i) const
229  {
230  return getter(container[i]);
231  }
232 
233 private:
237  const Container &container;
238 
244 };
245 
276 template <typename IndexType = boost::geometry::index::linear<16>,
277  typename ContainerType>
278 RTree<typename ContainerType::size_type,
279  IndexType,
281 pack_rtree_of_indices(const ContainerType &container);
282 
295 template <typename Value,
296  typename Options,
297  typename Translator,
298  typename Box,
299  typename Allocators>
301  : public boost::geometry::index::detail::rtree::visitor<
302  Value,
303  typename Options::parameters_type,
304  Box,
305  Allocators,
306  typename Options::node_tag,
307  true>::type
308 {
313  inline ExtractLevelVisitor(
314  Translator const & translator,
315  const unsigned int target_level,
316  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes);
317 
321  using InternalNode =
322  typename boost::geometry::index::detail::rtree::internal_node<
323  Value,
324  typename Options::parameters_type,
325  Box,
326  Allocators,
327  typename Options::node_tag>::type;
328 
332  using Leaf = typename boost::geometry::index::detail::rtree::leaf<
333  Value,
334  typename Options::parameters_type,
335  Box,
336  Allocators,
337  typename Options::node_tag>::type;
338 
343  inline void
344  operator()(InternalNode const &node);
345 
349  inline void
350  operator()(Leaf const &);
351 
355  Translator const &translator;
356 
360  size_t level;
361 
365  const size_t target_level;
366 
370  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes;
371 };
372 
424 template <typename Rtree>
425 inline std::vector<BoundingBox<
426  boost::geometry::dimension<typename Rtree::indexable_type>::value>>
427 extract_rtree_level(const Rtree &tree, const unsigned int level);
428 
429 
430 
431 // Inline and template functions
432 #ifndef DOXYGEN
433 
434 template <typename IndexType,
435  typename LeafTypeIterator,
436  typename IndexableGetter>
438 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
439 {
440  return RTree<typename LeafTypeIterator::value_type,
441  IndexType,
443 }
444 
445 
446 
447 template <typename IndexType, typename ContainerType, typename IndexableGetter>
449 pack_rtree(const ContainerType &container)
450 {
451  return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
452  container.begin(), container.end());
453 }
454 
455 
456 
457 template <typename IndexType, typename ContainerType>
458 RTree<typename ContainerType::size_type,
459  IndexType,
461 pack_rtree_of_indices(const ContainerType &container)
462 {
464  typename ContainerType::size_type>
465  indices(0, container.size());
466  return RTree<typename ContainerType::size_type,
467  IndexType,
469  indices.begin(),
470  indices.end(),
471  IndexType(),
473 }
474 
475 
476 
477 template <typename Value,
478  typename Options,
479  typename Translator,
480  typename Box,
481  typename Allocators>
484  const Translator & translator,
485  const unsigned int target_level,
486  std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
487  : translator(translator)
488  , level(0)
489  , target_level(target_level)
490  , boxes(boxes)
491 {}
492 
493 
494 
495 template <typename Value,
496  typename Options,
497  typename Translator,
498  typename Box,
499  typename Allocators>
500 void
503 {
504  using ElmentsType =
505  typename boost::geometry::index::detail::rtree::elements_type<
506  InternalNode>::type;
507 
508  const auto &elements = boost::geometry::index::detail::rtree::elements(node);
509 
510  if (level == target_level)
511  {
512  const auto offset = boxes.size();
513  boxes.resize(offset + elements.size());
514 
515  unsigned int i = offset;
516  for (typename ElmentsType::const_iterator it = elements.begin();
517  it != elements.end();
518  ++it)
519  {
520  boost::geometry::convert(it->first, boxes[i]);
521  ++i;
522  }
523  return;
524  }
525 
526  const size_t level_backup = level;
527  ++level;
528 
529  for (typename ElmentsType::const_iterator it = elements.begin();
530  it != elements.end();
531  ++it)
532  {
533  boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
534  }
535 
536  level = level_backup;
537 }
538 
539 template <typename Value,
540  typename Options,
541  typename Translator,
542  typename Box,
543  typename Allocators>
544 void
547 {}
548 
549 
550 
551 template <typename Rtree>
552 inline std::vector<BoundingBox<
553  boost::geometry::dimension<typename Rtree::indexable_type>::value>>
554 extract_rtree_level(const Rtree &tree, const unsigned int level)
555 {
556  constexpr unsigned int dim =
557  boost::geometry::dimension<typename Rtree::indexable_type>::value;
558 
559  using RtreeView =
560  boost::geometry::index::detail::rtree::utilities::view<Rtree>;
561  RtreeView rtv(tree);
562 
563  std::vector<BoundingBox<dim>> boxes;
564 
565  if (rtv.depth() == 0)
566  {
567  // The below algorithm does not work for `rtv.depth()==0`, which might
568  // happen if the number entries in the tree is too small.
569  // In this case, simply return a single bounding box.
570  boxes.resize(1);
571  boost::geometry::convert(tree.bounds(), boxes[0]);
572  }
573  else
574  {
575  const unsigned int target_level =
576  std::min<unsigned int>(level, rtv.depth() - 1);
577 
578  ExtractLevelVisitor<typename RtreeView::value_type,
579  typename RtreeView::options_type,
580  typename RtreeView::translator_type,
581  typename RtreeView::box_type,
582  typename RtreeView::allocators_type>
583  extract_level_visitor(rtv.translator(), target_level, boxes);
584  rtv.apply_visitor(extract_level_visitor);
585  }
586 
587  return boxes;
588 }
589 
590 
591 
592 template <class Rtree>
593 unsigned int
594 n_levels(const Rtree &tree)
595 {
596  boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
597  return rtv.depth();
598 }
599 
600 
601 
602 #endif
603 
605 
606 #endif
RTree< typename ContainerType::size_type, IndexType, IndexableGetterFromIndices< ContainerType > > pack_rtree_of_indices(const ContainerType &container)
types::global_dof_index size_type
Definition: cuda_kernels.h:45
typename boost::geometry::index::indexable< typename Container::value_type > IndexableGetter
Definition: rtree.h:205
std::vector< BoundingBox< boost::geometry::dimension< typename Rtree::indexable_type >::value > > extract_rtree_level(const Rtree &tree, const unsigned int level)
ExtractLevelVisitor(Translator const &translator, const unsigned int target_level, std::vector< BoundingBox< boost::geometry::dimension< Box >::value >> &boxes)
IndexableGetter getter
Definition: rtree.h:243
boost::geometry::index::rtree< LeafType, IndexType, IndexableGetter > RTree
Definition: rtree.h:145
#define DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
Definition: config.h:376
result_type operator()(size_t i) const
Definition: rtree.h:228
RTree< typename LeafTypeIterator::value_type, IndexType, IndexableGetter > pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
IndexableGetterFromIndices(Container const &c)
Definition: rtree.h:220
boost::integer_range< IncrementableType > iota_view
Definition: iota_view.h:46
#define DEAL_II_NAMESPACE_CLOSE
Definition: config.h:363
unsigned int level
Definition: grid_out.cc:4341
VectorType::value_type * end(VectorType &V)
typename boost::geometry::index::detail::rtree::leaf< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type Leaf
Definition: rtree.h:337
const Container & container
Definition: rtree.h:237
const size_t target_level
Definition: rtree.h:365
#define DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
Definition: config.h:413
#define DEAL_II_NAMESPACE_OPEN
Definition: config.h:362
VectorType::value_type * begin(VectorType &V)
typename IndexableGetter::result_type result_type
Definition: rtree.h:210
void operator()(InternalNode const &node)
Translator const & translator
Definition: rtree.h:355
typename boost::geometry::index::detail::rtree::internal_node< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type InternalNode
Definition: rtree.h:327
std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > & boxes
Definition: rtree.h:370