16#ifndef dealii_numerics_rtree_h
17#define dealii_numerics_rtree_h
29#include <boost/geometry/algorithms/distance.hpp>
31#ifdef DEAL_II_BOOST_HAS_BROKEN_HEADER_DEPRECATIONS
32# define BOOST_ALLOW_DEPRECATED_HEADERS
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
148template <
typename LeafType,
149 typename IndexType = boost::geometry::index::linear<16>,
150 typename IndexableGetter =
153 boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>;
162template <
typename IndexType = boost::geometry::index::linear<16>,
163 typename LeafTypeIterator,
164 typename IndexableGetter = boost::geometry::index::indexable<
165 typename LeafTypeIterator::value_type>>
179template <
typename IndexType = boost::geometry::index::linear<16>,
180 typename ContainerType,
181 typename IndexableGetter = boost::geometry::index::indexable<
182 typename ContainerType::value_type>>
204template <
typename Container>
284template <
typename IndexType = boost::geometry::index::linear<16>,
285 typename ContainerType>
303template <
typename Value,
309 :
public boost::geometry::index::detail::rtree::visitor<
311 typename Options::parameters_type,
314 typename Options::node_tag,
330 typename boost::geometry::index::detail::rtree::internal_node<
332 typename Options::parameters_type,
335 typename Options::node_tag>::type;
340 using Leaf =
typename boost::geometry::index::detail::rtree::leaf<
342 typename Options::parameters_type,
345 typename Options::node_tag>::type;
378 std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &
boxes;
432template <
typename Rtree>
434 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
442template <
typename IndexType,
443 typename LeafTypeIterator,
444 typename IndexableGetter>
448 return RTree<
typename LeafTypeIterator::value_type,
455template <
typename IndexType,
typename ContainerType,
typename IndexableGetter>
459 return pack_rtree<IndexType,
decltype(container.begin()), IndexableGetter>(
460 container.begin(), container.end());
465template <
typename IndexType,
typename ContainerType>
473 indices(0, container.size());
485template <
typename Value,
492 const Translator & translator,
493 const unsigned int target_level,
494 std::vector<
BoundingBox<boost::geometry::dimension<Box>::value>> &boxes)
495 : translator(translator)
497 , target_level(target_level)
503template <
typename Value,
513 typename boost::geometry::index::detail::rtree::elements_type<
516 const auto &elements = boost::geometry::index::detail::rtree::elements(node);
518 if (
level == target_level)
520 const auto offset = boxes.size();
521 boxes.resize(offset + elements.size());
523 unsigned int i = offset;
524 for (
typename ElmentsType::const_iterator it = elements.begin();
525 it != elements.end();
528 boost::geometry::convert(it->first, boxes[i]);
534 const size_t level_backup =
level;
537 for (
typename ElmentsType::const_iterator it = elements.begin();
538 it != elements.end();
541 boost::geometry::index::detail::rtree::apply_visitor(*
this, *it->second);
544 level = level_backup;
547template <
typename Value,
559template <
typename Rtree>
561 boost::geometry::dimension<typename Rtree::indexable_type>::value>>
564 constexpr unsigned int dim =
565 boost::geometry::dimension<typename Rtree::indexable_type>::value;
568 boost::geometry::index::detail::rtree::utilities::view<Rtree>;
571 std::vector<BoundingBox<dim>> boxes;
573 if (rtv.depth() == 0)
579 boost::geometry::convert(tree.bounds(), boxes[0]);
583 const unsigned int target_level =
584 std::min<unsigned int>(
level, rtv.depth() - 1);
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);
600template <
class Rtree>
602n_levels(
const Rtree &tree)
604 boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
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(Container const &c)
#define DEAL_II_NAMESPACE_OPEN
#define DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
#define DEAL_II_NAMESPACE_CLOSE
#define DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
types::global_dof_index size_type
VectorType::value_type * end(VectorType &V)
VectorType::value_type * begin(VectorType &V)
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
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)