Reference documentation for deal.II version GIT relicensing-29-g1d56f85c36 2024-02-28 12: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\}}\)
Loading...
Searching...
No Matches
rtree.h
Go to the documentation of this file.
1// ------------------------------------------------------------------------
2//
3// SPDX-License-Identifier: LGPL-2.1-or-later
4// Copyright (C) 2018 - 2023 by the deal.II authors
5//
6// This file is part of the deal.II library.
7//
8// Part of the source code is dual licensed under Apache-2.0 WITH
9// LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10// governing the source code and code contributions can be found in
11// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12//
13// ------------------------------------------------------------------------
14
15#ifndef dealii_numerics_rtree_h
16#define dealii_numerics_rtree_h
17
18#include <deal.II/base/config.h>
19
20#include <deal.II/base/point.h>
22
26
27#include <boost/geometry/algorithms/distance.hpp>
28#include <boost/geometry/index/rtree.hpp>
29#include <boost/geometry/strategies/strategies.hpp>
30
31#include <memory>
32
33
35
138template <typename LeafType,
139 typename IndexType = boost::geometry::index::linear<16>,
140 typename IndexableGetter =
142using RTree =
143 boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
144
152template <typename IndexType = boost::geometry::index::linear<16>,
153 typename LeafTypeIterator,
154 typename IndexableGetter = boost::geometry::index::indexable<
155 typename LeafTypeIterator::value_type>>
157pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
158
169template <typename IndexType = boost::geometry::index::linear<16>,
170 typename ContainerType,
171 typename IndexableGetter = boost::geometry::index::indexable<
172 typename ContainerType::value_type>>
174pack_rtree(const ContainerType &container);
175
194template <typename Container>
196{
197public:
204
208 using result_type = typename IndexableGetter::result_type;
209
213 using size_t = typename Container::size_type;
214
218 explicit IndexableGetterFromIndices(const Container &c)
219 : container(c)
220 {}
221
226 operator()(size_t i) const
227 {
228 return getter(container[i]);
229 }
230
231private:
235 const Container &container;
236
242};
243
298template <typename IndexType = boost::geometry::index::linear<16>,
299 typename ContainerType>
300RTree<typename ContainerType::size_type,
301 IndexType,
303pack_rtree_of_indices(const ContainerType &container);
304
317template <typename Value,
318 typename Options,
319 typename Translator,
320 typename Box,
321 typename Allocators>
323 : public boost::geometry::index::detail::rtree::visitor<
324 Value,
325 typename Options::parameters_type,
326 Box,
327 Allocators,
328 typename Options::node_tag,
329 true>::type
330{
336 const Translator &translator,
337 const unsigned int target_level,
338 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes);
339
344 typename boost::geometry::index::detail::rtree::internal_node<
345 Value,
346 typename Options::parameters_type,
347 Box,
348 Allocators,
349 typename Options::node_tag>::type;
350
354 using Leaf = typename boost::geometry::index::detail::rtree::leaf<
355 Value,
356 typename Options::parameters_type,
357 Box,
358 Allocators,
359 typename Options::node_tag>::type;
360
365 inline void
367
371 inline void
372 operator()(const Leaf &);
373
377 const Translator &translator;
378
382 size_t level;
383
387 const size_t target_level;
388
392 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes;
393};
394
446template <typename Rtree>
447inline std::vector<BoundingBox<
448 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
449extract_rtree_level(const Rtree &tree, const unsigned int level);
450
451
452
462template <typename Rtree>
463std::vector<std::vector<BoundingBox<
464 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
465extract_children_of_level(const Rtree &tree, const unsigned int level);
466
467
468
469// Inline and template functions
470#ifndef DOXYGEN
471
472template <typename IndexType,
473 typename LeafTypeIterator,
474 typename IndexableGetter>
476pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
477{
478 return RTree<typename LeafTypeIterator::value_type,
479 IndexType,
480 IndexableGetter>(begin, end);
481}
482
483
484
485template <typename IndexType, typename ContainerType, typename IndexableGetter>
487pack_rtree(const ContainerType &container)
488{
489 return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
490 container.begin(), container.end());
491}
492
493
494
495template <typename IndexType, typename ContainerType>
496RTree<typename ContainerType::size_type,
497 IndexType,
499pack_rtree_of_indices(const ContainerType &container)
500{
501 std_cxx20::ranges::iota_view<typename ContainerType::size_type,
502 typename ContainerType::size_type>
503 indices(0, container.size());
504 return RTree<typename ContainerType::size_type,
505 IndexType,
507 indices.begin(),
508 indices.end(),
509 IndexType(),
511}
512
513
514
515template <typename Value,
516 typename Options,
517 typename Translator,
518 typename Box,
519 typename Allocators>
522 const Translator &translator,
523 const unsigned int target_level,
524 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
525 : translator(translator)
526 , level(0)
527 , target_level(target_level)
528 , boxes(boxes)
529{}
530
531
532
533template <typename Value,
534 typename Options,
535 typename Translator,
536 typename Box,
537 typename Allocators>
538void
541{
542 using ElementsType =
543 typename boost::geometry::index::detail::rtree::elements_type<
544 InternalNode>::type;
545
546 const auto &elements = boost::geometry::index::detail::rtree::elements(node);
547
548 if (level == target_level)
549 {
550 const auto offset = boxes.size();
551 boxes.resize(offset + elements.size());
552
553 unsigned int i = offset;
554 for (typename ElementsType::const_iterator it = elements.begin();
555 it != elements.end();
556 ++it)
557 {
558 boost::geometry::convert(it->first, boxes[i]);
559 ++i;
560 }
561 return;
562 }
563
564 const size_t level_backup = level;
565 ++level;
566
567 for (typename ElementsType::const_iterator it = elements.begin();
568 it != elements.end();
569 ++it)
570 {
571 boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
572 }
573
574 level = level_backup;
575}
576
577template <typename Value,
578 typename Options,
579 typename Translator,
580 typename Box,
581 typename Allocators>
582void
585{}
586
587
588
589template <typename Rtree>
590inline std::vector<BoundingBox<
591 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
592extract_rtree_level(const Rtree &tree, const unsigned int level)
593{
594 constexpr unsigned int dim =
595 boost::geometry::dimension<typename Rtree::indexable_type>::value;
596
597 using RtreeView =
598 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
599 RtreeView rtv(tree);
600
601 std::vector<BoundingBox<dim>> boxes;
602
603 if (rtv.depth() == 0)
604 {
605 // The below algorithm does not work for `rtv.depth()==0`, which might
606 // happen if the number entries in the tree is too small.
607 // In this case, simply return a single bounding box.
608 boxes.resize(1);
609 boost::geometry::convert(tree.bounds(), boxes[0]);
610 }
611 else
612 {
613 const unsigned int target_level =
614 std::min<unsigned int>(level, rtv.depth() - 1);
615
616 ExtractLevelVisitor<typename RtreeView::value_type,
617 typename RtreeView::options_type,
618 typename RtreeView::translator_type,
619 typename RtreeView::box_type,
620 typename RtreeView::allocators_type>
621 extract_level_visitor(rtv.translator(), target_level, boxes);
622 rtv.apply_visitor(extract_level_visitor);
623 }
624
625 return boxes;
626}
627
628
629
630template <class Rtree>
631unsigned int
632n_levels(const Rtree &tree)
633{
634 boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
635 return rtv.depth();
636}
637
638
639template <typename Value,
640 typename Options,
641 typename Translator,
642 typename Box,
643 typename Allocators>
644struct NodeVisitor : public boost::geometry::index::detail::rtree::visitor<
645 Value,
646 typename Options::parameters_type,
647 Box,
648 Allocators,
649 typename Options::node_tag,
650 true>::type
651{
652 inline NodeVisitor(
653 const Translator &translator,
654 unsigned int target_level,
655 std::vector<
656 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>> &boxes);
657
658
662 using InternalNode =
663 typename boost::geometry::index::detail::rtree::internal_node<
664 Value,
665 typename Options::parameters_type,
666 Box,
667 Allocators,
668 typename Options::node_tag>::type;
669
673 using Leaf = typename boost::geometry::index::detail::rtree::leaf<
674 Value,
675 typename Options::parameters_type,
676 Box,
677 Allocators,
678 typename Options::node_tag>::type;
679
684 inline void
685 operator()(const InternalNode &node);
686
690 inline void
691 operator()(const Leaf &);
692
696 const Translator &translator;
697
701 size_t level;
702
707 size_t node_counter;
708
713 const size_t target_level;
714
720 std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>>
721 &boxes_in_boxes;
722};
723
724
725
726template <typename Value,
727 typename Options,
728 typename Translator,
729 typename Box,
730 typename Allocators>
731NodeVisitor<Value, Options, Translator, Box, Allocators>::NodeVisitor(
732 const Translator &translator,
733 const unsigned int target_level,
734 std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>>
735 &bb_in_boxes)
736 : translator(translator)
737 , level(0)
738 , node_counter(0)
739 , target_level(target_level)
740 , boxes_in_boxes(bb_in_boxes)
741{}
742
743
744
745template <typename Value,
746 typename Options,
747 typename Translator,
748 typename Box,
749 typename Allocators>
750void
751NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
752 const NodeVisitor::InternalNode &node)
753{
754 using elements_type =
755 typename boost::geometry::index::detail::rtree::elements_type<
756 InternalNode>::type; // pairs of bounding box and pointer to child node
757 const elements_type &elements =
758 boost::geometry::index::detail::rtree::elements(node);
759
760 if (level == target_level)
761 {
762 const unsigned int n_children = elements.size();
763 const auto offset = boxes_in_boxes.size();
764 boxes_in_boxes.resize(offset + n_children);
765 }
766
767 if (level == target_level + 1)
768 {
769 // I have now access to children of level target_level
770 boxes_in_boxes[node_counter].resize(elements.size()); // number of bboxes
771 unsigned int i = 0;
772 for (typename elements_type::const_iterator it = elements.begin();
773 it != elements.end();
774 ++it)
775 {
776 boost::geometry::convert(it->first, boxes_in_boxes[node_counter][i]);
777 ++i;
778 }
779 // Children have been stored, go to the next parent.
780 ++node_counter;
781 return;
782 }
783
784 size_t level_backup = level;
785 ++level;
786
787 for (typename elements_type::const_iterator it = elements.begin();
788 it != elements.end();
789 ++it)
790 {
791 boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
792 }
793
794 level = level_backup;
795}
796
797
798
799template <typename Value,
800 typename Options,
801 typename Translator,
802 typename Box,
803 typename Allocators>
804void
805NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
806 const NodeVisitor::Leaf &)
807{
808 // No children for leaf nodes.
809 boxes_in_boxes.clear();
810}
811
812template <typename Rtree>
813inline std::vector<std::vector<BoundingBox<
814 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
815extract_children_of_level(const Rtree &tree, const unsigned int level)
816{
817 constexpr unsigned int dim =
818 boost::geometry::dimension<typename Rtree::indexable_type>::value;
819
820 using RtreeView =
821 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
822 RtreeView rtv(tree);
823
824 std::vector<std::vector<BoundingBox<dim>>> boxes_in_boxes;
825
826 if (rtv.depth() == 0)
827 {
828 // The below algorithm does not work for `rtv.depth()==0`, which might
829 // happen if the number entries in the tree is too small.
830 // In this case, simply return a single bounding box.
831 boxes_in_boxes.resize(1);
832 boxes_in_boxes[0].resize(1);
833 boost::geometry::convert(tree.bounds(), boxes_in_boxes[0][0]);
834 }
835 else
836 {
837 const unsigned int target_level =
838 std::min<unsigned int>(level, rtv.depth() - 1);
839
840 NodeVisitor<typename RtreeView::value_type,
841 typename RtreeView::options_type,
842 typename RtreeView::translator_type,
843 typename RtreeView::box_type,
844 typename RtreeView::allocators_type>
845 node_visitor(rtv.translator(), target_level, boxes_in_boxes);
846 rtv.apply_visitor(node_visitor);
847 }
848
849 return boxes_in_boxes;
850}
851
852
853
854#endif
855
857
858#endif
result_type operator()(size_t i) const
Definition rtree.h:226
const Container & container
Definition rtree.h:235
typename Container::size_type size_t
Definition rtree.h:213
IndexableGetter getter
Definition rtree.h:241
typename boost::geometry::index::indexable< typename Container::value_type > IndexableGetter
Definition rtree.h:203
typename IndexableGetter::result_type result_type
Definition rtree.h:208
IndexableGetterFromIndices(const Container &c)
Definition rtree.h:218
#define DEAL_II_NAMESPACE_OPEN
Definition config.h:502
#define DEAL_II_NAMESPACE_CLOSE
Definition config.h:503
unsigned int level
Definition grid_out.cc:4616
boost::integer_range< IncrementableType > iota_view
Definition iota_view.h:45
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:143
std::vector< std::vector< BoundingBox< boost::geometry::dimension< typename Rtree::indexable_type >::value > > > extract_children_of_level(const Rtree &tree, const unsigned int level)
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)
void operator()(const Leaf &)
void operator()(const InternalNode &node)
std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > & boxes
Definition rtree.h:392
typename boost::geometry::index::detail::rtree::leaf< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type Leaf
Definition rtree.h:359
const size_t target_level
Definition rtree.h:387
typename boost::geometry::index::detail::rtree::internal_node< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type InternalNode
Definition rtree.h:349
const Translator & translator
Definition rtree.h:377
ExtractLevelVisitor(const Translator &translator, const unsigned int target_level, std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > &boxes)