Reference documentation for deal.II version 9.5.0
\(\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\}}\)
Loading...
Searching...
No Matches
rtree.h
Go to the documentation of this file.
1// ---------------------------------------------------------------------
2//
3// Copyright (C) 2017 - 2023 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
139template <typename LeafType,
140 typename IndexType = boost::geometry::index::linear<16>,
141 typename IndexableGetter =
143using RTree =
144 boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
145
153template <typename IndexType = boost::geometry::index::linear<16>,
154 typename LeafTypeIterator,
155 typename IndexableGetter = boost::geometry::index::indexable<
156 typename LeafTypeIterator::value_type>>
158pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
159
170template <typename IndexType = boost::geometry::index::linear<16>,
171 typename ContainerType,
172 typename IndexableGetter = boost::geometry::index::indexable<
173 typename ContainerType::value_type>>
175pack_rtree(const ContainerType &container);
176
195template <typename Container>
197{
198public:
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
232private:
236 const Container &container;
237
243};
244
275template <typename IndexType = boost::geometry::index::linear<16>,
276 typename ContainerType>
277RTree<typename ContainerType::size_type,
278 IndexType,
280pack_rtree_of_indices(const ContainerType &container);
281
294template <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
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
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
423template <typename Rtree>
424inline std::vector<BoundingBox<
425 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
426extract_rtree_level(const Rtree &tree, const unsigned int level);
427
428
429
430// Inline and template functions
431#ifndef DOXYGEN
432
433template <typename IndexType,
434 typename LeafTypeIterator,
435 typename IndexableGetter>
437pack_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
446template <typename IndexType, typename ContainerType, typename IndexableGetter>
448pack_rtree(const ContainerType &container)
449{
450 return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
451 container.begin(), container.end());
452}
453
454
455
456template <typename IndexType, typename ContainerType>
457RTree<typename ContainerType::size_type,
458 IndexType,
460pack_rtree_of_indices(const ContainerType &container)
461{
462 std_cxx20::ranges::iota_view<typename ContainerType::size_type,
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
476template <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
494template <typename Value,
495 typename Options,
496 typename Translator,
497 typename Box,
498 typename Allocators>
499void
502{
503 using ElementsType =
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 ElementsType::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 ElementsType::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
538template <typename Value,
539 typename Options,
540 typename Translator,
541 typename Box,
542 typename Allocators>
543void
546{}
547
548
549
550template <typename Rtree>
551inline std::vector<BoundingBox<
552 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
553extract_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
591template <class Rtree>
592unsigned int
593n_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
typename Container::size_type size_t
Definition rtree.h:214
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:472
#define DEAL_II_NAMESPACE_CLOSE
Definition config.h:473
unsigned int level
Definition grid_out.cc:4618
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:144
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: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 &)