diff options
Diffstat (limited to 'boost/geometry/index/detail/rtree/pack_create.hpp')
| -rw-r--r-- | boost/geometry/index/detail/rtree/pack_create.hpp | 51 |
1 files changed, 31 insertions, 20 deletions
diff --git a/boost/geometry/index/detail/rtree/pack_create.hpp b/boost/geometry/index/detail/rtree/pack_create.hpp index 4cfd39669d..33600a4c93 100644 --- a/boost/geometry/index/detail/rtree/pack_create.hpp +++ b/boost/geometry/index/detail/rtree/pack_create.hpp @@ -2,11 +2,12 @@ // // R-tree initial packing // -// Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2023 Adam Wulkiewicz, Lodz, Poland. // Copyright (c) 2020 Caian Benedicto, Campinas, Brazil. // -// This file was modified by Oracle on 2019. -// Modifications copyright (c) 2019 Oracle and/or its affiliates. +// This file was modified by Oracle on 2019-2023. +// Modifications copyright (c) 2019-2023 Oracle and/or its affiliates. +// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // // Use, modification and distribution is subject to the Boost Software License, @@ -18,12 +19,17 @@ #include <boost/core/ignore_unused.hpp> +#include <boost/geometry/algorithms/centroid.hpp> +#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> #include <boost/geometry/algorithms/expand.hpp> + #include <boost/geometry/index/detail/algorithms/bounds.hpp> +#include <boost/geometry/index/detail/algorithms/content.hpp> +#include <boost/geometry/index/detail/algorithms/is_valid.hpp> #include <boost/geometry/index/detail/algorithms/nth_element.hpp> +#include <boost/geometry/index/detail/rtree/node/node_elements.hpp> #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp> - -#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> +#include <boost/geometry/index/parameters.hpp> namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { @@ -72,23 +78,28 @@ template <std::size_t I, std::size_t Dimension> struct nth_element_and_half_boxes { template <typename EIt, typename Box> - static inline void apply(EIt first, EIt median, EIt last, Box const& box, Box & left, Box & right, std::size_t dim_index) + static inline void apply(EIt first, EIt median, EIt last, Box const& box, + Box & left, Box & right, std::size_t dim_index) { - if ( I == dim_index ) + if (I == dim_index) { index::detail::nth_element(first, median, last, point_entries_comparer<I>()); geometry::convert(box, left); geometry::convert(box, right); - typename coordinate_type<Box>::type edge_len - = geometry::get<max_corner, I>(box) - geometry::get<min_corner, I>(box); - typename coordinate_type<Box>::type median - = geometry::get<min_corner, I>(box) + edge_len / 2; - geometry::set<max_corner, I>(left, median); - geometry::set<min_corner, I>(right, median); + auto const mi = geometry::get<min_corner, I>(box); + auto const ma = geometry::get<max_corner, I>(box); + auto const center = mi + (ma - mi) / 2; + geometry::set<max_corner, I>(left, center); + geometry::set<min_corner, I>(right, center); } else - nth_element_and_half_boxes<I+1, Dimension>::apply(first, median, last, box, left, right, dim_index); + { + nth_element_and_half_boxes + < + I + 1, Dimension + >::apply(first, median, last, box, left, right, dim_index); + } } }; @@ -182,7 +193,7 @@ public: TmpAlloc const& temp_allocator) { typedef typename std::iterator_traits<InIt>::difference_type diff_type; - + diff_type diff = std::distance(first, last); if ( diff <= 0 ) return node_pointer(0); @@ -198,7 +209,7 @@ public: entries.reserve(values_count); auto const& strategy = index::detail::get_strategy(parameters); - + expandable_box<box_type, strategy_type> hint_box(strategy); for ( ; first != last ; ++first ) { @@ -320,7 +331,7 @@ private: { // NOTE: push_back() must be called at the end in order to support move_iterator. // The iterator is dereferenced 2x (no temporary reference) to support - // non-true reference types and move_iterator without boost::forward<>. + // non-true reference types and move_iterator without std::forward<>. elements_box.expand(translator(*(first->second))); rtree::elements(l).push_back(*(first->second)); // MAY THROW (A?,C) } @@ -361,7 +372,7 @@ private: rtree::elements(in).reserve(nodes_count); // MAY THROW (A) // calculate values box and copy values expandable_box<box_type, strategy_type> elements_box(detail::get_strategy(parameters)); - + per_level_packets(first, last, hint_box, values_count, subtree_counts, next_subtree_counts, rtree::elements(in), elements_box, parameters, translator, allocators); @@ -406,7 +417,7 @@ private: elements_box.expand(el.first); return; } - + size_type median_count = calculate_median_count(values_count, subtree_counts); EIt median = first + median_count; @@ -416,7 +427,7 @@ private: box_type left, right; pack_utils::nth_element_and_half_boxes<0, dimension> ::apply(first, median, last, hint_box, left, right, greatest_dim_index); - + per_level_packets(first, median, left, median_count, subtree_counts, next_subtree_counts, elements, elements_box, |