ceph/src/boost/boost/geometry/algorithms/correct.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2017-2020.
   9 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11
  12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  14
  15 // Use, modification and distribution is subject to the Boost Software License,
  16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  17 // http://www.boost.org/LICENSE_1_0.txt)
  18
  19 #ifndef BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
  20 #define BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
  21
  22
  23 #include <algorithm>
  24 #include <cstddef>
  25 #include <functional>
  26
  27 #include <boost/range/begin.hpp>
  28 #include <boost/range/end.hpp>
  29 #include <boost/range/value_type.hpp>
  30
  31 #include <boost/variant/apply_visitor.hpp>
  32 #include <boost/variant/static_visitor.hpp>
  33 #include <boost/variant/variant_fwd.hpp>
  34
  35 #include <boost/geometry/algorithms/correct_closure.hpp>
  36 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  37
  38 #include <boost/geometry/core/closure.hpp>
  39 #include <boost/geometry/core/cs.hpp>
  40 #include <boost/geometry/core/exterior_ring.hpp>
  41 #include <boost/geometry/core/interior_rings.hpp>
  42 #include <boost/geometry/core/mutable_range.hpp>
  43 #include <boost/geometry/core/ring_type.hpp>
  44 #include <boost/geometry/core/tags.hpp>
  45
  46 #include <boost/geometry/geometries/concepts/check.hpp>
  47
  48 #include <boost/geometry/algorithms/area.hpp>
  49 #include <boost/geometry/algorithms/detail/multi_modify.hpp>
  50 #include <boost/geometry/util/order_as_direction.hpp>
  51
  52 namespace boost { namespace geometry
  53 {
  54
  55 // Silence warning C4127: conditional expression is constant
  56 #if defined(_MSC_VER)
  57 #pragma warning(push)
  58 #pragma warning(disable : 4127)
  59 #endif
  60
  61 #ifndef DOXYGEN_NO_DETAIL
  62 namespace detail { namespace correct
  63 {
  64
  65 template <typename Geometry>
  66 struct correct_nop
  67 {
  68     template <typename Strategy>
  69     static inline void apply(Geometry& , Strategy const& )
  70     {}
  71 };
  72
  73
  74 template <typename Box, std::size_t Dimension, std::size_t DimensionCount>
  75 struct correct_box_loop
  76 {
  77     typedef typename coordinate_type<Box>::type coordinate_type;
  78
  79     static inline void apply(Box& box)
  80     {
  81         if (get<min_corner, Dimension>(box) > get<max_corner, Dimension>(box))
  82         {
  83             // Swap the coordinates
  84             coordinate_type max_value = get<min_corner, Dimension>(box);
  85             coordinate_type min_value = get<max_corner, Dimension>(box);
  86             set<min_corner, Dimension>(box, min_value);
  87             set<max_corner, Dimension>(box, max_value);
  88         }
  89
  90         correct_box_loop
  91             <
  92                 Box, Dimension + 1, DimensionCount
  93             >::apply(box);
  94     }
  95 };
  96
  97
  98
  99 template <typename Box, std::size_t DimensionCount>
 100 struct correct_box_loop<Box, DimensionCount, DimensionCount>
 101 {
 102     static inline void apply(Box& )
 103     {}
 104
 105 };
 106
 107
 108 // Correct a box: make min/max correct
 109 template <typename Box>
 110 struct correct_box
 111 {
 112     template <typename Strategy>
 113     static inline void apply(Box& box, Strategy const& )
 114     {
 115         // Currently only for Cartesian coordinates
 116         // (or spherical without crossing dateline)
 117         // Future version: adapt using strategies
 118         correct_box_loop
 119             <
 120                 Box, 0, dimension<Box>::type::value
 121             >::apply(box);
 122     }
 123 };
 124
 125
 126 // Close a ring, if not closed
 127 template <typename Ring, template <typename> class Predicate>
 128 struct correct_ring
 129 {
 130     typedef typename point_type<Ring>::type point_type;
 131     typedef typename coordinate_type<Ring>::type coordinate_type;
 132
 133     typedef detail::area::ring_area
 134             <
 135                 order_as_direction<geometry::point_order<Ring>::value>::value,
 136                 geometry::closure<Ring>::value
 137             > ring_area_type;
 138
 139
 140     template <typename Strategy>
 141     static inline void apply(Ring& r, Strategy const& strategy)
 142     {
 143         // Correct closure if necessary
 144         detail::correct_closure::close_or_open_ring<Ring>::apply(r);
 145
 146         // Check area
 147         typedef typename area_result<Ring, Strategy>::type area_result_type;
 148         Predicate<area_result_type> predicate;
 149         area_result_type const zero = 0;
 150         if (predicate(ring_area_type::apply(r,
 151                                             // TEMP - in the future (umbrella) strategy will be passed
 152                                             geometry::strategies::area::services::strategy_converter
 153                                                 <
 154                                                     Strategy
 155                                                 >::get(strategy)),
 156                       zero))
 157         {
 158             std::reverse(boost::begin(r), boost::end(r));
 159         }
 160     }
 161 };
 162
 163 // Correct a polygon: normalizes all rings, sets outer ring clockwise, sets all
 164 // inner rings counter clockwise (or vice versa depending on orientation)
 165 template <typename Polygon>
 166 struct correct_polygon
 167 {
 168     typedef typename ring_type<Polygon>::type ring_type;
 169
 170     template <typename Strategy>
 171     static inline void apply(Polygon& poly, Strategy const& strategy)
 172     {
 173         correct_ring
 174             <
 175                 ring_type,
 176                 std::less
 177             >::apply(exterior_ring(poly), strategy);
 178
 179         typename interior_return_type<Polygon>::type
 180             rings = interior_rings(poly);
 181         for (typename detail::interior_iterator<Polygon>::type
 182                 it = boost::begin(rings); it != boost::end(rings); ++it)
 183         {
 184             correct_ring
 185                 <
 186                     ring_type,
 187                     std::greater
 188                 >::apply(*it, strategy);
 189         }
 190     }
 191 };
 192
 193
 194 }} // namespace detail::correct
 195 #endif // DOXYGEN_NO_DETAIL
 196
 197
 198 #ifndef DOXYGEN_NO_DISPATCH
 199 namespace dispatch
 200 {
 201
 202 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
 203 struct correct: not_implemented<Tag>
 204 {};
 205
 206 template <typename Point>
 207 struct correct<Point, point_tag>
 208     : detail::correct::correct_nop<Point>
 209 {};
 210
 211 template <typename LineString>
 212 struct correct<LineString, linestring_tag>
 213     : detail::correct::correct_nop<LineString>
 214 {};
 215
 216 template <typename Segment>
 217 struct correct<Segment, segment_tag>
 218     : detail::correct::correct_nop<Segment>
 219 {};
 220
 221
 222 template <typename Box>
 223 struct correct<Box, box_tag>
 224     : detail::correct::correct_box<Box>
 225 {};
 226
 227 template <typename Ring>
 228 struct correct<Ring, ring_tag>
 229     : detail::correct::correct_ring
 230         <
 231             Ring,
 232             std::less
 233         >
 234 {};
 235
 236 template <typename Polygon>
 237 struct correct<Polygon, polygon_tag>
 238     : detail::correct::correct_polygon<Polygon>
 239 {};
 240
 241
 242 template <typename MultiPoint>
 243 struct correct<MultiPoint, multi_point_tag>
 244     : detail::correct::correct_nop<MultiPoint>
 245 {};
 246
 247
 248 template <typename MultiLineString>
 249 struct correct<MultiLineString, multi_linestring_tag>
 250     : detail::correct::correct_nop<MultiLineString>
 251 {};
 252
 253
 254 template <typename Geometry>
 255 struct correct<Geometry, multi_polygon_tag>
 256     : detail::multi_modify
 257         <
 258             Geometry,
 259             detail::correct::correct_polygon
 260                 <
 261                     typename boost::range_value<Geometry>::type
 262                 >
 263         >
 264 {};
 265
 266
 267 } // namespace dispatch
 268 #endif // DOXYGEN_NO_DISPATCH
 269
 270
 271 namespace resolve_variant {
 272
 273 template <typename Geometry>
 274 struct correct
 275 {
 276     template <typename Strategy>
 277     static inline void apply(Geometry& geometry, Strategy const& strategy)
 278     {
 279         concepts::check<Geometry const>();
 280         dispatch::correct<Geometry>::apply(geometry, strategy);
 281     }
 282 };
 283
 284 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 285 struct correct<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 286 {
 287     template <typename Strategy>
 288     struct visitor: boost::static_visitor<void>
 289     {
 290         Strategy const& m_strategy;
 291
 292         visitor(Strategy const& strategy): m_strategy(strategy) {}
 293
 294         template <typename Geometry>
 295         void operator()(Geometry& geometry) const
 296         {
 297             correct<Geometry>::apply(geometry, m_strategy);
 298         }
 299     };
 300
 301     template <typename Strategy>
 302     static inline void
 303     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry, Strategy const& strategy)
 304     {
 305         boost::apply_visitor(visitor<Strategy>(strategy), geometry);
 306     }
 307 };
 308
 309 } // namespace resolve_variant
 310
 311
 312 /*!
 313 \brief Corrects a geometry
 314 \details Corrects a geometry: all rings which are wrongly oriented with respect
 315     to their expected orientation are reversed. To all rings which do not have a
 316     closing point and are typed as they should have one, the first point is
 317     appended. Also boxes can be corrected.
 318 \ingroup correct
 319 \tparam Geometry \tparam_geometry
 320 \param geometry \param_geometry which will be corrected if necessary
 321
 322 \qbk{[include reference/algorithms/correct.qbk]}
 323 */
 324 template <typename Geometry>
 325 inline void correct(Geometry& geometry)
 326 {
 327     typedef typename point_type<Geometry>::type point_type;
 328
 329     typedef typename strategy::area::services::default_strategy
 330         <
 331             typename cs_tag<point_type>::type
 332         >::type strategy_type;
 333
 334     resolve_variant::correct<Geometry>::apply(geometry, strategy_type());
 335 }
 336
 337 /*!
 338 \brief Corrects a geometry
 339 \details Corrects a geometry: all rings which are wrongly oriented with respect
 340     to their expected orientation are reversed. To all rings which do not have a
 341     closing point and are typed as they should have one, the first point is
 342     appended. Also boxes can be corrected.
 343 \ingroup correct
 344 \tparam Geometry \tparam_geometry
 345 \tparam Strategy \tparam_strategy{Area}
 346 \param geometry \param_geometry which will be corrected if necessary
 347 \param strategy \param_strategy{area}
 348
 349 \qbk{distinguish,with strategy}
 350
 351 \qbk{[include reference/algorithms/correct.qbk]}
 352 */
 353 template <typename Geometry, typename Strategy>
 354 inline void correct(Geometry& geometry, Strategy const& strategy)
 355 {
 356     resolve_variant::correct<Geometry>::apply(geometry, strategy);
 357 }
 358
 359 #if defined(_MSC_VER)
 360 #pragma warning(pop)
 361 #endif
 362
 363 }} // namespace boost::geometry
 364
 365
 366 #endif // BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP