| 1 |
// ------------------------------------------------------------------------ |
| 2 |
// |
| 3 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 4 |
// Copyright (C) 2018 - 2025 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> |
| 21 |
#include <deal.II/base/std_cxx20/iota_view.h> |
| 22 |
|
| 23 |
#include <deal.II/boost_adaptors/bounding_box.h> |
| 24 |
#include <deal.II/boost_adaptors/point.h> |
| 25 |
#include <deal.II/boost_adaptors/segment.h> |
| 26 |
|
| 27 |
DEAL_II_DISABLE_EXTRA_DIAGNOSTICS |
| 28 |
#include <boost/geometry/algorithms/distance.hpp> |
| 29 |
#include <boost/geometry/index/rtree.hpp> |
| 30 |
#include <boost/geometry/strategies/strategies.hpp> |
| 31 |
DEAL_II_ENABLE_EXTRA_DIAGNOSTICS |
| 32 |
|
| 33 |
#include <memory> |
| 34 |
|
| 35 |
|
| 36 |
DEAL_II_NAMESPACE_OPEN |
| 37 |
|
| 38 |
/** |
| 39 |
* A wrapper for the boost::geometry::index::rtree class, implementing a |
| 40 |
* self-balancing spatial index (the R-tree) capable of storing various types of |
| 41 |
* values, using different balancing algorithms. |
| 42 |
* |
| 43 |
* From [Wikipedia](https://en.wikipedia.org/wiki/R-tree): |
| 44 |
* <blockquote> |
| 45 |
* R-trees are tree data structures used for spatial access methods, i.e., for |
| 46 |
* indexing multi-dimensional information such as geographical coordinates, |
| 47 |
* rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 |
| 48 |
* and has found significant use in both theoretical and applied contexts. A |
| 49 |
* common real-world usage for an R-tree might be to store spatial objects such |
| 50 |
* as restaurant locations or the polygons that typical maps are made of: |
| 51 |
* streets, buildings, outlines of lakes, coastlines, etc. and then find answers |
| 52 |
* quickly to queries such as "Find all museums within 2 km of my current |
| 53 |
* location", "retrieve all road segments within 2 km of my location" (to |
| 54 |
* display them in a navigation system) or "find the nearest gas station" |
| 55 |
* (although not taking roads into account). The R-tree can also accelerate |
| 56 |
* nearest neighbor search for various distance metrics, including |
| 57 |
* great-circle distance. |
| 58 |
* |
| 59 |
* The key idea of the data structure is to group nearby objects and represent |
| 60 |
* them with their minimum bounding rectangle in the next higher level of the |
| 61 |
* tree; the "R" in R-tree is for rectangle. Since all objects lie within this |
| 62 |
* bounding rectangle, a query that does not intersect the bounding rectangle |
| 63 |
* also cannot intersect any of the contained objects. At the leaf level, each |
| 64 |
* rectangle describes a single object; at higher levels the aggregation of an |
| 65 |
* increasing number of objects. This can also be seen as an increasingly coarse |
| 66 |
* approximation of the data set. |
| 67 |
* |
| 68 |
* The key difficulty of R-tree is to build an efficient tree that on one hand |
| 69 |
* is balanced (so the leaf nodes are at the same height) on the other hand the |
| 70 |
* rectangles do not cover too much empty space and do not overlap too much (so |
| 71 |
* that during search, fewer subtrees need to be processed). For example, the |
| 72 |
* original idea for inserting elements to obtain an efficient tree is to always |
| 73 |
* insert into the subtree that requires least enlargement of its bounding box. |
| 74 |
* Once that page is full, the data is split into two sets that should cover the |
| 75 |
* minimal area each. Most of the research and improvements for R-trees aims at |
| 76 |
* improving the way the tree is built and can be grouped into two objectives: |
| 77 |
* building an efficient tree from scratch (known as bulk-loading) and |
| 78 |
* performing changes on an existing tree (insertion and deletion). |
| 79 |
* </blockquote> |
| 80 |
* |
| 81 |
* An RTree may store any type of @p LeafType as long as it is possible to extract |
| 82 |
* an @p Indexable that the RTree can handle and compare values. An @p Indexable |
| 83 |
* is a type adapted to the Point, BoundingBox or Segment concept, for which |
| 84 |
* distance and equality comparison are implemented. The deal.II Point, Segment, |
| 85 |
* and BoundingBox classes satisfy this requirement, but you can mix in any |
| 86 |
* geometry object that boost::geometry accepts as indexable. |
| 87 |
* |
| 88 |
* In particular, given an @p Indexable type (for example a Point, a BoundingBox, |
| 89 |
* or a Segment), @p LeafType can by any of @p Indexable, `std::pair<Indexable, T>`, |
| 90 |
* `boost::tuple<Indexable, ...>` or `std::tuple<Indexable, ...>`. |
| 91 |
* |
| 92 |
* The optional argument @p IndexType is used only when adding elements to the |
| 93 |
* tree one by one. If a range insertion is used, then the tree is built using |
| 94 |
* the packing algorithm. |
| 95 |
* |
| 96 |
* Linear, quadratic, and rstar algorithms are available if one wants to |
| 97 |
* construct the tree sequentially. However, none of these is very efficient, |
| 98 |
* and users should use the packing algorithm when possible. |
| 99 |
* |
| 100 |
* The packing algorithm constructs the tree all at once, and may be used when |
| 101 |
* you have all the leaves at your disposal. |
| 102 |
* |
| 103 |
* This class is usually used in combination with one of the two helper |
| 104 |
* functions pack_rtree(), that takes a container or a range of iterators to |
| 105 |
* construct the RTree using the packing algorithm. |
| 106 |
* |
| 107 |
* An example usage is the following: |
| 108 |
* |
| 109 |
* @code |
| 110 |
* std::vector<Point<2>> points = generate_some_points(); |
| 111 |
* auto tree = pack_rtree(points.begin(), points.end()); |
| 112 |
* // or, equivalently: |
| 113 |
* // auto tree = pack_rtree(points); |
| 114 |
* @endcode |
| 115 |
* |
| 116 |
* The tree is accessed by using [`boost::geometry::index` |
| 117 |
* queries](https://www.boost.org/doc/libs/1_68_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html). |
| 118 |
* For example, after constructing the tree with the snippet above, one can ask |
| 119 |
* for the closest points to a segment in the following way: |
| 120 |
* |
| 121 |
* @code |
| 122 |
* namespace bgi = boost::geometry::index; |
| 123 |
* |
| 124 |
* Segment<2> segment(Point<2>(0,0), Point<2>(1,1)); |
| 125 |
* |
| 126 |
* std::vector<Point<2>> intersection; |
| 127 |
* tree.query(bgi::nearest(segment,3), std::back_inserter(intersection)); |
| 128 |
* // Returns the 3 closest points to the Segment defined above. |
| 129 |
* @endcode |
| 130 |
* |
| 131 |
* In general, a tree does not need to store the actual objects, as long as it |
| 132 |
* knows how to access a const reference to an indexable type. This is |
| 133 |
* achieved by passing the optional template argument @p IndexableGetter, that |
| 134 |
* extracts a const reference to one of the possible indexable types given an |
| 135 |
* object of type @p LeafType. As an example, one may store points in a container, |
| 136 |
* and only create a tree of the indices within the container, using the |
| 137 |
* IndexableGetterFromIndices class defined below, and the function |
| 138 |
* pack_rtree_of_indices(). |
| 139 |
*/ |
| 140 |
template <typename LeafType, |
| 141 |
typename IndexType = boost::geometry::index::linear<16>, |
| 142 |
typename IndexableGetter = |
| 143 |
boost::geometry::index::indexable<LeafType>> |
| 144 |
using RTree = |
| 145 |
boost::geometry::index::rtree<LeafType, IndexType, IndexableGetter>; |
| 146 |
|
| 147 |
/** |
| 148 |
* Construct the correct RTree object by passing an iterator range. |
| 149 |
* |
| 150 |
* Notice that the order of the parameters is the opposite with respect to the |
| 151 |
* RTree class, since we can automatically infer the @p LeafType from the |
| 152 |
* arguments. |
| 153 |
*/ |
| 154 |
template <typename IndexType = boost::geometry::index::linear<16>, |
| 155 |
typename LeafTypeIterator, |
| 156 |
typename IndexableGetter = boost::geometry::index::indexable< |
| 157 |
typename LeafTypeIterator::value_type>> |
| 158 |
RTree<typename LeafTypeIterator::value_type, IndexType, IndexableGetter> |
| 159 |
pack_rtree(const LeafTypeIterator &begin, const LeafTypeIterator &end); |
| 160 |
|
| 161 |
/** |
| 162 |
* Construct an RTree object by passing an STL container type. |
| 163 |
* This function is used in step-70. |
| 164 |
* |
| 165 |
* Notice that the order of the template parameters is the opposite with respect |
| 166 |
* to the |
| 167 |
* RTree class, since we can automatically infer the @p LeafType from the |
| 168 |
* arguments, and we only need to specify the @p IndexType if the default is not |
| 169 |
* adequate. |
| 170 |
*/ |
| 171 |
template <typename IndexType = boost::geometry::index::linear<16>, |
| 172 |
typename ContainerType, |
| 173 |
typename IndexableGetter = boost::geometry::index::indexable< |
| 174 |
typename ContainerType::value_type>> |
| 175 |
RTree<typename ContainerType::value_type, IndexType, IndexableGetter> |
| 176 |
pack_rtree(const ContainerType &container); |
| 177 |
|
| 178 |
/** |
| 179 |
* A class that may be used as an @p IndexableGetter template argument for an |
| 180 |
* RTree that stores indices to entries in a @p Container type. |
| 181 |
* |
| 182 |
* This class may be used as a proxy to extract an indexable type from |
| 183 |
* compatible containers. For example: |
| 184 |
* @code |
| 185 |
* std::vector<std::pair<Point<dim>, double> > point_temperature = fill(); |
| 186 |
* IndexableGetterFromIndices<decltype(point_temperature)> |
| 187 |
* getter(point_temperature); |
| 188 |
* |
| 189 |
* const Point<dim> &p = getter(i); // returns point_temperature[i].first; |
| 190 |
* @endcode |
| 191 |
* |
| 192 |
* This class is used by the pack_rtree_of_indices() function to construct an |
| 193 |
* RTree where the leaves are indices pointing to the entries of the container |
| 194 |
* passed to this class. |
| 195 |
*/ |
| 196 |
template <typename Container> |
| 197 |
class IndexableGetterFromIndices |
| 198 |
{ |
| 199 |
public: |
| 200 |
/** |
| 201 |
* An alias for the boost type that is used to extract a Point, Segment, or |
| 202 |
* BoundingBox from compatible types (pairs, tuples, etc.). |
| 203 |
*/ |
| 204 |
using IndexableGetter = |
| 205 |
typename boost::geometry::index::indexable<typename Container::value_type>; |
| 206 |
|
| 207 |
/** |
| 208 |
* An alias to the actual geometrical type. |
| 209 |
*/ |
| 210 |
using result_type = typename IndexableGetter::result_type; |
| 211 |
|
| 212 |
/** |
| 213 |
* An alias to the index type. |
| 214 |
*/ |
| 215 |
using size_t = typename Container::size_type; |
| 216 |
|
| 217 |
/** |
| 218 |
* Constructor. Store a const reference to a container. |
| 219 |
*/ |
| 220 |
explicit IndexableGetterFromIndices(const Container &c) |
| 221 |
: container(c) |
| 222 |
{} |
| 223 |
|
| 224 |
/** |
| 225 |
* Implements the @p IndexableGetter requirements of the rtree class. |
| 226 |
*/ |
| 227 |
result_type |
| 228 |
operator()(size_t i) const |
| 229 |
{ |
| 230 |
return getter(container[i]); |
| 231 |
} |
| 232 |
|
| 233 |
private: |
| 234 |
/** |
| 235 |
* A const reference to the container. |
| 236 |
*/ |
| 237 |
const Container &container; |
| 238 |
|
| 239 |
/** |
| 240 |
* An instantiation of the getter that allows easy translation from the |
| 241 |
* container @p value_type and the actual indexable type. |
| 242 |
*/ |
| 243 |
IndexableGetter getter; |
| 244 |
}; |
| 245 |
|
| 246 |
/** |
| 247 |
* Construct a RTree object that stores the indices of an existing container of |
| 248 |
* indexable types. The only requirement on the container is that it supports |
| 249 |
* operator[] for any index between 0 and the size of the container (i.e., a |
| 250 |
* std::vector, or an std::array will do, however an std::map won't). |
| 251 |
* |
| 252 |
* Differently from the object created by the pack_rtree() function, in this |
| 253 |
* case we don't store the actual geometrical types, but just their indices: |
| 254 |
* |
| 255 |
* @code |
| 256 |
* namespace bgi = boost::geometry::index; |
| 257 |
* std::vector<Point<dim>> some_points = fill(); |
| 258 |
* auto tree = pack_rtree(points); // the tree contains a copy of the points |
| 259 |
* auto index_tree = pack_rtree_of_indices(points); // the tree contains only |
| 260 |
* // the indices of the |
| 261 |
* // points |
| 262 |
* BoundingBox<dim> box = build_a_box(); |
| 263 |
* |
| 264 |
* for(const auto &p: tree | bgi::adaptors::queried(bgi::intersects(box))) |
| 265 |
* std::cout << "Point p: " << p << std::endl; |
| 266 |
* |
| 267 |
* for(const auto &i: index_tree | bgi::adaptors::queried(bgi::intersects(box))) |
| 268 |
* std::cout << "Point p: " << some_points[i] << std::endl; |
| 269 |
* @endcode |
| 270 |
* |
| 271 |
* The leaves stored in the tree are the indices of the corresponding entry in |
| 272 |
* the container. A reference to the external container is stored internally, |
| 273 |
* but keep in mind that if you change the container, you should rebuild the |
| 274 |
* tree. |
| 275 |
* |
| 276 |
* @warning This function does not work on Windows. As an alternative, |
| 277 |
* build a tree with pairs of point and id. For instance to |
| 278 |
* create an intersection between `BoundingBox<dim> box` and |
| 279 |
* `std::vector<BoundingBox<dim>> boxes`, don't write: |
| 280 |
* @code |
| 281 |
* const auto tree = pack_rtree_of_indices(boxes); |
| 282 |
* |
| 283 |
* for (const auto &i : tree | bgi::adaptors::queried(bgi::intersects(box))) |
| 284 |
* std::cout << i << " " << boxes[i] << std::endl; |
| 285 |
* @endcode |
| 286 |
* but instead: |
| 287 |
* @code |
| 288 |
* std::vector<std::pair<BoundingBox<dim>, unsigned int>> boxes_and_ids; |
| 289 |
* |
| 290 |
* for(unsigned int i = 0; i < boxes.size(); ++i) |
| 291 |
* boxes_and_ids.emplace_back(boxes[i], i); |
| 292 |
* |
| 293 |
* const auto tree = pack_rtree(boxes_and_ids); |
| 294 |
* |
| 295 |
* for (const auto &i : tree | bgi::adaptors::queried(bgi::intersects(box))) |
| 296 |
* std::cout << i->second << " " << boxes[i->second] << std::endl; |
| 297 |
* @endcode |
| 298 |
* |
| 299 |
*/ |
| 300 |
template <typename IndexType = boost::geometry::index::linear<16>, |
| 301 |
typename ContainerType> |
| 302 |
RTree<typename ContainerType::size_type, |
| 303 |
IndexType, |
| 304 |
IndexableGetterFromIndices<ContainerType>> |
| 305 |
pack_rtree_of_indices(const ContainerType &container); |
| 306 |
|
| 307 |
/** |
| 308 |
* Helper structure that allows one to extract a level from an RTree as a vector |
| 309 |
* of BoundingBox objects. |
| 310 |
* |
| 311 |
* This structure implements a boost::geometry::index::detail::rtree::visitor |
| 312 |
* object, allowing one to visit any existing RTree object, and return the |
| 313 |
* vector of bounding boxes associated to a specific target level of the tree. |
| 314 |
* |
| 315 |
* Although possible, direct usage of this structure is cumbersome. The |
| 316 |
* suggested usage of this class is through the helper function |
| 317 |
* extract_rtree_level(). |
| 318 |
*/ |
| 319 |
template <typename Value, |
| 320 |
typename Options, |
| 321 |
typename Translator, |
| 322 |
typename Box, |
| 323 |
typename Allocators> |
| 324 |
struct ExtractLevelVisitor |
| 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 |
{ |
| 333 |
/** |
| 334 |
* Construct a vector @p boxes of BoundingBox objects corresponding to the |
| 335 |
* @p target_level of the tree. |
| 336 |
*/ |
| 337 |
inline ExtractLevelVisitor( |
| 338 |
const Translator &translator, |
| 339 |
const unsigned int target_level, |
| 340 |
std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes); |
| 341 |
|
| 342 |
/** |
| 343 |
* An alias that identifies an InternalNode of the tree. |
| 344 |
*/ |
| 345 |
using InternalNode = |
| 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 |
|
| 353 |
/** |
| 354 |
* An alias that identifies a Leaf of the tree. |
| 355 |
*/ |
| 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 |
|
| 363 |
/** |
| 364 |
* Implements the visitor interface for InternalNode objects. If the node |
| 365 |
* belongs to the @p target_level, then fill the bounding box vector. |
| 366 |
*/ |
| 367 |
inline void |
| 368 |
operator()(const InternalNode &node); |
| 369 |
|
| 370 |
/** |
| 371 |
* Implements the visitor interface for Leaf objects. |
| 372 |
*/ |
| 373 |
inline void |
| 374 |
operator()(const Leaf &); |
| 375 |
|
| 376 |
/** |
| 377 |
* Translator interface, required by the boost implementation of the rtree. |
| 378 |
*/ |
| 379 |
const Translator &translator; |
| 380 |
|
| 381 |
/** |
| 382 |
* Store the level we are currently visiting. |
| 383 |
*/ |
| 384 |
std::size_t level; |
| 385 |
|
| 386 |
/** |
| 387 |
* The level we want to extract from the RTree object. |
| 388 |
*/ |
| 389 |
const std::size_t target_level; |
| 390 |
|
| 391 |
/** |
| 392 |
* A reference to the input vector of BoundingBox objects. |
| 393 |
*/ |
| 394 |
std::vector<BoundingBox<boost::geometry::dimension<Box>::value>> &boxes; |
| 395 |
}; |
| 396 |
|
| 397 |
/** |
| 398 |
* Given a RTree object @p rtree, and a target level @p level, return a vector |
| 399 |
* of BoundingBox objects containing all the bounding boxes that make the given |
| 400 |
* @p level of the @p rtree. This function is a convenient wrapper around the |
| 401 |
* ExtractLevelVisitor class. It is used in step-70. |
| 402 |
* |
| 403 |
* Since an RTree object is a balanced tree, you can expect each entry of the |
| 404 |
* resulting vector to contain roughly the same number of children, and |
| 405 |
* ultimately, the same number of leaf objects. If you request for a level that |
| 406 |
* is not present in the RTree, the last level is returned. |
| 407 |
* |
| 408 |
* A typical usage of this function is in the context of |
| 409 |
* parallel::distributed::Triangulation objects, where one would like to |
| 410 |
* construct a rough representation of the area which is covered by the locally |
| 411 |
* owned cells of the active process, and exchange this information with other |
| 412 |
* processes. The finest level of information is given by the leaves, which in |
| 413 |
* this context would be the collection of all the bounding boxes associated |
| 414 |
* to the locally owned cells of the triangulation. Exchanging this information |
| 415 |
* with all participating processes would defeat the purpose of parallel |
| 416 |
* computations. If however one constructs an RTree containing these bounding |
| 417 |
* boxes (for example, by calling |
| 418 |
* GridTools::Cache::get_cell_bounding_boxes_rtree()), and then extracts one of |
| 419 |
* the first levels of the RTree, only a handful of BoundingBox objects would be |
| 420 |
* returned, allowing the user to have a very efficient description of the |
| 421 |
* geometry of the domain, and of its distribution among processes. |
| 422 |
* |
| 423 |
* An example usage is given by the following snippet of code: |
| 424 |
* @code |
| 425 |
* parallel::distributed::Triangulation<2> tria(MPI_COMM_WORLD); |
| 426 |
* GridGenerator::hyper_ball(tria); |
| 427 |
* tria.refine_global(4); |
| 428 |
* |
| 429 |
* std::vector<BoundingBox<2>> all_boxes(tria.n_locally_owned_active_cells()); |
| 430 |
* unsigned int i = 0; |
| 431 |
* for (const auto &cell : tria.active_cell_iterators()) |
| 432 |
* if (cell->is_locally_owned()) |
| 433 |
* all_boxes[i++] = cell->bounding_box(); |
| 434 |
* |
| 435 |
* const auto tree = pack_rtree(all_boxes); |
| 436 |
* const auto boxes = extract_rtree_level(tree, 1); |
| 437 |
* @endcode |
| 438 |
* |
| 439 |
* When run on three processes, the complete set of the BoundingBox objects |
| 440 |
* surrounding only the locally owned cells and the second level of the rtree |
| 441 |
* constructed with those boxes would look like in the following pictures (one |
| 442 |
* image per process): |
| 443 |
* |
| 444 |
* @image html rtree-process-0.png |
| 445 |
* @image html rtree-process-1.png |
| 446 |
* @image html rtree-process-2.png |
| 447 |
*/ |
| 448 |
template <typename Rtree> |
| 449 |
inline std::vector<BoundingBox< |
| 450 |
boost::geometry::dimension<typename Rtree::indexable_type>::value>> |
| 451 |
extract_rtree_level(const Rtree &tree, const unsigned int level); |
| 452 |
|
| 453 |
|
| 454 |
|
| 455 |
/** |
| 456 |
* Given an Rtree object @p tree and a target level @p level, this function returns |
| 457 |
* the bounding boxes associated to the children on level l+1 and stores them in |
| 458 |
* a vector. The resulting type is hence a vector of vectors of BoundingBox |
| 459 |
* objects. |
| 460 |
* If @p v is such a vector, then @p v has the following property: |
| 461 |
* @p v[i] is a vector with all of the bounding boxes associated to the children |
| 462 |
* of the i-th node of the tree. |
| 463 |
*/ |
| 464 |
template <typename Rtree> |
| 465 |
std::vector<std::vector<BoundingBox< |
| 466 |
boost::geometry::dimension<typename Rtree::indexable_type>::value>>> |
| 467 |
extract_children_of_level(const Rtree &tree, const unsigned int level); |
| 468 |
|
| 469 |
|
| 470 |
|
| 471 |
// Inline and template functions |
| 472 |
#ifndef DOXYGEN |
| 473 |
|
| 474 |
template <typename IndexType, |
| 475 |
typename LeafTypeIterator, |
| 476 |
typename IndexableGetter> |
| 477 |
RTree<typename LeafTypeIterator::value_type, IndexType, IndexableGetter> |
| 478 |
pack_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 |
|
| 487 |
template <typename IndexType, typename ContainerType, typename IndexableGetter> |
| 488 |
RTree<typename ContainerType::value_type, IndexType, IndexableGetter> |
| 489 |
pack_rtree(const ContainerType &container) |
| 490 |
{ |
| 491 |
return pack_rtree<IndexType, decltype(container.begin()), IndexableGetter>( |
| 492 |
container.begin(), container.end()); |
| 493 |
} |
| 494 |
|
| 495 |
|
| 496 |
|
| 497 |
template <typename IndexType, typename ContainerType> |
| 498 |
RTree<typename ContainerType::size_type, |
| 499 |
IndexType, |
| 500 |
IndexableGetterFromIndices<ContainerType>> |
| 501 |
pack_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, |
| 516 |
IndexableGetterFromIndices<ContainerType>>( |
| 517 |
indices.begin(), |
| 518 |
indices.end(), |
| 519 |
IndexType(), |
| 520 |
IndexableGetterFromIndices<ContainerType>(container)); |
| 521 |
} |
| 522 |
|
| 523 |
|
| 524 |
|
| 525 |
template <typename Value, |
| 526 |
typename Options, |
| 527 |
typename Translator, |
| 528 |
typename Box, |
| 529 |
typename Allocators> |
| 530 |
ExtractLevelVisitor<Value, Options, Translator, Box, Allocators>:: |
| 531 |
ExtractLevelVisitor( |
| 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 |
|
| 543 |
template <typename Value, |
| 544 |
typename Options, |
| 545 |
typename Translator, |
| 546 |
typename Box, |
| 547 |
typename Allocators> |
| 548 |
void |
| 549 |
ExtractLevelVisitor<Value, Options, Translator, Box, Allocators>::operator()( |
| 550 |
const ExtractLevelVisitor::InternalNode &node) |
| 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 std::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 |
|
| 587 |
template <typename Value, |
| 588 |
typename Options, |
| 589 |
typename Translator, |
| 590 |
typename Box, |
| 591 |
typename Allocators> |
| 592 |
void |
| 593 |
ExtractLevelVisitor<Value, Options, Translator, Box, Allocators>::operator()( |
| 594 |
const ExtractLevelVisitor::Leaf &) |
| 595 |
{} |
| 596 |
|
| 597 |
|
| 598 |
|
| 599 |
template <typename Rtree> |
| 600 |
inline std::vector<BoundingBox< |
| 601 |
boost::geometry::dimension<typename Rtree::indexable_type>::value>> |
| 602 |
extract_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 |
|
| 640 |
template <class Rtree> |
| 641 |
unsigned int |
| 642 |
n_levels(const Rtree &tree) |
| 643 |
{ |
| 644 |
boost::geometry::index::detail::rtree::utilities::view<Rtree> rtv(tree); |
| 645 |
return rtv.depth(); |
| 646 |
} |
| 647 |
|
| 648 |
|
| 649 |
template <typename Value, |
| 650 |
typename Options, |
| 651 |
typename Translator, |
| 652 |
typename Box, |
| 653 |
typename Allocators> |
| 654 |
struct 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 |
|
| 669 |
/** |
| 670 |
* An alias that identifies an InternalNode of the tree. |
| 671 |
*/ |
| 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 |
|
| 680 |
/** |
| 681 |
* An alias that identifies a Leaf of the tree. |
| 682 |
*/ |
| 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 |
|
| 690 |
/** |
| 691 |
* Implements the visitor interface for InternalNode objects. If the node |
| 692 |
* belongs to the level next to @p target_level, then fill the bounding box vector for that node. |
| 693 |
*/ |
| 694 |
inline void |
| 695 |
operator()(const InternalNode &node); |
| 696 |
|
| 697 |
/** |
| 698 |
* Implements the visitor interface for Leaf objects. |
| 699 |
*/ |
| 700 |
inline void |
| 701 |
operator()(const Leaf &); |
| 702 |
|
| 703 |
/** |
| 704 |
* Translator interface, required by the boost implementation of the rtree. |
| 705 |
*/ |
| 706 |
const Translator &translator; |
| 707 |
|
| 708 |
/** |
| 709 |
* Store the level we are currently visiting. |
| 710 |
*/ |
| 711 |
std::size_t level; |
| 712 |
|
| 713 |
/** |
| 714 |
* Index used to keep track of the number of different visited nodes during |
| 715 |
* recursion/ |
| 716 |
*/ |
| 717 |
std::size_t node_counter; |
| 718 |
|
| 719 |
/** |
| 720 |
* The level where children are living. |
| 721 |
* Before: "we want to extract from the RTree object." |
| 722 |
*/ |
| 723 |
const std::size_t target_level; |
| 724 |
|
| 725 |
/** |
| 726 |
* A reference to the input vector of vector of BoundingBox objects. This |
| 727 |
* vector v has the following property: v[i] = vector with all |
| 728 |
* of the BoundingBox bounded by the i-th node of the Rtree. |
| 729 |
*/ |
| 730 |
std::vector<std::vector<BoundingBox<boost::geometry::dimension<Box>::value>>> |
| 731 |
&boxes_in_boxes; |
| 732 |
}; |
| 733 |
|
| 734 |
|
| 735 |
|
| 736 |
template <typename Value, |
| 737 |
typename Options, |
| 738 |
typename Translator, |
| 739 |
typename Box, |
| 740 |
typename Allocators> |
| 741 |
NodeVisitor<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 |
|
| 755 |
template <typename Value, |
| 756 |
typename Options, |
| 757 |
typename Translator, |
| 758 |
typename Box, |
| 759 |
typename Allocators> |
| 760 |
void |
| 761 |
NodeVisitor<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 |
std::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 |
|
| 809 |
template <typename Value, |
| 810 |
typename Options, |
| 811 |
typename Translator, |
| 812 |
typename Box, |
| 813 |
typename Allocators> |
| 814 |
void |
| 815 |
NodeVisitor<Value, Options, Translator, Box, Allocators>::operator()( |
| 816 |
const NodeVisitor::Leaf &) |
| 817 |
{ |
| 818 |
// No children for leaf nodes. |
| 819 |
boxes_in_boxes.clear(); |
| 820 |
} |
| 821 |
|
| 822 |
template <typename Rtree> |
| 823 |
inline std::vector<std::vector<BoundingBox< |
| 824 |
boost::geometry::dimension<typename Rtree::indexable_type>::value>>> |
| 825 |
extract_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 |
|
| 866 |
DEAL_II_NAMESPACE_CLOSE |
| 867 |
|
| 868 |
#endif |