Loading [MathJax]/extensions/TeX/newcommand.js
 Reference documentation for deal.II version 9.3.3
\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\}}
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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/algorithms/distance.hpp>
30
31#ifdef DEAL_II_BOOST_HAS_BROKEN_HEADER_DEPRECATIONS
32# define BOOST_ALLOW_DEPRECATED_HEADERS
33#endif
34#include <boost/geometry/index/rtree.hpp>
35#include <boost/geometry/strategies/strategies.hpp>
36#ifdef DEAL_II_BOOST_HAS_BROKEN_HEADER_DEPRECATIONS
37# undef BOOST_ALLOW_DEPRECATED_HEADERS
38#endif
40
41#include <memory>
42
43
45
148template <typename LeafType,
149 typename IndexType = boost::geometry::index::linear<16>,
150 typename IndexableGetter =
152using RTree =
153 boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
154
162template <typename IndexType = boost::geometry::index::linear<16>,
163 typename LeafTypeIterator,
164 typename IndexableGetter = boost::geometry::index::indexable<
165 typename LeafTypeIterator::value_type>>
167pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
168
179template <typename IndexType = boost::geometry::index::linear<16>,
180 typename ContainerType,
181 typename IndexableGetter = boost::geometry::index::indexable<
182 typename ContainerType::value_type>>
184pack_rtree(const ContainerType &container);
185
204template <typename Container>
206{
207public:
214
218 using result_type = typename IndexableGetter::result_type;
219
223 using size_t = typename Container::size_type;
224
228 explicit IndexableGetterFromIndices(Container const &c)
229 : container(c)
230 {}
231
236 operator()(size_t i) const
237 {
238 return getter(container[i]);
239 }
240
241private:
245 const Container &container;
246
252};
253
284template <typename IndexType = boost::geometry::index::linear<16>,
285 typename ContainerType>
287 IndexType,
289pack_rtree_of_indices(const ContainerType &container);
290
303template <typename Value,
304 typename Options,
305 typename Translator,
306 typename Box,
307 typename Allocators>
309 : public boost::geometry::index::detail::rtree::visitor<
310 Value,
311 typename Options::parameters_type,
312 Box,
313 Allocators,
314 typename Options::node_tag,
315 true>::type
316{
322 Translator const & translator,
323 const unsigned int target_level,
324 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes);
325
330 typename boost::geometry::index::detail::rtree::internal_node<
331 Value,
332 typename Options::parameters_type,
333 Box,
334 Allocators,
335 typename Options::node_tag>::type;
336
340 using Leaf = typename boost::geometry::index::detail::rtree::leaf<
341 Value,
342 typename Options::parameters_type,
343 Box,
344 Allocators,
345 typename Options::node_tag>::type;
346
351 inline void
353
357 inline void
358 operator()(Leaf const &);
359
363 Translator const &translator;
364
368 size_t level;
369
373 const size_t target_level;
374
378 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes;
379};
380
432template <typename Rtree>
433inline std::vector<BoundingBox<
434 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
435extract_rtree_level(const Rtree &tree, const unsigned int level);
436
437
438
439// Inline and template functions
440#ifndef DOXYGEN
441
442template <typename IndexType,
443 typename LeafTypeIterator,
444 typename IndexableGetter>
446pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
447{
448 return RTree<typename LeafTypeIterator::value_type,
449 IndexType,
450 IndexableGetter>(begin, end);
451}
452
453
454
455template <typename IndexType, typename ContainerType, typename IndexableGetter>
457pack_rtree(const ContainerType &container)
458{
459 return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
460 container.begin(), container.end());
461}
462
463
464
465template <typename IndexType, typename ContainerType>
467 IndexType,
469pack_rtree_of_indices(const ContainerType &container)
470{
473 indices(0, container.size());
474 return RTree<typename ContainerType::size_type,
475 IndexType,
477 indices.begin(),
478 indices.end(),
479 IndexType(),
481}
482
483
484
485template <typename Value,
486 typename Options,
487 typename Translator,
488 typename Box,
489 typename Allocators>
492 const Translator & translator,
493 const unsigned int target_level,
494 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
495 : translator(translator)
496 , level(0)
497 , target_level(target_level)
498 , boxes(boxes)
499{}
500
501
502
503template <typename Value,
504 typename Options,
505 typename Translator,
506 typename Box,
507 typename Allocators>
508void
511{
512 using ElmentsType =
513 typename boost::geometry::index::detail::rtree::elements_type<
514 InternalNode>::type;
515
516 const auto &elements = boost::geometry::index::detail::rtree::elements(node);
517
518 if (level == target_level)
519 {
520 const auto offset = boxes.size();
521 boxes.resize(offset + elements.size());
522
523 unsigned int i = offset;
524 for (typename ElmentsType::const_iterator it = elements.begin();
525 it != elements.end();
526 ++it)
527 {
528 boost::geometry::convert(it->first, boxes[i]);
529 ++i;
530 }
531 return;
532 }
533
534 const size_t level_backup = level;
535 ++level;
536
537 for (typename ElmentsType::const_iterator it = elements.begin();
538 it != elements.end();
539 ++it)
540 {
541 boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
542 }
543
544 level = level_backup;
545}
546
547template <typename Value,
548 typename Options,
549 typename Translator,
550 typename Box,
551 typename Allocators>
552void
555{}
556
557
558
559template <typename Rtree>
560inline std::vector<BoundingBox<
561 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
562extract_rtree_level(const Rtree &tree, const unsigned int level)
563{
564 constexpr unsigned int dim =
565 boost::geometry::dimension<typename Rtree::indexable_type>::value;
566
567 using RtreeView =
568 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
569 RtreeView rtv(tree);
570
571 std::vector<BoundingBox<dim>> boxes;
572
573 if (rtv.depth() == 0)
574 {
575 // The below algorithm does not work for `rtv.depth()==0`, which might
576 // happen if the number entries in the tree is too small.
577 // In this case, simply return a single bounding box.
578 boxes.resize(1);
579 boost::geometry::convert(tree.bounds(), boxes[0]);
580 }
581 else
582 {
583 const unsigned int target_level =
584 std::min<unsigned int>(level, rtv.depth() - 1);
585
586 ExtractLevelVisitor<typename RtreeView::value_type,
587 typename RtreeView::options_type,
588 typename RtreeView::translator_type,
589 typename RtreeView::box_type,
590 typename RtreeView::allocators_type>
591 extract_level_visitor(rtv.translator(), target_level, boxes);
592 rtv.apply_visitor(extract_level_visitor);
593 }
594
595 return boxes;
596}
597
598
599
600template <class Rtree>
601unsigned int
602n_levels(const Rtree &tree)
603{
604 boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
605 return rtv.depth();
606}
607
608
609
610#endif
611
613
614#endif
result_type operator()(size_t i) const
Definition: rtree.h:236
const Container & container
Definition: rtree.h:245
typename Container::size_type size_t
Definition: rtree.h:223
IndexableGetter getter
Definition: rtree.h:251
typename boost::geometry::index::indexable< typename Container::value_type > IndexableGetter
Definition: rtree.h:213
typename IndexableGetter::result_type result_type
Definition: rtree.h:218
IndexableGetterFromIndices(Container const &c)
Definition: rtree.h:228
#define DEAL_II_NAMESPACE_OPEN
Definition: config.h:402
#define DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
Definition: config.h:416
#define DEAL_II_NAMESPACE_CLOSE
Definition: config.h:403
#define DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
Definition: config.h:454
unsigned int level
Definition: grid_out.cc:4590
types::global_dof_index size_type
Definition: cuda_kernels.h:45
VectorType::value_type * end(VectorType &V)
VectorType::value_type * begin(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)
boost::geometry::index::rtree< LeafType, IndexType, IndexableGetter > RTree
Definition: rtree.h:153
RTree< typename LeafTypeIterator::value_type, IndexType, IndexableGetter > pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
RTree< typename ContainerType::size_type, IndexType, IndexableGetterFromIndices< ContainerType > > pack_rtree_of_indices(const ContainerType &container)
Translator const & translator
Definition: rtree.h:363
std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > & boxes
Definition: rtree.h:378
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:345
const size_t target_level
Definition: rtree.h:373
typename boost::geometry::index::detail::rtree::internal_node< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type InternalNode
Definition: rtree.h:335
ExtractLevelVisitor(Translator const &translator, const unsigned int target_level, std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > &boxes)
void operator()(Leaf const &)