geometry/algorithms/simplify.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2023-2024 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2018-2023.
0009 // Modifications copyright (c) 2018-2023 Oracle and/or its affiliates.
0010 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0011 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0012
0013 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0014 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0015
0016 // Use, modification and distribution is subject to the Boost Software License,
0017 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0018 // http://www.boost.org/LICENSE_1_0.txt)
0019
0020 #ifndef BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP
0021 #define BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP
0022
0023 #include <cstddef>
0024 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
0025 #include <iostream>
0026 #endif
0027 #include <set>
0028 #include <vector>
0029
0030 #include <boost/core/addressof.hpp>
0031 #include <boost/range/begin.hpp>
0032 #include <boost/range/end.hpp>
0033 #include <boost/range/size.hpp>
0034 #include <boost/range/value_type.hpp>
0035
0036 #include <boost/geometry/algorithms/area.hpp>
0037 #include <boost/geometry/algorithms/clear.hpp>
0038 #include <boost/geometry/algorithms/convert.hpp>
0039 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
0040 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0041 #include <boost/geometry/algorithms/detail/visit.hpp>
0042 #include <boost/geometry/algorithms/not_implemented.hpp>
0043 #include <boost/geometry/algorithms/is_empty.hpp>
0044 #include <boost/geometry/algorithms/perimeter.hpp>
0045
0046 #include <boost/geometry/core/cs.hpp>
0047 #include <boost/geometry/core/closure.hpp>
0048 #include <boost/geometry/core/exterior_ring.hpp>
0049 #include <boost/geometry/core/interior_rings.hpp>
0050 #include <boost/geometry/core/mutable_range.hpp>
0051 #include <boost/geometry/core/tags.hpp>
0052 #include <boost/geometry/core/visit.hpp>
0053
0054 #include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility
0055 #include <boost/geometry/geometries/concepts/check.hpp>
0056
0057 #include <boost/geometry/strategies/default_strategy.hpp>
0058 #include <boost/geometry/strategies/detail.hpp>
0059 #include <boost/geometry/strategies/distance/comparable.hpp>
0060 #include <boost/geometry/strategies/simplify/cartesian.hpp>
0061 #include <boost/geometry/strategies/simplify/geographic.hpp>
0062 #include <boost/geometry/strategies/simplify/spherical.hpp>
0063
0064 #include <boost/geometry/util/constexpr.hpp>
0065 #include <boost/geometry/util/type_traits_std.hpp>
0066
0067 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
0068 #include <boost/geometry/io/dsv/write.hpp>
0069 #endif
0070
0071 namespace boost { namespace geometry
0072 {
0073
0074 #ifndef DOXYGEN_NO_DETAIL
0075 namespace detail { namespace simplify
0076 {
0077
0078 /*!
0079 \brief Small wrapper around a point, with an extra member "included"
0080 \details
0081     It has a const-reference to the original point (so no copy here)
0082 \tparam the enclosed point type
0083 */
0084 template <typename Point>
0085 struct douglas_peucker_point
0086 {
0087     typedef Point point_type;
0088
0089     Point const* p;
0090     bool included;
0091
0092     inline douglas_peucker_point(Point const& ap)
0093         : p(boost::addressof(ap))
0094         , included(false)
0095     {}
0096 };
0097
0098 /*!
0099 \brief Implements the simplify algorithm.
0100 \details The douglas_peucker policy simplifies a linestring, ring or
0101     vector of points using the well-known Douglas-Peucker algorithm.
0102 \note This strategy uses itself a point-segment potentially comparable
0103     distance strategy
0104 \author Barend and Maarten, 1995/1996
0105 \author Barend, revised for Generic Geometry Library, 2008
0106 */
0107
0108 /*
0109 For the algorithm, see for example:
0110  - http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
0111  - http://www2.dcs.hull.ac.uk/CISRG/projects/Royal-Inst/demos/dp.html
0112 */
0113 class douglas_peucker
0114 {
0115     template <typename Iterator, typename Distance, typename PSDistanceStrategy>
0116     static inline void consider(Iterator begin,
0117                                 Iterator end,
0118                                 Distance const& max_dist,
0119                                 int& n,
0120                                 PSDistanceStrategy const& ps_distance_strategy)
0121     {
0122         typedef typename std::iterator_traits<Iterator>::value_type::point_type point_type;
0123         typedef decltype(ps_distance_strategy.apply(std::declval<point_type>(),
0124                             std::declval<point_type>(), std::declval<point_type>())) distance_type;
0125
0126         std::size_t size = end - begin;
0127
0128         // size must be at least 3
0129         // because we want to consider a candidate point in between
0130         if (size <= 2)
0131         {
0132 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
0133             if (begin != end)
0134             {
0135                 std::cout << "ignore between " << dsv(*(begin->p))
0136                     << " and " << dsv(*((end - 1)->p))
0137                     << " size=" << size << std::endl;
0138             }
0139             std::cout << "return because size=" << size << std::endl;
0140 #endif
0141             return;
0142         }
0143
0144         Iterator last = end - 1;
0145
0146 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
0147         std::cout << "find between " << dsv(*(begin->p))
0148             << " and " << dsv(*(last->p))
0149             << " size=" << size << std::endl;
0150 #endif
0151
0152
0153         // Find most far point, compare to the current segment
0154         //geometry::segment<Point const> s(begin->p, last->p);
0155         distance_type md(-1.0); // any value < 0
0156         Iterator candidate = end;
0157         for (Iterator it = begin + 1; it != last; ++it)
0158         {
0159             distance_type dist = ps_distance_strategy.apply(*(it->p), *(begin->p), *(last->p));
0160
0161 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
0162             std::cout << "consider " << dsv(*(it->p))
0163                 << " at " << double(dist)
0164                 << ((dist > max_dist) ? " maybe" : " no")
0165                 << std::endl;
0166
0167 #endif
0168             if (md < dist)
0169             {
0170                 md = dist;
0171                 candidate = it;
0172             }
0173         }
0174
0175         // If a point is found, set the include flag
0176         // and handle segments in between recursively
0177         if (max_dist < md && candidate != end)
0178         {
0179 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
0180             std::cout << "use " << dsv(candidate->p) << std::endl;
0181 #endif
0182
0183             candidate->included = true;
0184             n++;
0185
0186             consider(begin, candidate + 1, max_dist, n, ps_distance_strategy);
0187             consider(candidate, end, max_dist, n, ps_distance_strategy);
0188         }
0189     }
0190
0191     template
0192     <
0193         typename Range, typename OutputIterator, typename Distance,
0194         typename PSDistanceStrategy
0195     >
0196     static inline OutputIterator apply_(Range const& range,
0197                                         OutputIterator out,
0198                                         Distance const& max_distance,
0199                                         PSDistanceStrategy const& ps_distance_strategy)
0200     {
0201 #ifdef BOOST_GEOMETRY_DEBUG_DOUGLAS_PEUCKER
0202             std::cout << "max distance: " << max_distance
0203                       << std::endl << std::endl;
0204 #endif
0205
0206         typedef typename boost::range_value<Range>::type point_type;
0207         typedef douglas_peucker_point<point_type> dp_point_type;
0208
0209         // Copy coordinates, a vector of references to all points
0210         std::vector<dp_point_type> ref_candidates(boost::begin(range),
0211                                                   boost::end(range));
0212
0213         // Include first and last point of line,
0214         // they are always part of the line
0215         int n = 2;
0216         ref_candidates.front().included = true;
0217         ref_candidates.back().included = true;
0218
0219         // Get points, recursively, including them if they are further away
0220         // than the specified distance
0221         consider(boost::begin(ref_candidates), boost::end(ref_candidates), max_distance, n,
0222                  ps_distance_strategy);
0223
0224         // Copy included elements to the output
0225         for (auto it = boost::begin(ref_candidates); it != boost::end(ref_candidates); ++it)
0226         {
0227             if (it->included)
0228             {
0229                 // copy-coordinates does not work because OutputIterator
0230                 // does not model Point (??)
0231                 //geometry::convert(*(it->p), *out);
0232                 *out = *(it->p);
0233                 ++out;
0234             }
0235         }
0236         return out;
0237     }
0238
0239 public:
0240     template <typename Range, typename OutputIterator, typename Distance, typename Strategies>
0241     static inline OutputIterator apply(Range const& range,
0242                                        OutputIterator out,
0243                                        Distance const& max_distance,
0244                                        Strategies const& strategies)
0245     {
0246         typedef typename boost::range_value<Range>::type point_type;
0247         typedef decltype(strategies.distance(detail::dummy_point(), detail::dummy_segment())) distance_strategy_type;
0248
0249         typedef typename strategy::distance::services::comparable_type
0250             <
0251                 distance_strategy_type
0252             >::type comparable_distance_strategy_type;
0253
0254         comparable_distance_strategy_type cstrategy = strategy::distance::services::get_comparable
0255             <
0256                 distance_strategy_type
0257             >::apply(strategies.distance(detail::dummy_point(), detail::dummy_segment()));
0258
0259         return apply_(range, out,
0260                       strategy::distance::services::result_from_distance
0261                           <
0262                               comparable_distance_strategy_type, point_type, point_type
0263                           >::apply(cstrategy, max_distance),
0264                       cstrategy);
0265     }
0266 };
0267
0268
0269 template <typename Range, typename Strategies>
0270 inline bool is_degenerate(Range const& range, Strategies const& strategies)
0271 {
0272     return boost::size(range) == 2
0273         && detail::equals::equals_point_point(geometry::range::front(range),
0274                                               geometry::range::back(range),
0275                                               strategies);
0276 }
0277
0278 struct simplify_range_insert
0279 {
0280     template
0281     <
0282         typename Range, typename OutputIterator, typename Distance,
0283         typename Impl, typename Strategies
0284     >
0285     static inline void apply(Range const& range, OutputIterator out,
0286                              Distance const& max_distance,
0287                              Impl const& impl,
0288                              Strategies const& strategies)
0289     {
0290         if (is_degenerate(range, strategies))
0291         {
0292             std::copy(boost::begin(range), boost::begin(range) + 1, out);
0293         }
0294         else if (boost::size(range) <= 2 || max_distance < 0)
0295         {
0296             std::copy(boost::begin(range), boost::end(range), out);
0297         }
0298         else
0299         {
0300             impl.apply(range, out, max_distance, strategies);
0301         }
0302     }
0303 };
0304
0305
0306 struct simplify_copy_assign
0307 {
0308     template
0309     <
0310         typename In, typename Out, typename Distance,
0311         typename Impl, typename Strategies
0312     >
0313     static inline void apply(In const& in, Out& out,
0314                              Distance const& ,
0315                              Impl const& ,
0316                              Strategies const& )
0317     {
0318         out = in;
0319     }
0320 };
0321
0322
0323 struct simplify_copy
0324 {
0325     template
0326     <
0327         typename RangeIn, typename RangeOut, typename Distance,
0328         typename Impl, typename Strategies
0329     >
0330     static inline void apply(RangeIn const& range, RangeOut& out,
0331                              Distance const& ,
0332                              Impl const& ,
0333                              Strategies const& )
0334     {
0335         std::copy(boost::begin(range), boost::end(range),
0336                   geometry::range::back_inserter(out));
0337     }
0338 };
0339
0340
0341 template <std::size_t MinimumToUseStrategy>
0342 struct simplify_range
0343 {
0344     template
0345     <
0346         typename RangeIn, typename RangeOut, typename Distance,
0347         typename Impl, typename Strategies
0348     >
0349     static inline void apply(RangeIn const& range, RangeOut& out,
0350                              Distance const& max_distance,
0351                              Impl const& impl,
0352                              Strategies const& strategies)
0353     {
0354         // For a RING:
0355         // Note that, especially if max_distance is too large,
0356         // the output ring might be self intersecting while the input ring is
0357         // not, although chances are low in normal polygons
0358
0359         if (boost::size(range) <= MinimumToUseStrategy || max_distance < 0)
0360         {
0361             simplify_copy::apply(range, out, max_distance, impl, strategies);
0362         }
0363         else
0364         {
0365             simplify_range_insert::apply(range, geometry::range::back_inserter(out),
0366                                          max_distance, impl, strategies);
0367         }
0368
0369         // Verify the two remaining points are equal. If so, remove one of them.
0370         // This can cause the output being under the minimum size
0371         if (is_degenerate(out, strategies))
0372         {
0373             range::resize(out, 1);
0374         }
0375     }
0376 };
0377
0378 struct simplify_ring
0379 {
0380 private :
0381     template <typename Area>
0382     static inline int area_sign(Area const& area)
0383     {
0384         return area > 0 ? 1 : area < 0 ? -1 : 0;
0385     }
0386
0387     template <typename Ring, typename Strategies>
0388     static std::size_t get_opposite(std::size_t index, Ring const& ring,
0389                                     Strategies const& strategies)
0390     {
0391         // TODO: Instead of calling the strategy call geometry::comparable_distance() ?
0392
0393         auto const cdistance_strategy = strategies::distance::detail::make_comparable(strategies)
0394             .distance(detail::dummy_point(), detail::dummy_point());
0395
0396         using point_type = geometry::point_type_t<Ring>;
0397         using cdistance_type = decltype(cdistance_strategy.apply(
0398             std::declval<point_type>(), std::declval<point_type>()));
0399
0400         // Verify if it is NOT the case that all points are less than the
0401         // simplifying distance. If so, output is empty.
0402         cdistance_type max_cdistance(-1);
0403
0404         point_type const& point = range::at(ring, index);
0405         std::size_t i = 0;
0406         for (auto it = boost::begin(ring); it != boost::end(ring); ++it, ++i)
0407         {
0408             cdistance_type const cdistance = cdistance_strategy.apply(*it, point);
0409             if (cdistance > max_cdistance)
0410             {
0411                 max_cdistance = cdistance;
0412                 index = i;
0413             }
0414         }
0415         return index;
0416     }
0417
0418 public :
0419     template
0420     <
0421         typename RingIn, typename RingOut,
0422         typename Distance, typename Impl, typename Strategies
0423     >
0424     static inline void apply(RingIn const& ring, RingOut& out, Distance const& max_distance,
0425                              Impl const& impl, Strategies const& strategies)
0426     {
0427         std::size_t const size = boost::size(ring);
0428         if (size == 0)
0429         {
0430             return;
0431         }
0432
0433         constexpr bool is_closed_in = geometry::closure<RingIn>::value == closed;
0434         constexpr bool is_closed_out = geometry::closure<RingOut>::value == closed;
0435         constexpr bool is_clockwise_in = geometry::point_order<RingIn>::value == clockwise;
0436         constexpr bool is_clockwise_out = geometry::point_order<RingOut>::value == clockwise;
0437
0438         // TODO: instead of area() use calculate_point_order() ?
0439
0440         int const input_sign = area_sign(geometry::area(ring, strategies));
0441
0442         std::set<std::size_t> visited_indexes;
0443
0444         // Rotate it into a copied vector
0445         // (vector, because source type might not support rotation)
0446         // (duplicate end point will be simplified away)
0447         using point_type = geometry::point_type_t<RingIn>;
0448
0449         std::vector<point_type> rotated;
0450         rotated.reserve(size + 1); // 1 because open rings are closed
0451
0452         // Closing point (but it will not start here)
0453         std::size_t index = 0;
0454
0455         // Iterate (usually one iteration is enough)
0456         for (std::size_t iteration = 0; iteration < 4u; iteration++)
0457         {
0458             // Always take the opposite. Opposite guarantees that no point
0459             // "halfway" is chosen, creating an artefact (very narrow triangle)
0460             // Iteration 0: opposite to closing point (1/2, = on convex hull)
0461             //              (this will start simplification with that point
0462             //               and its opposite ~0)
0463             // Iteration 1: move a quarter on that ring, then opposite to 1/4
0464             //              (with its opposite 3/4)
0465             // Iteration 2: move an eight on that ring, then opposite (1/8)
0466             // Iteration 3: again move a quarter, then opposite (7/8)
0467             // So finally 8 "sides" of the ring have been examined (if it were
0468             // a semi-circle). Most probably, there are only 0 or 1 iterations.
0469             switch (iteration)
0470             {
0471                 case 1 : index = (index + size / 4) % size; break;
0472                 case 2 : index = (index + size / 8) % size; break;
0473                 case 3 : index = (index + size / 4) % size; break;
0474             }
0475             index = get_opposite(index, ring, strategies);
0476
0477             if (visited_indexes.count(index) > 0)
0478             {
0479                 // Avoid trying the same starting point more than once
0480                 continue;
0481             }
0482
0483             // Do not duplicate the closing point
0484             auto rot_end = boost::end(ring);
0485             std::size_t rot_index = index;
0486             if BOOST_GEOMETRY_CONSTEXPR (is_closed_in)
0487             {
0488                 if (size > 1)
0489                 {
0490                     --rot_end;
0491                     if (rot_index == size - 1) { rot_index = 0; }
0492                 }
0493             }
0494
0495             std::rotate_copy(boost::begin(ring), range::pos(ring, rot_index),
0496                              rot_end, std::back_inserter(rotated));
0497
0498             // Close the rotated copy
0499             rotated.push_back(range::at(ring, rot_index));
0500
0501             simplify_range<0>::apply(rotated, out, max_distance, impl, strategies);
0502
0503             // Open output if needed
0504             if BOOST_GEOMETRY_CONSTEXPR (! is_closed_out)
0505             {
0506                 if (boost::size(out) > 1)
0507                 {
0508                     range::pop_back(out);
0509                 }
0510             }
0511
0512             // TODO: instead of area() use calculate_point_order() ?
0513
0514             // Verify that what was positive, stays positive (or goes to 0)
0515             // and what was negative stays negative (or goes to 0)
0516             int const output_sign = area_sign(geometry::area(out, strategies));
0517             if (output_sign == input_sign)
0518             {
0519                 // Result is considered as satisfactory (usually this is the
0520                 // first iteration - only for small rings, having a scale
0521                 // similar to simplify_distance, next iterations are tried
0522                 return;
0523             }
0524
0525             // Original is simplified away. Possibly there is a solution
0526             // when another starting point is used
0527             geometry::clear(out);
0528
0529             if (iteration == 0
0530                 && geometry::perimeter(ring, strategies) < 3 * max_distance)
0531             {
0532                 // Check if it is useful to iterate. A minimal triangle has a
0533                 // perimeter of a bit more than 3 times the simplify distance
0534                 return;
0535             }
0536
0537             // Prepare next try
0538             visited_indexes.insert(index);
0539             rotated.clear();
0540         }
0541
0542         if BOOST_GEOMETRY_CONSTEXPR (is_clockwise_in != is_clockwise_out)
0543         {
0544             std::reverse(boost::begin(out), boost::end(out));
0545         }
0546     }
0547 };
0548
0549
0550 struct simplify_polygon
0551 {
0552 private:
0553
0554     template
0555     <
0556         typename IteratorIn,
0557         typename InteriorRingsOut,
0558         typename Distance,
0559         typename Impl,
0560         typename Strategies
0561     >
0562     static inline void iterate(IteratorIn begin, IteratorIn end,
0563                                InteriorRingsOut& interior_rings_out,
0564                                Distance const& max_distance,
0565                                Impl const& impl, Strategies const& strategies)
0566     {
0567         typedef typename boost::range_value<InteriorRingsOut>::type single_type;
0568         for (IteratorIn it = begin; it != end; ++it)
0569         {
0570             single_type out;
0571             simplify_ring::apply(*it, out, max_distance, impl, strategies);
0572             if (! geometry::is_empty(out))
0573             {
0574                 range::push_back(interior_rings_out, std::move(out));
0575             }
0576         }
0577     }
0578
0579     template
0580     <
0581         typename InteriorRingsIn,
0582         typename InteriorRingsOut,
0583         typename Distance,
0584         typename Impl,
0585         typename Strategies
0586     >
0587     static inline void apply_interior_rings(InteriorRingsIn const& interior_rings_in,
0588                                             InteriorRingsOut& interior_rings_out,
0589                                             Distance const& max_distance,
0590                                             Impl const& impl, Strategies const& strategies)
0591     {
0592         range::clear(interior_rings_out);
0593
0594         iterate(boost::begin(interior_rings_in), boost::end(interior_rings_in),
0595                 interior_rings_out,
0596                 max_distance,
0597                 impl, strategies);
0598     }
0599
0600 public:
0601     template
0602     <
0603         typename PolygonIn, typename PolygonOut,
0604         typename Distance, typename Impl, typename Strategies
0605     >
0606     static inline void apply(PolygonIn const& poly_in, PolygonOut& poly_out,
0607                              Distance const& max_distance,
0608                              Impl const& impl, Strategies const& strategies)
0609     {
0610         // Note that if there are inner rings, and distance is too large,
0611         // they might intersect with the outer ring in the output,
0612         // while it didn't in the input.
0613         simplify_ring::apply(exterior_ring(poly_in), exterior_ring(poly_out),
0614                              max_distance, impl, strategies);
0615
0616         apply_interior_rings(interior_rings(poly_in), interior_rings(poly_out),
0617                              max_distance, impl, strategies);
0618     }
0619 };
0620
0621
0622 template<typename Policy>
0623 struct simplify_multi
0624 {
0625     template
0626     <
0627         typename MultiGeometryIn, typename MultiGeometryOut,
0628         typename Distance, typename Impl, typename Strategies
0629     >
0630     static inline void apply(MultiGeometryIn const& multi, MultiGeometryOut& out,
0631                              Distance const& max_distance,
0632                              Impl const& impl, Strategies const& strategies)
0633     {
0634         range::clear(out);
0635
0636         using single_type = typename boost::range_value<MultiGeometryOut>::type;
0637
0638         for (auto it = boost::begin(multi); it != boost::end(multi); ++it)
0639         {
0640             single_type single_out;
0641             Policy::apply(*it, single_out, max_distance, impl, strategies);
0642             if (! geometry::is_empty(single_out))
0643             {
0644                 range::push_back(out, std::move(single_out));
0645             }
0646         }
0647     }
0648 };
0649
0650
0651 template <typename Geometry>
0652 struct has_same_tag_as
0653 {
0654     template <typename OtherGeometry>
0655     struct pred
0656         : std::is_same<geometry::tag_t<Geometry>, geometry::tag_t<OtherGeometry>>
0657     {};
0658 };
0659
0660 template <typename StaticGeometryIn, typename DynamicGeometryOut>
0661 struct static_geometry_type
0662 {
0663     using type = typename util::sequence_find_if
0664         <
0665             typename traits::geometry_types<DynamicGeometryOut>::type,
0666             detail::simplify::has_same_tag_as<StaticGeometryIn>::template pred
0667         >::type;
0668
0669     BOOST_GEOMETRY_STATIC_ASSERT(
0670         (! std::is_void<type>::value),
0671         "Unable to find corresponding geometry in GeometryOut",
0672         StaticGeometryIn, DynamicGeometryOut);
0673 };
0674
0675
0676 }} // namespace detail::simplify
0677 #endif // DOXYGEN_NO_DETAIL
0678
0679
0680 #ifndef DOXYGEN_NO_DISPATCH
0681 namespace dispatch
0682 {
0683
0684 template
0685 <
0686     typename GeometryIn,
0687     typename GeometryOut,
0688     typename TagIn = tag_t<GeometryIn>,
0689     typename TagOut = tag_t<GeometryOut>
0690 >
0691 struct simplify: not_implemented<TagIn, TagOut>
0692 {};
0693
0694 template <typename PointIn, typename PointOut>
0695 struct simplify<PointIn, PointOut, point_tag, point_tag>
0696 {
0697     template <typename Distance, typename Impl, typename Strategy>
0698     static inline void apply(PointIn const& point, PointOut& out, Distance const& ,
0699                              Impl const& , Strategy const& )
0700     {
0701         geometry::convert(point, out);
0702     }
0703 };
0704
0705 template <typename SegmentIn, typename SegmentOut>
0706 struct simplify<SegmentIn, SegmentOut, segment_tag, segment_tag>
0707     : detail::simplify::simplify_copy_assign
0708 {};
0709
0710 template <typename BoxIn, typename BoxOut>
0711 struct simplify<BoxIn, BoxOut, box_tag, box_tag>
0712     : detail::simplify::simplify_copy_assign
0713 {};
0714
0715 // Linestring, keep 2 points (unless those points are the same)
0716 template <typename LinestringIn, typename LinestringOut>
0717 struct simplify<LinestringIn, LinestringOut, linestring_tag, linestring_tag>
0718     : detail::simplify::simplify_range<2>
0719 {};
0720
0721 template <typename RingIn, typename RingOut>
0722 struct simplify<RingIn, RingOut, ring_tag, ring_tag>
0723     : detail::simplify::simplify_ring
0724 {};
0725
0726 template <typename PolygonIn, typename PolygonOut>
0727 struct simplify<PolygonIn, PolygonOut, polygon_tag, polygon_tag>
0728     : detail::simplify::simplify_polygon
0729 {};
0730
0731 template <typename MultiPointIn, typename MultiPointOut>
0732 struct simplify<MultiPointIn, MultiPointOut, multi_point_tag, multi_point_tag>
0733     : detail::simplify::simplify_copy
0734 {};
0735
0736 template <typename MultiLinestringIn, typename MultiLinestringOut>
0737 struct simplify<MultiLinestringIn, MultiLinestringOut, multi_linestring_tag, multi_linestring_tag>
0738     : detail::simplify::simplify_multi<detail::simplify::simplify_range<2> >
0739 {};
0740
0741 template <typename MultiPolygonIn, typename MultiPolygonOut>
0742 struct simplify<MultiPolygonIn, MultiPolygonOut, multi_polygon_tag, multi_polygon_tag>
0743     : detail::simplify::simplify_multi<detail::simplify::simplify_polygon>
0744 {};
0745
0746
0747 template
0748 <
0749     typename Geometry,
0750     typename Tag = tag_t<Geometry>
0751 >
0752 struct simplify_insert: not_implemented<Tag>
0753 {};
0754
0755
0756 template <typename Linestring>
0757 struct simplify_insert<Linestring, linestring_tag>
0758     : detail::simplify::simplify_range_insert
0759 {};
0760
0761 template <typename Ring>
0762 struct simplify_insert<Ring, ring_tag>
0763     : detail::simplify::simplify_range_insert
0764 {};
0765
0766
0767 } // namespace dispatch
0768 #endif // DOXYGEN_NO_DISPATCH
0769
0770
0771 namespace resolve_strategy
0772 {
0773
0774 template
0775 <
0776     typename Strategies,
0777     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0778 >
0779 struct simplify
0780 {
0781     template <typename GeometryIn, typename GeometryOut, typename Distance>
0782     static inline void apply(GeometryIn const& geometry,
0783                              GeometryOut& out,
0784                              Distance const& max_distance,
0785                              Strategies const& strategies)
0786     {
0787         dispatch::simplify
0788             <
0789                 GeometryIn, GeometryOut
0790             >::apply(geometry, out, max_distance,
0791                      detail::simplify::douglas_peucker(),
0792                      strategies);
0793     }
0794 };
0795
0796 template <typename Strategy>
0797 struct simplify<Strategy, false>
0798 {
0799     template <typename GeometryIn, typename GeometryOut, typename Distance>
0800     static inline void apply(GeometryIn const& geometry,
0801                              GeometryOut& out,
0802                              Distance const& max_distance,
0803                              Strategy const& strategy)
0804     {
0805         using strategies::simplify::services::strategy_converter;
0806
0807         simplify
0808             <
0809                 decltype(strategy_converter<Strategy>::get(strategy))
0810             >::apply(geometry, out, max_distance,
0811                      strategy_converter<Strategy>::get(strategy));
0812     }
0813 };
0814
0815 template <>
0816 struct simplify<default_strategy, false>
0817 {
0818     template <typename GeometryIn, typename GeometryOut, typename Distance>
0819     static inline void apply(GeometryIn const& geometry,
0820                              GeometryOut& out,
0821                              Distance const& max_distance,
0822                              default_strategy)
0823     {
0824         // NOTE: Alternatively take two geometry types in default_strategy
0825         using cs_tag1_t = geometry::cs_tag_t<GeometryIn>;
0826         using cs_tag2_t = geometry::cs_tag_t<GeometryOut>;
0827         BOOST_GEOMETRY_STATIC_ASSERT(
0828             (std::is_same<cs_tag1_t, cs_tag2_t>::value),
0829             "Incompatible coordinate systems",
0830             cs_tag1_t, cs_tag2_t);
0831
0832         typedef typename strategies::simplify::services::default_strategy
0833             <
0834                 GeometryIn
0835             >::type strategy_type;
0836
0837         simplify
0838             <
0839                 strategy_type
0840             >::apply(geometry, out, max_distance, strategy_type());
0841     }
0842 };
0843
0844 template
0845 <
0846     typename Strategies,
0847     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0848 >
0849 struct simplify_insert
0850 {
0851     template<typename Geometry, typename OutputIterator, typename Distance>
0852     static inline void apply(Geometry const& geometry,
0853                              OutputIterator& out,
0854                              Distance const& max_distance,
0855                              Strategies const& strategies)
0856     {
0857         dispatch::simplify_insert
0858             <
0859                 Geometry
0860             >::apply(geometry, out, max_distance,
0861                      detail::simplify::douglas_peucker(),
0862                      strategies);
0863     }
0864 };
0865
0866 template <typename Strategy>
0867 struct simplify_insert<Strategy, false>
0868 {
0869     template<typename Geometry, typename OutputIterator, typename Distance>
0870     static inline void apply(Geometry const& geometry,
0871                              OutputIterator& out,
0872                              Distance const& max_distance,
0873                              Strategy const& strategy)
0874     {
0875         using strategies::simplify::services::strategy_converter;
0876
0877         simplify_insert
0878             <
0879                 decltype(strategy_converter<Strategy>::get(strategy))
0880             >::apply(geometry, out, max_distance,
0881                      strategy_converter<Strategy>::get(strategy));
0882     }
0883 };
0884
0885 template <>
0886 struct simplify_insert<default_strategy, false>
0887 {
0888     template <typename Geometry, typename OutputIterator, typename Distance>
0889     static inline void apply(Geometry const& geometry,
0890                              OutputIterator& out,
0891                              Distance const& max_distance,
0892                              default_strategy)
0893     {
0894         typedef typename strategies::simplify::services::default_strategy
0895             <
0896                 Geometry
0897             >::type strategy_type;
0898
0899         simplify_insert
0900             <
0901                 strategy_type
0902             >::apply(geometry, out, max_distance, strategy_type());
0903     }
0904 };
0905
0906 } // namespace resolve_strategy
0907
0908
0909 namespace resolve_dynamic {
0910
0911 template
0912 <
0913     typename GeometryIn, typename GeometryOut,
0914     typename TagIn = tag_t<GeometryIn>,
0915     typename TagOut = tag_t<GeometryOut>
0916 >
0917 struct simplify
0918 {
0919     template <typename Distance, typename Strategy>
0920     static inline void apply(GeometryIn const& geometry,
0921                              GeometryOut& out,
0922                              Distance const& max_distance,
0923                              Strategy const& strategy)
0924     {
0925         resolve_strategy::simplify<Strategy>::apply(geometry, out, max_distance, strategy);
0926     }
0927 };
0928
0929 template <typename GeometryIn, typename GeometryOut>
0930 struct simplify<GeometryIn, GeometryOut, dynamic_geometry_tag, dynamic_geometry_tag>
0931 {
0932     template <typename Distance, typename Strategy>
0933     static inline void apply(GeometryIn const& geometry,
0934                              GeometryOut& out,
0935                              Distance const& max_distance,
0936                              Strategy const& strategy)
0937     {
0938         traits::visit<GeometryIn>::apply([&](auto const& g)
0939         {
0940             using geom_t = util::remove_cref_t<decltype(g)>;
0941             using detail::simplify::static_geometry_type;
0942             using geom_out_t = typename static_geometry_type<geom_t, GeometryOut>::type;
0943             geom_out_t o;
0944             simplify<geom_t, geom_out_t>::apply(g, o, max_distance, strategy);
0945             out = std::move(o);
0946         }, geometry);
0947     }
0948 };
0949
0950 template <typename GeometryIn, typename GeometryOut>
0951 struct simplify<GeometryIn, GeometryOut, geometry_collection_tag, geometry_collection_tag>
0952 {
0953     template <typename Distance, typename Strategy>
0954     static inline void apply(GeometryIn const& geometry,
0955                              GeometryOut& out,
0956                              Distance const& max_distance,
0957                              Strategy const& strategy)
0958     {
0959         detail::visit_breadth_first([&](auto const& g)
0960         {
0961             using geom_t = util::remove_cref_t<decltype(g)>;
0962             using detail::simplify::static_geometry_type;
0963             using geom_out_t = typename static_geometry_type<geom_t, GeometryOut>::type;
0964             geom_out_t o;
0965             simplify<geom_t, geom_out_t>::apply(g, o, max_distance, strategy);
0966             traits::emplace_back<GeometryOut>::apply(out, std::move(o));
0967             return true;
0968         }, geometry);
0969     }
0970 };
0971
0972 } // namespace resolve_dynamic
0973
0974
0975 /*!
0976 \brief Simplify a geometry using a specified strategy
0977 \ingroup simplify
0978 \tparam Geometry \tparam_geometry
0979 \tparam GeometryOut The output geometry
0980 \tparam Distance A numerical distance measure
0981 \tparam Strategy A type fulfilling a SimplifyStrategy concept
0982 \param geometry input geometry, to be simplified
0983 \param out output geometry, simplified version of the input geometry
0984 \param max_distance distance (in units of input coordinates) of a vertex
0985     to other segments to be removed
0986 \param strategy simplify strategy to be used for simplification
0987 \note The simplification is done with Douglas-Peucker algorithm
0988
0989 \image html svg_simplify_country.png "The image below presents the simplified country"
0990 \qbk{distinguish,with strategy}
0991 */
0992 template<typename Geometry, typename GeometryOut, typename Distance, typename Strategy>
0993 inline void simplify(Geometry const& geometry, GeometryOut& out,
0994                      Distance const& max_distance, Strategy const& strategy)
0995 {
0996     concepts::check<Geometry const>();
0997     concepts::check<GeometryOut>();
0998
0999     geometry::clear(out);
1000
1001     resolve_dynamic::simplify<Geometry, GeometryOut>::apply(geometry, out, max_distance, strategy);
1002 }
1003
1004
1005
1006
1007 /*!
1008 \brief Simplify a geometry
1009 \ingroup simplify
1010 \tparam Geometry \tparam_geometry
1011 \tparam GeometryOut The output geometry
1012 \tparam Distance \tparam_numeric
1013 \param geometry input geometry, to be simplified
1014 \param out output geometry, simplified version of the input geometry
1015 \param max_distance distance (in units of input coordinates) of a vertex
1016     to other segments to be removed
1017 \note The simplification is done with Douglas-Peucker algorithm
1018
1019 \qbk{[include reference/algorithms/simplify.qbk]}
1020  */
1021 template<typename Geometry, typename GeometryOut, typename Distance>
1022 inline void simplify(Geometry const& geometry, GeometryOut& out,
1023                      Distance const& max_distance)
1024 {
1025     concepts::check<Geometry const>();
1026     concepts::check<GeometryOut>();
1027
1028     geometry::simplify(geometry, out, max_distance, default_strategy());
1029 }
1030
1031
1032 #ifndef DOXYGEN_NO_DETAIL
1033 namespace detail { namespace simplify
1034 {
1035
1036
1037 /*!
1038 \brief Simplify a geometry, using an output iterator
1039     and a specified strategy
1040 \ingroup simplify
1041 \tparam Geometry \tparam_geometry
1042 \param geometry input geometry, to be simplified
1043 \param out output iterator, outputs all simplified points
1044 \param max_distance distance (in units of input coordinates) of a vertex
1045     to other segments to be removed
1046 \param strategy simplify strategy to be used for simplification
1047
1048 \qbk{distinguish,with strategy}
1049 \qbk{[include reference/algorithms/simplify.qbk]}
1050 */
1051 template<typename Geometry, typename OutputIterator, typename Distance, typename Strategy>
1052 inline void simplify_insert(Geometry const& geometry, OutputIterator out,
1053                             Distance const& max_distance, Strategy const& strategy)
1054 {
1055     concepts::check<Geometry const>();
1056
1057     resolve_strategy::simplify_insert<Strategy>::apply(geometry, out, max_distance, strategy);
1058 }
1059
1060 /*!
1061 \brief Simplify a geometry, using an output iterator
1062 \ingroup simplify
1063 \tparam Geometry \tparam_geometry
1064 \param geometry input geometry, to be simplified
1065 \param out output iterator, outputs all simplified points
1066 \param max_distance distance (in units of input coordinates) of a vertex
1067     to other segments to be removed
1068
1069 \qbk{[include reference/algorithms/simplify_insert.qbk]}
1070  */
1071 template<typename Geometry, typename OutputIterator, typename Distance>
1072 inline void simplify_insert(Geometry const& geometry, OutputIterator out,
1073                             Distance const& max_distance)
1074 {
1075     // Concept: output point type = point type of input geometry
1076     concepts::check<Geometry const>();
1077     concepts::check<point_type_t<Geometry>>();
1078
1079     simplify_insert(geometry, out, max_distance, default_strategy());
1080 }
1081
1082 }} // namespace detail::simplify
1083 #endif // DOXYGEN_NO_DETAIL
1084
1085
1086
1087 }} // namespace boost::geometry
1088
1089 #endif // BOOST_GEOMETRY_ALGORITHMS_SIMPLIFY_HPP