detail/distance/geometry_collection.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2021 Oracle and/or its affiliates.
0004 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0005
0006 // Licensed under the Boost Software License version 1.0.
0007 // http://www.boost.org/users/license.html
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_COLLECTION_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_COLLECTION_HPP
0011
0012
0013 #include <vector>
0014
0015 #include <boost/range/size.hpp>
0016
0017 #include <boost/geometry/algorithms/dispatch/distance.hpp>
0018 #include <boost/geometry/algorithms/detail/visit.hpp>
0019 #include <boost/geometry/core/assert.hpp>
0020 #include <boost/geometry/core/point_type.hpp>
0021 #include <boost/geometry/index/rtree.hpp>
0022 #include <boost/geometry/strategies/distance.hpp>
0023 #include <boost/geometry/strategies/distance_result.hpp>
0024
0025
0026 namespace boost { namespace geometry
0027 {
0028
0029
0030 #ifndef DOXYGEN_NO_DETAIL
0031 namespace detail { namespace distance
0032 {
0033
0034
0035 template <typename Geometry, typename GeometryCollection, typename Strategies>
0036 inline auto geometry_to_collection(Geometry const& geometry,
0037                                    GeometryCollection const& collection,
0038                                    Strategies const& strategies)
0039 {
0040     using result_t = typename geometry::distance_result<Geometry, GeometryCollection, Strategies>::type;
0041     result_t result = 0;
0042     bool is_first = true;
0043     detail::visit_breadth_first([&](auto const& g)
0044     {
0045         result_t r = dispatch::distance
0046                         <
0047                             Geometry, util::remove_cref_t<decltype(g)>, Strategies
0048                         >::apply(geometry, g, strategies);
0049         if (is_first)
0050         {
0051             result = r;
0052             is_first = false;
0053         }
0054         else if (r < result)
0055         {
0056             result = r;
0057         }
0058         return result > result_t(0);
0059     }, collection);
0060
0061     return result;
0062 }
0063
0064 template <typename GeometryCollection1, typename GeometryCollection2, typename Strategies>
0065 inline auto collection_to_collection(GeometryCollection1 const& collection1,
0066                                      GeometryCollection2 const& collection2,
0067                                      Strategies const& strategies)
0068 {
0069     using result_t = typename geometry::distance_result<GeometryCollection1, GeometryCollection2, Strategies>::type;
0070
0071     using point1_t = typename geometry::point_type<GeometryCollection1>::type;
0072     using box1_t = model::box<point1_t>;
0073     using point2_t = typename geometry::point_type<GeometryCollection2>::type;
0074     using box2_t = model::box<point2_t>;
0075
0076     using rtree_value_t = std::pair<box1_t, typename boost::range_iterator<GeometryCollection1 const>::type>;
0077     using rtree_params_t = index::parameters<index::rstar<4>, Strategies>;
0078     using rtree_t = index::rtree<rtree_value_t, rtree_params_t>;
0079
0080     rtree_params_t rtree_params(index::rstar<4>(), strategies);
0081     rtree_t rtree(rtree_params);
0082
0083     // Build rtree of boxes and iterators of elements of GC1
0084     // TODO: replace this with visit_breadth_first_iterator to avoid creating an unnecessary container?
0085     {
0086         std::vector<rtree_value_t> values;
0087         visit_breadth_first_impl<true>::apply([&](auto & g1, auto it)
0088         {
0089             box1_t b1 = geometry::return_envelope<box1_t>(g1, strategies);
0090             geometry::detail::expand_by_epsilon(b1);
0091             values.emplace_back(b1, it);
0092             return true;
0093         }, collection1);
0094         rtree_t rt(values.begin(), values.end(), rtree_params);
0095         rtree = std::move(rt);
0096     }
0097
0098     result_t const zero = 0;
0099     auto const rtree_qend = rtree.qend();
0100
0101     result_t result = 0;
0102     bool is_first = true;
0103     visit_breadth_first([&](auto const& g2)
0104     {
0105         box2_t b2 = geometry::return_envelope<box2_t>(g2, strategies);
0106         geometry::detail::expand_by_epsilon(b2);
0107
0108         for (auto it = rtree.qbegin(index::nearest(b2, rtree.size())) ; it != rtree_qend ; ++it)
0109         {
0110             // If the distance between boxes is greater than or equal to previously found
0111             // distance between geometries then stop processing the current b2 because no
0112             // closer b1 will be found
0113             if (! is_first)
0114             {
0115                 result_t const bd = dispatch::distance
0116                     <
0117                         box1_t, box2_t, Strategies
0118                     >::apply(it->first, b2, strategies);
0119                 if (bd >= result)
0120                 {
0121                     break;
0122                 }
0123             }
0124
0125             // Boxes are closer than the previously found distance (or it's the first time),
0126             // calculate the new distance between geometries and check if it's closer (or assign it).
0127             traits::iter_visit<GeometryCollection1>::apply([&](auto const& g1)
0128             {
0129                 result_t const d = dispatch::distance
0130                     <
0131                         util::remove_cref_t<decltype(g1)>, util::remove_cref_t<decltype(g2)>,
0132                         Strategies
0133                     >::apply(g1, g2, strategies);
0134                 if (is_first)
0135                 {
0136                     result = d;
0137                     is_first = false;
0138                 }
0139                 else if (d < result)
0140                 {
0141                     result = d;
0142                 }
0143             }, it->second);
0144
0145             // The smallest possible distance found, end searching.
0146             if (! is_first && result <= zero)
0147             {
0148                 return false;
0149             }
0150         }
0151
0152         // Just in case
0153         return is_first || result > zero;
0154     }, collection2);
0155
0156     return result;
0157 }
0158
0159
0160 }} // namespace detail::distance
0161 #endif // DOXYGEN_NO_DETAIL
0162
0163
0164 #ifndef DOXYGEN_NO_DISPATCH
0165 namespace dispatch
0166 {
0167
0168
0169 template
0170 <
0171     typename Geometry, typename GeometryCollection, typename Strategies, typename Tag1
0172 >
0173 struct distance
0174     <
0175         Geometry, GeometryCollection, Strategies,
0176         Tag1, geometry_collection_tag, void, false
0177     >
0178 {
0179     static inline auto apply(Geometry const& geometry,
0180                              GeometryCollection const& collection,
0181                              Strategies const& strategies)
0182     {
0183         assert_dimension_equal<Geometry, GeometryCollection>();
0184
0185         return detail::distance::geometry_to_collection(geometry, collection, strategies);
0186     }
0187 };
0188
0189 template
0190 <
0191     typename GeometryCollection, typename Geometry, typename Strategies, typename Tag2
0192 >
0193 struct distance
0194     <
0195         GeometryCollection, Geometry, Strategies,
0196         geometry_collection_tag, Tag2, void, false
0197     >
0198 {
0199     static inline auto apply(GeometryCollection const& collection,
0200                              Geometry const& geometry,
0201                              Strategies const& strategies)
0202     {
0203         assert_dimension_equal<Geometry, GeometryCollection>();
0204
0205         return detail::distance::geometry_to_collection(geometry, collection, strategies);
0206     }
0207 };
0208
0209 template
0210 <
0211     typename GeometryCollection1, typename GeometryCollection2, typename Strategies
0212 >
0213 struct distance
0214     <
0215         GeometryCollection1, GeometryCollection2, Strategies,
0216         geometry_collection_tag, geometry_collection_tag, void, false
0217     >
0218 {
0219     static inline auto apply(GeometryCollection1 const& collection1,
0220                              GeometryCollection2 const& collection2,
0221                              Strategies const& strategies)
0222     {
0223         assert_dimension_equal<GeometryCollection1, GeometryCollection2>();
0224
0225         // Build the rtree for the smaller GC (ignoring recursive GCs)
0226         return boost::size(collection1) <= boost::size(collection2)
0227              ? detail::distance::collection_to_collection(collection1, collection2, strategies)
0228              : detail::distance::collection_to_collection(collection2, collection1, strategies);
0229     }
0230 };
0231
0232 } // namespace dispatch
0233 #endif // DOXYGEN_NO_DISPATCH
0234
0235
0236 }} // namespace boost::geometry
0237
0238
0239 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP