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