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