1 files changed, 118 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/gc_make_rtree.hpp b/boost/geometry/algorithms/detail/gc_make_rtree.hpp
new file mode 100644
index 0000000000..c1c00d4692
--- /dev/null
+++ b/boost/geometry/algorithms/detail/gc_make_rtree.hpp
@@ -0,0 +1,118 @@
+// Boost.Geometry
+
+// Copyright (c) 2022, Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
+
+// Licensed under the Boost Software License version 1.0.
+// http://www.boost.org/users/license.html
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_GC_MAKE_RTREE_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GC_MAKE_RTREE_HPP
+
+#include <vector>
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+#include <boost/range/size.hpp>
+
+#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
+#include <boost/geometry/algorithms/detail/visit.hpp>
+#include <boost/geometry/algorithms/envelope.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/strategies/index/services.hpp>
+#include <boost/geometry/views/detail/random_access_view.hpp>
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail
+{
+
+
+template <typename GC>
+using gc_make_rtree_box_t = geometry::model::box
+    <
+        geometry::model::point
+            <
+                typename geometry::coordinate_type<GC>::type,
+                geometry::dimension<GC>::value,
+                typename geometry::coordinate_system<GC>::type
+            >
+    >;
+
+
+template <typename GC, typename Strategy>
+inline auto gc_make_rtree_iterators(GC& gc, Strategy const& strategy)
+{
+    using box_t = gc_make_rtree_box_t<GC>;
+    using iter_t = typename boost::range_iterator<GC>::type;
+
+    using rtree_param_t = index::rstar<4>;
+    using rtree_parameters_t = index::parameters<rtree_param_t, Strategy>;
+    using value_t = std::pair<box_t, iter_t>;
+    using rtree_t = index::rtree<value_t, rtree_parameters_t>;
+
+    // TODO: get rid of the temporary vector
+    auto const size = boost::size(gc);
+    std::vector<value_t> values;
+    values.reserve(size);
+
+    visit_breadth_first_impl<true>::apply([&](auto const& g, auto iter)
+    {
+        box_t b = geometry::return_envelope<box_t>(g, strategy);
+        detail::expand_by_epsilon(b);
+        values.emplace_back(b, iter);
+        return true;
+    }, gc);
+
+    return rtree_t(values.begin(), values.end(), rtree_parameters_t(rtree_param_t(), strategy));
+}
+
+
+template <typename GCView, typename Strategy>
+inline auto gc_make_rtree_indexes(GCView const& gc, Strategy const& strategy)
+{
+    // Alternatively only take random_access_view<GC>
+    static const bool is_random_access = is_random_access_range<GCView>::value;
+    static const bool is_not_recursive = ! is_geometry_collection_recursive<GCView>::value;
+    BOOST_GEOMETRY_STATIC_ASSERT((is_random_access && is_not_recursive),
+                                 "This algorithm requires random-access, non-recursive geometry collection or view.",
+                                 GCView);
+
+    using box_t = gc_make_rtree_box_t<GCView>;
+
+    using rtree_param_t = index::rstar<4>;
+    using rtree_parameters_t = index::parameters<rtree_param_t, Strategy>;
+    using value_t = std::pair<box_t, std::size_t>;
+    using rtree_t = index::rtree<value_t, rtree_parameters_t>;
+
+    // TODO: get rid of the temporary vector
+    std::size_t const size = boost::size(gc);
+    std::vector<value_t> values;
+    values.reserve(size);
+
+    auto const begin = boost::begin(gc);
+    for (std::size_t i = 0; i < size; ++i)
+    {
+        traits::iter_visit<GCView>::apply([&](auto const& g)
+        {
+            box_t b = geometry::return_envelope<box_t>(g, strategy);
+            detail::expand_by_epsilon(b);
+            values.emplace_back(b, i);
+        }, begin + i);
+    }
+
+    return rtree_t(values.begin(), values.end(), rtree_parameters_t(rtree_param_t(), strategy));
+}
+
+
+} // namespace detail
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_GC_MAKE_RTREE_HPP