Reference documentation for deal.II version 9.2.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\}}\)
rtree.h
Go to the documentation of this file.
1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 2017 - 2020 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>
22 
26 
28 #include <boost/geometry/index/rtree.hpp>
29 #include <boost/geometry/strategies/strategies.hpp>
31 
32 #include <memory>
33 
34 
36 
132 template <typename LeafType,
133  typename IndexType = boost::geometry::index::linear<16>>
134 using RTree = boost::geometry::index::rtree<LeafType, IndexType>;
135 
146 template <typename IndexType = boost::geometry::index::linear<16>,
147  typename LeafTypeIterator>
149 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end);
150 
163 template <typename IndexType = boost::geometry::index::linear<16>,
164  typename ContainerType>
166 pack_rtree(const ContainerType &container);
167 
182 template <typename Value,
183  typename Options,
184  typename Translator,
185  typename Box,
186  typename Allocators>
188  : public boost::geometry::index::detail::rtree::visitor<
189  Value,
190  typename Options::parameters_type,
191  Box,
192  Allocators,
193  typename Options::node_tag,
194  true>::type
195 {
200  inline ExtractLevelVisitor(
201  Translator const & translator,
202  const unsigned int target_level,
204 
208  using InternalNode =
209  typename boost::geometry::index::detail::rtree::internal_node<
210  Value,
211  typename Options::parameters_type,
212  Box,
213  Allocators,
214  typename Options::node_tag>::type;
215 
219  using Leaf = typename boost::geometry::index::detail::rtree::leaf<
220  Value,
221  typename Options::parameters_type,
222  Box,
223  Allocators,
224  typename Options::node_tag>::type;
225 
230  inline void
231  operator()(InternalNode const &node);
232 
236  inline void
237  operator()(Leaf const &);
238 
242  Translator const &translator;
243 
247  size_t level;
248 
252  const size_t target_level;
253 
258 };
259 
313 template <typename Rtree>
314 inline std::vector<BoundingBox<
316 extract_rtree_level(const Rtree &tree, const unsigned int level);
317 
318 
319 
320 // Inline and template functions
321 #ifndef DOXYGEN
322 template <typename IndexType, typename LeafTypeIterator>
324 pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
325 {
327 }
328 
329 
330 
331 template <typename IndexType, typename ContainerType>
333 pack_rtree(const ContainerType &container)
334 {
335  return pack_rtree<IndexType>(container.begin(), container.end());
336 }
337 
338 
339 
340 template <typename Value,
341  typename Options,
342  typename Translator,
343  typename Box,
344  typename Allocators>
347  const Translator & translator,
348  const unsigned int target_level,
350  : translator(translator)
351  , level(0)
352  , target_level(target_level)
353  , boxes(boxes)
354 {}
355 
356 
357 
358 template <typename Value,
359  typename Options,
360  typename Translator,
361  typename Box,
362  typename Allocators>
363 void
366 {
367  using ElmentsType =
368  typename boost::geometry::index::detail::rtree::elements_type<
369  InternalNode>::type;
370 
371  const auto &elements = boost::geometry::index::detail::rtree::elements(node);
372 
373  if (level == target_level)
374  {
375  const auto offset = boxes.size();
376  boxes.resize(offset + elements.size());
377 
378  unsigned int i = offset;
379  for (typename ElmentsType::const_iterator it = elements.begin();
380  it != elements.end();
381  ++it)
382  {
383  boost::geometry::convert(it->first, boxes[i]);
384  ++i;
385  }
386  return;
387  }
388 
389  const size_t level_backup = level;
390  ++level;
391 
392  for (typename ElmentsType::const_iterator it = elements.begin();
393  it != elements.end();
394  ++it)
395  {
396  boost::geometry::index::detail::rtree::apply_visitor(*this, *it->second);
397  }
398 
399  level = level_backup;
400 }
401 
402 template <typename Value,
403  typename Options,
404  typename Translator,
405  typename Box,
406  typename Allocators>
407 void
410 {}
411 
412 
413 
414 template <typename Rtree>
415 inline std::vector<BoundingBox<
417 extract_rtree_level(const Rtree &tree, const unsigned int level)
418 {
419  constexpr unsigned int dim =
421 
422  using RtreeView =
423  boost::geometry::index::detail::rtree::utilities::view<Rtree>;
424  RtreeView rtv(tree);
425 
426  std::vector<BoundingBox<dim>> boxes;
427 
428  if (rtv.depth() == 0)
429  {
430  // The below algorithm does not work for `rtv.depth()==0`, which might
431  // happen if the number entries in the tree is too small.
432  // In this case, simply return a single bounding box.
433  boxes.resize(1);
434  boost::geometry::convert(tree.bounds(), boxes[0]);
435  }
436  else
437  {
438  const unsigned int target_level =
439  std::min<unsigned int>(level, rtv.depth() - 1);
440 
441  ExtractLevelVisitor<typename RtreeView::value_type,
442  typename RtreeView::options_type,
443  typename RtreeView::translator_type,
444  typename RtreeView::box_type,
445  typename RtreeView::allocators_type>
446  extract_level_visitor(rtv.translator(), target_level, boxes);
447  rtv.apply_visitor(extract_level_visitor);
448  }
449 
450  return boxes;
451 }
452 
453 
454 
455 template <class Rtree>
456 unsigned int
457 n_levels(const Rtree &tree)
458 {
459  boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree);
460  return rtv.depth();
461 }
462 
463 
464 
465 #endif
466 
468 
469 #endif
ExtractLevelVisitor::target_level
const size_t target_level
Definition: rtree.h:252
ExtractLevelVisitor::ExtractLevelVisitor
ExtractLevelVisitor(Translator const &translator, const unsigned int target_level, std::vector< BoundingBox< boost::geometry::dimension< Box >::value >> &boxes)
bounding_box.h
ExtractLevelVisitor::Leaf
typename boost::geometry::index::detail::rtree::leaf< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type Leaf
Definition: rtree.h:224
extract_rtree_level
std::vector< BoundingBox< boost::geometry::dimension< typename Rtree::indexable_type >::value > > extract_rtree_level(const Rtree &tree, const unsigned int level)
ExtractLevelVisitor::operator()
void operator()(InternalNode const &node)
ExtractLevelVisitor::InternalNode
typename boost::geometry::index::detail::rtree::internal_node< Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag >::type InternalNode
Definition: rtree.h:214
BoundingBox
Definition: bounding_box.h:128
level
unsigned int level
Definition: grid_out.cc:4355
DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
#define DEAL_II_ENABLE_EXTRA_DIAGNOSTICS
Definition: config.h:409
RTree
boost::geometry::index::rtree< LeafType, IndexType > RTree
Definition: rtree.h:134
TrilinosWrappers::internal::begin
VectorType::value_type * begin(VectorType &V)
Definition: trilinos_sparse_matrix.cc:51
DEAL_II_NAMESPACE_OPEN
#define DEAL_II_NAMESPACE_OPEN
Definition: config.h:358
TrilinosWrappers::internal::end
VectorType::value_type * end(VectorType &V)
Definition: trilinos_sparse_matrix.cc:65
ExtractLevelVisitor::translator
const Translator & translator
Definition: rtree.h:242
value
static const bool value
Definition: dof_tools_constraints.cc:433
pack_rtree
RTree< typename LeafTypeIterator::value_type, IndexType > pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end)
ExtractLevelVisitor::boxes
std::vector< BoundingBox< boost::geometry::dimension< Box >::value > > & boxes
Definition: rtree.h:257
config.h
ExtractLevelVisitor::level
size_t level
Definition: rtree.h:247
DEAL_II_NAMESPACE_CLOSE
#define DEAL_II_NAMESPACE_CLOSE
Definition: config.h:359
segment.h
point.h
ExtractLevelVisitor
Definition: rtree.h:187
DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
#define DEAL_II_DISABLE_EXTRA_DIAGNOSTICS
Definition: config.h:372
point.h