detail/buffer/implementation.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
0006
0007 // This file was modified by Oracle on 2017-2022.
0008 // Modifications copyright (c) 2017-2022 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0012 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0013
0014 // Use, modification and distribution is subject to the Boost Software License,
0015 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0016 // http://www.boost.org/LICENSE_1_0.txt)
0017
0018 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_IMPLEMENTATION_HPP
0019 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_IMPLEMENTATION_HPP
0020
0021 #include <boost/range/value_type.hpp>
0022
0023 #include <boost/geometry/algorithms/detail/buffer/buffer_box.hpp>
0024 #include <boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp>
0025 #include <boost/geometry/algorithms/detail/buffer/interface.hpp>
0026 #include <boost/geometry/algorithms/detail/visit.hpp> // for GC
0027 #include <boost/geometry/algorithms/envelope.hpp>
0028 #include <boost/geometry/algorithms/is_empty.hpp>
0029 #include <boost/geometry/algorithms/union.hpp> // for GC
0030 #include <boost/geometry/arithmetic/arithmetic.hpp>
0031 #include <boost/geometry/geometries/box.hpp>
0032 #include <boost/geometry/strategies/buffer/cartesian.hpp>
0033 #include <boost/geometry/strategies/buffer/geographic.hpp>
0034 #include <boost/geometry/strategies/buffer/spherical.hpp>
0035 #include <boost/geometry/util/math.hpp>
0036 #include <boost/geometry/util/range.hpp>
0037
0038 namespace boost { namespace geometry
0039 {
0040
0041 #ifndef DOXYGEN_NO_DISPATCH
0042 namespace dispatch
0043 {
0044
0045 template <typename BoxIn, typename BoxOut>
0046 struct buffer_dc<BoxIn, BoxOut, box_tag, box_tag>
0047 {
0048     template <typename Distance>
0049     static inline void apply(BoxIn const& box_in, BoxOut& box_out,
0050                              Distance const& distance, Distance const& )
0051     {
0052         detail::buffer::buffer_box(box_in, distance, box_out);
0053     }
0054 };
0055
0056
0057 template <typename Input, typename Output, typename TagIn>
0058 struct buffer_all<Input, Output, TagIn, multi_polygon_tag>
0059 {
0060     template
0061     <
0062         typename DistanceStrategy,
0063         typename SideStrategy,
0064         typename JoinStrategy,
0065         typename EndStrategy,
0066         typename PointStrategy,
0067         typename Strategies
0068     >
0069     static inline void apply(Input const& geometry_in,
0070                              Output& geometry_out,
0071                              DistanceStrategy const& distance_strategy,
0072                              SideStrategy const& side_strategy,
0073                              JoinStrategy const& join_strategy,
0074                              EndStrategy const& end_strategy,
0075                              PointStrategy const& point_strategy,
0076                              Strategies const& strategies)
0077     {
0078         typedef typename boost::range_value<Output>::type polygon_type;
0079
0080         typedef typename point_type<Input>::type point_type;
0081         typedef typename rescale_policy_type
0082             <
0083                 point_type,
0084                 typename geometry::cs_tag<point_type>::type
0085             >::type rescale_policy_type;
0086
0087         if (geometry::is_empty(geometry_in))
0088         {
0089             // Then output geometry is kept empty as well
0090             return;
0091         }
0092
0093         model::box<point_type> box;
0094         geometry::envelope(geometry_in, box);
0095         geometry::buffer(box, box, distance_strategy.max_distance(join_strategy, end_strategy));
0096
0097         rescale_policy_type rescale_policy
0098                 = boost::geometry::get_rescale_policy<rescale_policy_type>(
0099                     box, strategies);
0100
0101         detail::buffer::buffer_inserter<polygon_type>(geometry_in,
0102                     range::back_inserter(geometry_out),
0103                     distance_strategy,
0104                     side_strategy,
0105                     join_strategy,
0106                     end_strategy,
0107                     point_strategy,
0108                     strategies,
0109                     rescale_policy);
0110     }
0111 };
0112
0113
0114 template <typename Input, typename Output>
0115 struct buffer_all<Input, Output, geometry_collection_tag, multi_polygon_tag>
0116 {
0117     template
0118     <
0119         typename DistanceStrategy,
0120         typename SideStrategy,
0121         typename JoinStrategy,
0122         typename EndStrategy,
0123         typename PointStrategy,
0124         typename Strategies
0125     >
0126     static inline void apply(Input const& geometry_in,
0127                              Output& geometry_out,
0128                              DistanceStrategy const& distance_strategy,
0129                              SideStrategy const& side_strategy,
0130                              JoinStrategy const& join_strategy,
0131                              EndStrategy const& end_strategy,
0132                              PointStrategy const& point_strategy,
0133                              Strategies const& strategies)
0134     {
0135         // NOTE: The buffer normally calculates everything at once (by pieces) and traverses all
0136         //   of them to apply the union operation. Not even by merging elements. But that is
0137         //   complex and has led to issues as well. Here intermediate results are calculated
0138         //   with buffer and the results are merged afterwards.
0139         // NOTE: This algorithm merges partial results iteratively.
0140         //   We could first gather all of the results and after that
0141         //   use some more optimal method like merge_elements().
0142         detail::visit_breadth_first([&](auto const& g)
0143         {
0144             Output buffer_result;
0145             buffer_all
0146                 <
0147                     util::remove_cref_t<decltype(g)>, Output
0148                 >::apply(g, buffer_result, distance_strategy, side_strategy,
0149                          join_strategy, end_strategy, point_strategy, strategies);
0150
0151             if (! geometry::is_empty(buffer_result))
0152             {
0153                 Output union_result;
0154                 geometry::union_(geometry_out, buffer_result, union_result, strategies);
0155                 geometry_out = std::move(union_result);
0156             }
0157
0158             return true;
0159         }, geometry_in);
0160     }
0161 };
0162
0163 template <typename Input, typename Output>
0164 struct buffer_all<Input, Output, geometry_collection_tag, geometry_collection_tag>
0165 {
0166     template
0167     <
0168         typename DistanceStrategy,
0169         typename SideStrategy,
0170         typename JoinStrategy,
0171         typename EndStrategy,
0172         typename PointStrategy,
0173         typename Strategies
0174     >
0175     static inline void apply(Input const& geometry_in,
0176                              Output& geometry_out,
0177                              DistanceStrategy const& distance_strategy,
0178                              SideStrategy const& side_strategy,
0179                              JoinStrategy const& join_strategy,
0180                              EndStrategy const& end_strategy,
0181                              PointStrategy const& point_strategy,
0182                              Strategies const& strategies)
0183     {
0184         // NOTE: We could also allow returning GC containing only polygons.
0185         //   We'd have to wrap them in model::multi_polygon and then
0186         //   iteratively emplace_back() into the GC.
0187         using mpo_t = typename util::sequence_find_if
0188             <
0189                 typename traits::geometry_types<Output>::type,
0190                 util::is_multi_polygon
0191             >::type;
0192         mpo_t result;
0193         buffer_all
0194             <
0195                 Input, mpo_t
0196             >::apply(geometry_in, result, distance_strategy, side_strategy,
0197                      join_strategy, end_strategy, point_strategy, strategies);
0198         range::emplace_back(geometry_out, std::move(result));
0199     }
0200 };
0201
0202 template <typename Input, typename Output, typename TagIn>
0203 struct buffer_all<Input, Output, TagIn, geometry_collection_tag>
0204     : buffer_all<Input, Output, geometry_collection_tag, geometry_collection_tag>
0205 {};
0206
0207
0208 } // namespace dispatch
0209 #endif // DOXYGEN_NO_DISPATCH
0210
0211 }} // namespace boost::geometry
0212
0213
0214 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_IMPLEMENTATION_HPP