geometry/algorithms/densify.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
0004
0005 // Copyright (c) 2017-2023, Oracle and/or its affiliates.
0006 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0007 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0008
0009 // Licensed under the Boost Software License version 1.0.
0010 // http://www.boost.org/users/license.html
0011
0012 #ifndef BOOST_GEOMETRY_ALGORITHMS_DENSIFY_HPP
0013 #define BOOST_GEOMETRY_ALGORITHMS_DENSIFY_HPP
0014
0015
0016 #include <boost/range/size.hpp>
0017 #include <boost/range/value_type.hpp>
0018 #include <boost/throw_exception.hpp>
0019
0020 #include <boost/geometry/algorithms/clear.hpp>
0021 #include <boost/geometry/algorithms/convert.hpp>
0022 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
0023 #include <boost/geometry/algorithms/detail/visit.hpp>
0024 #include <boost/geometry/algorithms/not_implemented.hpp>
0025 #include <boost/geometry/core/closure.hpp>
0026 #include <boost/geometry/core/exception.hpp>
0027 #include <boost/geometry/core/tag.hpp>
0028 #include <boost/geometry/core/tags.hpp>
0029 #include <boost/geometry/core/visit.hpp>
0030 #include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility
0031 #include <boost/geometry/strategies/default_strategy.hpp>
0032 #include <boost/geometry/strategies/densify/cartesian.hpp>
0033 #include <boost/geometry/strategies/densify/geographic.hpp>
0034 #include <boost/geometry/strategies/densify/spherical.hpp>
0035 #include <boost/geometry/strategies/detail.hpp>
0036 #include <boost/geometry/util/constexpr.hpp>
0037 #include <boost/geometry/util/range.hpp>
0038
0039
0040 namespace boost { namespace geometry
0041 {
0042
0043
0044 #ifndef DOXYGEN_NO_DETAIL
0045 namespace detail { namespace densify
0046 {
0047
0048 template <typename Range>
0049 struct push_back_policy
0050 {
0051     typedef typename boost::range_value<Range>::type point_type;
0052
0053     inline explicit push_back_policy(Range & rng)
0054         : m_rng(rng)
0055     {}
0056
0057     inline void apply(point_type const& p)
0058     {
0059         range::push_back(m_rng, p);
0060     }
0061
0062 private:
0063     Range & m_rng;
0064 };
0065
0066 template <typename Range, typename Point>
0067 inline void convert_and_push_back(Range & range, Point const& p)
0068 {
0069     typename boost::range_value<Range>::type p2;
0070     geometry::detail::conversion::convert_point_to_point(p, p2);
0071     range::push_back(range, p2);
0072 }
0073
0074 template <bool AppendLastPoint = true>
0075 struct densify_range
0076 {
0077     template <typename FwdRng, typename MutRng, typename T, typename Strategies>
0078     static inline void apply(FwdRng const& rng, MutRng & rng_out,
0079                              T const& len, Strategies const& strategies)
0080     {
0081         typedef typename boost::range_value<FwdRng>::type point_t;
0082
0083         auto it = boost::begin(rng);
0084         auto const end = boost::end(rng);
0085
0086         if (it == end) // empty(rng)
0087         {
0088             return;
0089         }
0090
0091         auto strategy = strategies.densify(rng);
0092         push_back_policy<MutRng> policy(rng_out);
0093
0094         auto prev = it;
0095         for ( ++it ; it != end ; prev = it++)
0096         {
0097             point_t const& p0 = *prev;
0098             point_t const& p1 = *it;
0099
0100             convert_and_push_back(rng_out, p0);
0101
0102             strategy.apply(p0, p1, policy, len);
0103         }
0104
0105         if BOOST_GEOMETRY_CONSTEXPR (AppendLastPoint)
0106         {
0107             convert_and_push_back(rng_out, *prev); // back(rng)
0108         }
0109     }
0110 };
0111
0112 template <bool IsClosed1, bool IsClosed2> // false, X
0113 struct densify_ring
0114 {
0115     template <typename Geometry, typename GeometryOut, typename T, typename Strategies>
0116     static inline void apply(Geometry const& ring, GeometryOut & ring_out,
0117                              T const& len, Strategies const& strategies)
0118     {
0119         geometry::detail::densify::densify_range<true>
0120             ::apply(ring, ring_out, len, strategies);
0121
0122         if (boost::size(ring) <= 1)
0123             return;
0124
0125         auto const& p0 = range::back(ring);
0126         auto const& p1 = range::front(ring);
0127
0128         auto strategy = strategies.densify(ring);
0129         push_back_policy<GeometryOut> policy(ring_out);
0130
0131         strategy.apply(p0, p1, policy, len);
0132
0133         if BOOST_GEOMETRY_CONSTEXPR (IsClosed2)
0134         {
0135             convert_and_push_back(ring_out, p1);
0136         }
0137     }
0138 };
0139
0140 template <>
0141 struct densify_ring<true, true>
0142     : densify_range<true>
0143 {};
0144
0145 template <>
0146 struct densify_ring<true, false>
0147     : densify_range<false>
0148 {};
0149
0150 struct densify_convert
0151 {
0152     template <typename GeometryIn, typename GeometryOut, typename T, typename Strategy>
0153     static void apply(GeometryIn const& in, GeometryOut &out,
0154                       T const& , Strategy const& )
0155     {
0156         geometry::convert(in, out);
0157     }
0158 };
0159
0160 }} // namespace detail::densify
0161 #endif // DOXYGEN_NO_DETAIL
0162
0163
0164 #ifndef DOXYGEN_NO_DISPATCH
0165 namespace dispatch
0166 {
0167
0168
0169 template
0170 <
0171     typename Geometry,
0172     typename GeometryOut,
0173     typename Tag1 = typename tag<Geometry>::type,
0174     typename Tag2 = typename tag<GeometryOut>::type
0175 >
0176 struct densify
0177     : not_implemented<Tag1, Tag2>
0178 {};
0179
0180 template <typename Geometry, typename GeometryOut>
0181 struct densify<Geometry, GeometryOut, point_tag, point_tag>
0182     : geometry::detail::densify::densify_convert
0183 {};
0184
0185 template <typename Geometry, typename GeometryOut>
0186 struct densify<Geometry, GeometryOut, segment_tag, segment_tag>
0187     : geometry::detail::densify::densify_convert
0188 {};
0189
0190 template <typename Geometry, typename GeometryOut>
0191 struct densify<Geometry, GeometryOut, box_tag, box_tag>
0192     : geometry::detail::densify::densify_convert
0193 {};
0194
0195 template <typename Geometry, typename GeometryOut>
0196 struct densify<Geometry, GeometryOut, multi_point_tag, multi_point_tag>
0197     : geometry::detail::densify::densify_convert
0198 {};
0199
0200 template <typename Geometry, typename GeometryOut>
0201 struct densify<Geometry, GeometryOut, linestring_tag, linestring_tag>
0202     : geometry::detail::densify::densify_range<>
0203 {};
0204
0205 template <typename Geometry, typename GeometryOut>
0206 struct densify<Geometry, GeometryOut, multi_linestring_tag, multi_linestring_tag>
0207 {
0208     template <typename T, typename Strategy>
0209     static void apply(Geometry const& mls, GeometryOut & mls_out,
0210                       T const& len, Strategy const& strategy)
0211     {
0212         std::size_t count = boost::size(mls);
0213         range::resize(mls_out, count);
0214
0215         for (std::size_t i = 0 ; i < count ; ++i)
0216         {
0217             geometry::detail::densify::densify_range<>
0218                 ::apply(range::at(mls, i), range::at(mls_out, i),
0219                         len, strategy);
0220         }
0221     }
0222 };
0223
0224 template <typename Geometry, typename GeometryOut>
0225 struct densify<Geometry, GeometryOut, ring_tag, ring_tag>
0226     : geometry::detail::densify::densify_ring
0227         <
0228             geometry::closure<Geometry>::value != geometry::open,
0229             geometry::closure<GeometryOut>::value != geometry::open
0230         >
0231 {};
0232
0233 template <typename Geometry, typename GeometryOut>
0234 struct densify<Geometry, GeometryOut, polygon_tag, polygon_tag>
0235 {
0236     template <typename T, typename Strategy>
0237     static void apply(Geometry const& poly, GeometryOut & poly_out,
0238                       T const& len, Strategy const& strategy)
0239     {
0240         apply_ring(exterior_ring(poly), exterior_ring(poly_out),
0241                    len, strategy);
0242
0243         std::size_t count = boost::size(interior_rings(poly));
0244         range::resize(interior_rings(poly_out), count);
0245
0246         for (std::size_t i = 0 ; i < count ; ++i)
0247         {
0248             apply_ring(range::at(interior_rings(poly), i),
0249                        range::at(interior_rings(poly_out), i),
0250                        len, strategy);
0251         }
0252     }
0253
0254     template <typename Ring, typename RingOut, typename T, typename Strategy>
0255     static void apply_ring(Ring const& ring, RingOut & ring_out,
0256                            T const& len, Strategy const& strategy)
0257     {
0258         densify<Ring, RingOut, ring_tag, ring_tag>
0259             ::apply(ring, ring_out, len, strategy);
0260     }
0261 };
0262
0263 template <typename Geometry, typename GeometryOut>
0264 struct densify<Geometry, GeometryOut, multi_polygon_tag, multi_polygon_tag>
0265 {
0266     template <typename T, typename Strategy>
0267     static void apply(Geometry const& mpoly, GeometryOut & mpoly_out,
0268                       T const& len, Strategy const& strategy)
0269     {
0270         std::size_t count = boost::size(mpoly);
0271         range::resize(mpoly_out, count);
0272
0273         for (std::size_t i = 0 ; i < count ; ++i)
0274         {
0275             apply_poly(range::at(mpoly, i),
0276                        range::at(mpoly_out, i),
0277                        len, strategy);
0278         }
0279     }
0280
0281     template <typename Poly, typename PolyOut, typename T, typename Strategy>
0282     static void apply_poly(Poly const& poly, PolyOut & poly_out,
0283                            T const& len, Strategy const& strategy)
0284     {
0285         densify<Poly, PolyOut, polygon_tag, polygon_tag>::
0286             apply(poly, poly_out, len, strategy);
0287     }
0288 };
0289
0290
0291 } // namespace dispatch
0292 #endif // DOXYGEN_NO_DISPATCH
0293
0294
0295 namespace resolve_strategy
0296 {
0297
0298 template
0299 <
0300     typename Strategies,
0301     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0302 >
0303 struct densify
0304 {
0305     template <typename Geometry, typename Distance>
0306     static inline void apply(Geometry const& geometry,
0307                              Geometry& out,
0308                              Distance const& max_distance,
0309                              Strategies const& strategies)
0310     {
0311         dispatch::densify
0312             <
0313                 Geometry, Geometry
0314             >::apply(geometry, out, max_distance, strategies);
0315     }
0316 };
0317
0318 template <typename Strategy>
0319 struct densify<Strategy, false>
0320 {
0321     template <typename Geometry, typename Distance>
0322     static inline void apply(Geometry const& geometry,
0323                              Geometry& out,
0324                              Distance const& max_distance,
0325                              Strategy const& strategy)
0326     {
0327         using strategies::densify::services::strategy_converter;
0328
0329         dispatch::densify
0330             <
0331                 Geometry, Geometry
0332             >::apply(geometry, out, max_distance,
0333                      strategy_converter<Strategy>::get(strategy));
0334     }
0335 };
0336
0337 template <>
0338 struct densify<default_strategy, false>
0339 {
0340     template <typename Geometry, typename Distance>
0341     static inline void apply(Geometry const& geometry,
0342                              Geometry& out,
0343                              Distance const& max_distance,
0344                              default_strategy const&)
0345     {
0346         typedef typename strategies::densify::services::default_strategy
0347             <
0348                 Geometry
0349             >::type strategies_type;
0350
0351         dispatch::densify
0352             <
0353                 Geometry, Geometry
0354             >::apply(geometry, out, max_distance, strategies_type());
0355     }
0356 };
0357
0358 } // namespace resolve_strategy
0359
0360
0361 namespace resolve_dynamic {
0362
0363 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
0364 struct densify
0365 {
0366     template <typename Distance, typename Strategy>
0367     static inline void apply(Geometry const& geometry,
0368                              Geometry& out,
0369                              Distance const& max_distance,
0370                              Strategy const& strategy)
0371     {
0372         resolve_strategy::densify
0373             <
0374                 Strategy
0375             >::apply(geometry, out, max_distance, strategy);
0376     }
0377 };
0378
0379 template <typename Geometry>
0380 struct densify<Geometry, dynamic_geometry_tag>
0381 {
0382     template <typename Distance, typename Strategy>
0383     static inline void
0384     apply(Geometry const& geometry,
0385           Geometry& out,
0386           Distance const& max_distance,
0387           Strategy const& strategy)
0388     {
0389         traits::visit<Geometry>::apply([&](auto const& g)
0390         {
0391             using geom_t = util::remove_cref_t<decltype(g)>;
0392             geom_t o;
0393             densify<geom_t>::apply(g, o, max_distance, strategy);
0394             out = std::move(o);
0395         }, geometry);
0396     }
0397 };
0398
0399 template <typename Geometry>
0400 struct densify<Geometry, geometry_collection_tag>
0401 {
0402     template <typename Distance, typename Strategy>
0403     static inline void
0404     apply(Geometry const& geometry,
0405           Geometry& out,
0406           Distance const& max_distance,
0407           Strategy const& strategy)
0408     {
0409         detail::visit_breadth_first([&](auto const& g)
0410         {
0411             using geom_t = util::remove_cref_t<decltype(g)>;
0412             geom_t o;
0413             densify<geom_t>::apply(g, o, max_distance, strategy);
0414             traits::emplace_back<Geometry>::apply(out, std::move(o));
0415             return true;
0416         }, geometry);
0417     }
0418 };
0419
0420 } // namespace resolve_dynamic
0421
0422
0423 /*!
0424 \brief Densify a geometry using a specified strategy
0425 \ingroup densify
0426 \tparam Geometry \tparam_geometry
0427 \tparam Distance A numerical distance measure
0428 \tparam Strategy A type fulfilling a DensifyStrategy concept
0429 \param geometry Input geometry, to be densified
0430 \param out Output geometry, densified version of the input geometry
0431 \param max_distance Distance threshold (in units depending on strategy)
0432 \param strategy Densify strategy to be used for densification
0433
0434 \qbk{distinguish,with strategy}
0435 \qbk{[include reference/algorithms/densify.qbk]}
0436
0437 \qbk{
0438 [heading Available Strategies]
0439 \* [link geometry.reference.strategies.strategy_densify_cartesian Cartesian]
0440 \* [link geometry.reference.strategies.strategy_densify_spherical Spherical]
0441 \* [link geometry.reference.strategies.strategy_densify_geographic Geographic]
0442
0443 [heading Example]
0444 [densify_strategy]
0445 [densify_strategy_output]
0446
0447 [heading See also]
0448 \* [link geometry.reference.algorithms.line_interpolate line_interpolate]
0449 }
0450 */
0451 template <typename Geometry, typename Distance, typename Strategy>
0452 inline void densify(Geometry const& geometry,
0453                     Geometry& out,
0454                     Distance const& max_distance,
0455                     Strategy const& strategy)
0456 {
0457     concepts::check<Geometry>();
0458
0459     if (max_distance <= Distance(0))
0460     {
0461         BOOST_THROW_EXCEPTION(geometry::invalid_input_exception());
0462     }
0463
0464     geometry::clear(out);
0465
0466     resolve_dynamic::densify
0467         <
0468             Geometry
0469         >::apply(geometry, out, max_distance, strategy);
0470 }
0471
0472
0473 /*!
0474 \brief Densify a geometry
0475 \ingroup densify
0476 \tparam Geometry \tparam_geometry
0477 \tparam Distance A numerical distance measure
0478 \param geometry Input geometry, to be densified
0479 \param out Output geometry, densified version of the input geometry
0480 \param max_distance Distance threshold (in units depending on coordinate system)
0481
0482 \qbk{[include reference/algorithms/densify.qbk]}
0483
0484 \qbk{
0485 [heading Example]
0486 [densify]
0487 [densify_output]
0488
0489 [heading See also]
0490 \* [link geometry.reference.algorithms.line_interpolate line_interpolate]
0491 }
0492 */
0493 template <typename Geometry, typename Distance>
0494 inline void densify(Geometry const& geometry,
0495                     Geometry& out,
0496                     Distance const& max_distance)
0497 {
0498     densify(geometry, out, max_distance, default_strategy());
0499 }
0500
0501
0502 }} // namespace boost::geometry
0503
0504 #endif // BOOST_GEOMETRY_ALGORITHMS_DENSIFY_HPP