15#ifndef dealii_numerics_rtree_h
16#define dealii_numerics_rtree_h
27#include <boost/geometry/algorithms/distance.hpp>
28#include <boost/geometry/index/rtree.hpp>
29#include <boost/geometry/strategies/strategies.hpp>
138template <
typename LeafType,
139 typename IndexType = boost::geometry::index::linear<16>,
140 typename IndexableGetter =
143 boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
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);
169template <
typename IndexType = boost::geometry::index::linear<16>,
170 typename ContainerType,
171 typename IndexableGetter = boost::geometry::index::indexable<
172 typename ContainerType::value_type>>
194template <
typename Container>
213 using size_t =
typename Container::size_type;
298template <
typename IndexType = boost::geometry::index::linear<16>,
299 typename ContainerType>
300RTree<
typename ContainerType::size_type,
317template <
typename Value,
323 :
public boost::geometry::index::detail::rtree::visitor<
325 typename Options::parameters_type,
328 typename Options::node_tag,
344 typename boost::geometry::index::detail::rtree::internal_node<
346 typename Options::parameters_type,
349 typename Options::node_tag>::type;
354 using Leaf =
typename boost::geometry::index::detail::rtree::leaf<
356 typename Options::parameters_type,
359 typename Options::node_tag>::type;
392 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &
boxes;
446template <
typename Rtree>
448 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
462template <
typename Rtree>
464 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
472template <
typename IndexType,
473 typename LeafTypeIterator,
474 typename IndexableGetter>
476pack_rtree(
const LeafTypeIterator &begin,
const LeafTypeIterator &end)
478 return RTree<
typename LeafTypeIterator::value_type,
480 IndexableGetter>(begin, end);
485template <
typename IndexType,
typename ContainerType,
typename IndexableGetter>
489 return pack_rtree<IndexType,
decltype(container.begin()), IndexableGetter>(
490 container.begin(), container.end());
495template <
typename IndexType,
typename ContainerType>
496RTree<
typename ContainerType::size_type,
502 typename ContainerType::size_type>
503 indices(0, container.size());
504 return RTree<
typename ContainerType::size_type,
515template <
typename Value,
522 const Translator &translator,
523 const unsigned int target_level,
524 std::vector<
BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
525 : translator(translator)
527 , target_level(target_level)
533template <
typename Value,
543 typename boost::geometry::index::detail::rtree::elements_type<
546 const auto &elements = boost::geometry::index::detail::rtree::elements(node);
548 if (
level == target_level)
550 const auto offset = boxes.size();
551 boxes.resize(offset + elements.size());
553 unsigned int i = offset;
554 for (
typename ElementsType::const_iterator it = elements.begin();
555 it != elements.end();
558 boost::geometry::convert(
it->first, boxes[i]);
564 const size_t level_backup =
level;
567 for (
typename ElementsType::const_iterator it = elements.begin();
568 it != elements.end();
571 boost::geometry::index::detail::rtree::apply_visitor(*
this, *
it->second);
574 level = level_backup;
577template <
typename Value,
589template <
typename Rtree>
591 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
594 constexpr unsigned int dim =
595 boost::geometry::dimension<typename Rtree::indexable_type>::value;
598 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
601 std::vector<BoundingBox<dim>> boxes;
603 if (rtv.depth() == 0)
609 boost::geometry::convert(tree.bounds(), boxes[0]);
613 const unsigned int target_level =
614 std::min<unsigned int>(
level, rtv.depth() - 1);
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);
630template <
class Rtree>
632n_levels(
const Rtree &tree)
634 boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
639template <
typename Value,
644struct NodeVisitor :
public boost::geometry::index::detail::rtree::visitor<
646 typename Options::parameters_type,
649 typename Options::node_tag,
653 const Translator &translator,
654 unsigned int target_level,
656 std::vector<
BoundingBox<boost::geometry::dimension<Box>::value>>> &boxes);
663 typename boost::geometry::index::detail::rtree::internal_node<
665 typename Options::parameters_type,
668 typename Options::node_tag>::type;
673 using Leaf =
typename boost::geometry::index::detail::rtree::leaf<
675 typename Options::parameters_type,
678 typename Options::node_tag>::type;
685 operator()(
const InternalNode &node);
691 operator()(
const Leaf &);
696 const Translator &translator;
713 const size_t target_level;
720 std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>>
726template <
typename Value,
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>>>
736 : translator(translator)
739 , target_level(target_level)
740 , boxes_in_boxes(bb_in_boxes)
745template <
typename Value,
751NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
752 const NodeVisitor::InternalNode &node)
754 using elements_type =
755 typename boost::geometry::index::detail::rtree::elements_type<
757 const elements_type &elements =
758 boost::geometry::index::detail::rtree::elements(node);
760 if (
level == target_level)
762 const unsigned int n_children = elements.size();
763 const auto offset = boxes_in_boxes.size();
764 boxes_in_boxes.resize(offset + n_children);
767 if (
level == target_level + 1)
770 boxes_in_boxes[node_counter].resize(elements.size());
772 for (
typename elements_type::const_iterator it = elements.begin();
773 it != elements.end();
776 boost::geometry::convert(
it->first, boxes_in_boxes[node_counter][i]);
784 size_t level_backup =
level;
787 for (
typename elements_type::const_iterator it = elements.begin();
788 it != elements.end();
791 boost::geometry::index::detail::rtree::apply_visitor(*
this, *
it->second);
794 level = level_backup;
799template <
typename Value,
805NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()(
806 const NodeVisitor::Leaf &)
809 boxes_in_boxes.clear();
812template <
typename Rtree>
814 boost::geometry::dimension<typename Rtree::indexable_type>::value>>>
817 constexpr unsigned int dim =
818 boost::geometry::dimension<typename Rtree::indexable_type>::value;
821 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
824 std::vector<std::vector<BoundingBox<dim>>> boxes_in_boxes;
826 if (rtv.depth() == 0)
831 boxes_in_boxes.resize(1);
832 boxes_in_boxes[0].resize(1);
833 boost::geometry::convert(tree.bounds(), boxes_in_boxes[0][0]);
837 const unsigned int target_level =
838 std::min<unsigned int>(
level, rtv.depth() - 1);
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);
849 return boxes_in_boxes;
result_type operator()(size_t i) const
const Container & container
typename Container::size_type size_t
typename boost::geometry::index::indexable< typename Container::value_type > IndexableGetter
typename IndexableGetter::result_type result_type
IndexableGetterFromIndices(const Container &c)
#define DEAL_II_NAMESPACE_OPEN
#define DEAL_II_NAMESPACE_CLOSE
boost::integer_range< IncrementableType > iota_view
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
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)