Reference documentation for deal.II version GIT relicensing-1062-gc06da148b8 2024-07-15 19:20: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 - 2024 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
28#include <boost/geometry/algorithms/distance.hpp>
29#include <boost/geometry/index/rtree.hpp>
30#include <boost/geometry/strategies/strategies.hpp>
32
33#include <memory>
34
35
37
140template <typename LeafType,
141 typename IndexType = boost::geometry::index::linear<16>,
142 typename IndexableGetter =
144using RTree =
145 boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
146
154template <typename IndexType = boost::geometry::index::linear<16>,
155 typename LeafTypeIterator,
156 typename IndexableGetter = boost::geometry::index::indexable<
157 typename LeafTypeIterator::value_type>>
159pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
160
171template <typename IndexType = boost::geometry::index::linear<16>,
172 typename ContainerType,
173 typename IndexableGetter = boost::geometry::index::indexable<
174 typename ContainerType::value_type>>
176pack_rtree(const ContainerType &container);
177
196template <typename Container>
198{
199public:
206
210 using result_type = typename IndexableGetter::result_type;
211
215 using size_t = typename Container::size_type;
216
220 explicit IndexableGetterFromIndices(const Container &c)
221 : container(c)
222 {}
223
228 operator()(size_t i) const
229 {
230 return getter(container[i]);
231 }
232
233private:
237 const Container &container;
238
244};
245
300template <typename IndexType = boost::geometry::index::linear<16>,
301 typename ContainerType>
302RTree<typename ContainerType::size_type,
303 IndexType,
305pack_rtree_of_indices(const ContainerType &container);
306
319template <typename Value,
320 typename Options,
321 typename Translator,
322 typename Box,
323 typename Allocators>
325 : public boost::geometry::index::detail::rtree::visitor<
326 Value,
327 typename Options::parameters_type,
328 Box,
329 Allocators,
330 typename Options::node_tag,
331 true>::type
332{
338 const Translator &translator,
339 const unsigned int target_level,
340 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes);
341
346 typename boost::geometry::index::detail::rtree::internal_node<
347 Value,
348 typename Options::parameters_type,
349 Box,
350 Allocators,
351 typename Options::node_tag>::type;
352
356 using Leaf = typename boost::geometry::index::detail::rtree::leaf<
357 Value,
358 typename Options::parameters_type,
359 Box,
360 Allocators,
361 typename Options::node_tag>::type;
362
367 inline void
369
373 inline void
374 operator()(const Leaf &);
375
379 const Translator &translator;
380
384 size_t level;
385
389 const size_t target_level;
390
394 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes;
395};
396
448template <typename Rtree>
449inline std::vector<BoundingBox<
450 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
451extract_rtree_level(const Rtree &tree, const unsigned int level);
452
453
454
464template <typename Rtree>
465std::vector<std::vector<BoundingBox<
466 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
467extract_children_of_level(const Rtree &tree, const unsigned int level);
468
469
470
471// Inline and template functions
472#ifndef DOXYGEN
473
474template <typename IndexType,
475 typename LeafTypeIterator,
476 typename IndexableGetter>
478pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
479{
480 return RTree<typename LeafTypeIterator::value_type,
481 IndexType,
482 IndexableGetter>(begin, end);
483}
484
485
486
487template <typename IndexType, typename ContainerType, typename IndexableGetter>
489pack_rtree(const ContainerType &container)
490{
491 return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>(
492 container.begin(), container.end());
493}
494
495
496
497template <typename IndexType, typename ContainerType>
498RTree<typename ContainerType::size_type,
499 IndexType,
501pack_rtree_of_indices(const ContainerType &container)
502{
503 // We need an array that holds the indices we want to pack. The rtree
504 // implementation in BOOST, for reasons not entirely clear, insists
505 // on using a reference to the elements of the range. This is fine if
506 // the indices are stored in a container, so that's what we do.
507 // (It would be nice if we could just pass a std::ranges::iota_view
508 // instead, but that has no nested 'reference' type, and this then
509 // trips up BOOST rtree.)
510 std::vector<typename ContainerType::size_type> indices(container.size());
511 for (typename ContainerType::size_type i = 0; i < container.size(); ++i)
512 indices[i] = i;
513
514 return RTree<typename ContainerType::size_type,
515 IndexType,
517 indices.begin(),
518 indices.end(),
519 IndexType(),
521}
522
523
524
525template <typename Value,
526 typename Options,
527 typename Translator,
528 typename Box,
529 typename Allocators>
532 const Translator &translator,
533 const unsigned int target_level,
534 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
535 : translator(translator)
536 , level(0)
537 , target_level(target_level)
538 , boxes(boxes)
539{}
540
541
542
543template <typename Value,
544 typename Options,
545 typename Translator,
546 typename Box,
547 typename Allocators>
548void
551{
552 using ElementsType =
553 typename boost::geometry::index::detail::rtree::elements_type<
554 InternalNode>::type;
555
556 const auto &elements = boost::geometry::index::detail::rtree::elements(node);
557
558 if (level == target_level)
559 {
560 const auto offset = boxes.size();
561 boxes.resize(offset + elements.size());
562
563 unsigned int i = offset;
564 for (typename ElementsType::const_iterator it = elements.begin();
565 it != elements.end();
566 ++it)
567 {
568 boost::geometry::convert(it->first, boxes[i]);
569 ++i;
570 }
571 return;
572 }
573
574 const size_t level_backup = level;
575 ++level;
576
577 for (typename ElementsType::const_iterator it = elements.begin();
578 it != elements.end();
579 ++it)
580 {
581 boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
582 }
583
584 level = level_backup;
585}
586
587template <typename Value,
588 typename Options,
589 typename Translator,
590 typename Box,
591 typename Allocators>
592void
595{}
596
597
598
599template <typename Rtree>
600inline std::vector<BoundingBox<
601 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
602extract_rtree_level(const Rtree &tree, const unsigned int level)
603{
604 constexpr unsigned int dim =
605 boost::geometry::dimension<typename Rtree::indexable_type>::value;
606
607 using RtreeView =
608 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
609 RtreeView rtv(tree);
610
611 std::vector<BoundingBox<dim>> boxes;
612
613 if (rtv.depth() == 0)
614 {
615 // The below algorithm does not work for `rtv.depth()==0`, which might
616 // happen if the number entries in the tree is too small.
617 // In this case, simply return a single bounding box.
618 boxes.resize(1);
619 boost::geometry::convert(tree.bounds(), boxes[0]);
620 }
621 else
622 {
623 const unsigned int target_level =
624 std::min<unsigned int>(level, rtv.depth() - 1);
625
626 ExtractLevelVisitor<typename RtreeView::value_type,
627 typename RtreeView::options_type,
628 typename RtreeView::translator_type,
629 typename RtreeView::box_type,
630 typename RtreeView::allocators_type>
631 extract_level_visitor(rtv.translator(), target_level, boxes);
632 rtv.apply_visitor(extract_level_visitor);
633 }
634
635 return boxes;
636}
637
638
639
640template <class Rtree>
641unsigned int
642n_levels(const Rtree &tree)
643{
644 boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
645 return rtv.depth();
646}
647
648
649template <typename Value,
650 typename Options,
651 typename Translator,
652 typename Box,
653 typename Allocators>
654struct NodeVisitor : public boost::geometry::index::detail::rtree::visitor<
655 Value,
656 typename Options::parameters_type,
657 Box,
658 Allocators,
659 typename Options::node_tag,
660 true>::type
661{
662 inline NodeVisitor(
663 const Translator &translator,
664 unsigned int target_level,
665 std::vector<
666 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>> &boxes);
667
668
672 using InternalNode =
673 typename boost::geometry::index::detail::rtree::internal_node<
674 Value,
675 typename Options::parameters_type,
676 Box,
677 Allocators,
678 typename Options::node_tag>::type;
679
683 using Leaf = typename boost::geometry::index::detail::rtree::leaf<
684 Value,
685 typename Options::parameters_type,
686 Box,
687 Allocators,
688 typename Options::node_tag>::type;
689
694 inline void
695 operator()(const InternalNode &node);
696
700 inline void
701 operator()(const Leaf &);
702
706 const Translator &translator;
707
711 size_t level;
712
717 size_t node_counter;
718
723 const size_t target_level;
724
730 std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>>
731 &boxes_in_boxes;
732};
733
734
735
736template <typename Value,
737 typename Options,
738 typename Translator,
739 typename Box,
740 typename Allocators>
741NodeVisitor<Value, Options, Translator, Box, Allocators>::NodeVisitor(
742 const Translator &translator,
743 const unsigned int target_level,
744 std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>>
745 &bb_in_boxes)
746 : translator(translator)
747 , level(0)
748 , node_counter(0)
749 , target_level(target_level)
750 , boxes_in_boxes(bb_in_boxes)
751{}
752
753
754
755template <typename Value,
756 typename Options,
757 typename Translator,
758 typename Box,
759 typename Allocators>
760void
761NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
762 const NodeVisitor::InternalNode &node)
763{
764 using elements_type =
765 typename boost::geometry::index::detail::rtree::elements_type<
766 InternalNode>::type; // pairs of bounding box and pointer to child node
767 const elements_type &elements =
768 boost::geometry::index::detail::rtree::elements(node);
769
770 if (level == target_level)
771 {
772 const unsigned int n_children = elements.size();
773 const auto offset = boxes_in_boxes.size();
774 boxes_in_boxes.resize(offset + n_children);
775 }
776
777 if (level == target_level + 1)
778 {
779 // I have now access to children of level target_level
780 boxes_in_boxes[node_counter].resize(elements.size()); // number of bboxes
781 unsigned int i = 0;
782 for (typename elements_type::const_iterator it = elements.begin();
783 it != elements.end();
784 ++it)
785 {
786 boost::geometry::convert(it->first, boxes_in_boxes[node_counter][i]);
787 ++i;
788 }
789 // Children have been stored, go to the next parent.
790 ++node_counter;
791 return;
792 }
793
794 size_t level_backup = level;
795 ++level;
796
797 for (typename elements_type::const_iterator it = elements.begin();
798 it != elements.end();
799 ++it)
800 {
801 boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
802 }
803
804 level = level_backup;
805}
806
807
808
809template <typename Value,
810 typename Options,
811 typename Translator,
812 typename Box,
813 typename Allocators>
814void
815NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
816 const NodeVisitor::Leaf &)
817{
818 // No children for leaf nodes.
819 boxes_in_boxes.clear();
820}
821
822template <typename Rtree>
823inline std::vector<std::vector<BoundingBox<
824 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
825extract_children_of_level(const Rtree &tree, const unsigned int level)
826{
827 constexpr unsigned int dim =
828 boost::geometry::dimension<typename Rtree::indexable_type>::value;
829
830 using RtreeView =
831 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
832 RtreeView rtv(tree);
833
834 std::vector<std::vector<BoundingBox<dim>>> boxes_in_boxes;
835
836 if (rtv.depth() == 0)
837 {
838 // The below algorithm does not work for `rtv.depth()==0`, which might
839 // happen if the number entries in the tree is too small.
840 // In this case, simply return a single bounding box.
841 boxes_in_boxes.resize(1);
842 boxes_in_boxes[0].resize(1);
843 boost::geometry::convert(tree.bounds(), boxes_in_boxes[0][0]);
844 }
845 else
846 {
847 const unsigned int target_level =
848 std::min<unsigned int>(level, rtv.depth() - 1);
849
850 NodeVisitor<typename RtreeView::value_type,
851 typename RtreeView::options_type,
852 typename RtreeView::translator_type,
853 typename RtreeView::box_type,
854 typename RtreeView::allocators_type>
855 node_visitor(rtv.translator(), target_level, boxes_in_boxes);
856 rtv.apply_visitor(node_visitor);
857 }
858
859 return boxes_in_boxes;
860}
861
862
863
864#endif
865
867
868#endif
result_type operator()(size_t i) const
Definition rtree.h:228
const Container & container
Definition rtree.h:237
typename Container::size_type size_t
Definition rtree.h:215
IndexableGetter getter
Definition rtree.h:243
typename boost::geometry::index::indexable< typename Container::value_type > IndexableGetter
Definition rtree.h:205
typename IndexableGetter::result_type result_type
Definition rtree.h:210
IndexableGetterFromIndices(const Container &c)
Definition rtree.h:220
#define DEAL_II_NAMESPACE_OPEN
Definition config.h:502
#define DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
Definition config.h:516
#define DEAL_II_NAMESPACE_CLOSE
Definition config.h:503
#define DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
Definition config.h:559
unsigned int level
Definition grid_out.cc:4626
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:145
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:394
typename boost::geometry::index::detail::rtree::leaf< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type Leaf
Definition rtree.h:361
const size_t target_level
Definition rtree.h:389
typename boost::geometry::index::detail::rtree::internal_node< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type InternalNode
Definition rtree.h:351
const Translator & translator
Definition rtree.h:379
ExtractLevelVisitor(const Translator &translator, const unsigned int target_level, std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > &boxes)