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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2017-2021.
   6 // Modifications copyright (c) 2017-2021 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP
  16
  17
  18 #include <boost/range/empty.hpp>
  19
  20 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  21 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
  22 #include <boost/geometry/algorithms/detail/visit.hpp>
  23 #include <boost/geometry/core/access.hpp>
  24 #include <boost/geometry/core/closure.hpp>
  25 #include <boost/geometry/core/cs.hpp>
  26 #include <boost/geometry/core/coordinate_dimension.hpp>
  27 #include <boost/geometry/core/exterior_ring.hpp>
  28 #include <boost/geometry/core/point_type.hpp>
  29 #include <boost/geometry/core/interior_rings.hpp>
  30 #include <boost/geometry/core/visit.hpp>
  31 #include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility
  32 #include <boost/geometry/geometries/concepts/check.hpp>
  33 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
  34 #include <boost/geometry/strategies/default_strategy.hpp>
  35 #include <boost/geometry/strategies/is_convex/cartesian.hpp>
  36 #include <boost/geometry/strategies/is_convex/geographic.hpp>
  37 #include <boost/geometry/strategies/is_convex/spherical.hpp>
  38 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
  39
  40
  41 namespace boost { namespace geometry
  42 {
  43
  44
  45 #ifndef DOXYGEN_NO_DETAIL
  46 namespace detail { namespace is_convex
  47 {
  48
  49 struct ring_is_convex
  50 {
  51     template <typename Ring, typename Strategies>
  52     static inline bool apply(Ring const& ring, Strategies const& strategies)
  53     {
  54         std::size_t n = boost::size(ring);
  55         if (n < detail::minimum_ring_size<Ring>::value)
  56         {
  57             // (Too) small rings are considered as non-concave, is convex
  58             return true;
  59         }
  60
  61         // Walk in clockwise direction, consider ring as closed
  62         // (though closure is not important in this algorithm - any dupped
  63         //  point is skipped)
  64         using view_type = detail::closed_clockwise_view<Ring const>;
  65         view_type const view(ring);
  66
  67         using it_type = geometry::ever_circling_range_iterator<view_type const>;
  68         it_type previous(view);
  69         it_type current(view);
  70         current++;
  71
  72         auto const equals_strategy = strategies.relate(dummy_point(), dummy_point());
  73
  74         std::size_t index = 1;
  75         while (equals::equals_point_point(*current, *previous, equals_strategy)
  76             && index < n)
  77         {
  78             current++;
  79             index++;
  80         }
  81
  82         if (index == n)
  83         {
  84             // All points are apparently equal
  85             return true;
  86         }
  87
  88         it_type next = current;
  89         next++;
  90         while (equals::equals_point_point(*current, *next, equals_strategy))
  91         {
  92             next++;
  93         }
  94
  95         auto const side_strategy = strategies.side();
  96
  97         // We have now three different points on the ring
  98         // Walk through all points, use a counter because of the ever-circling
  99         // iterator
 100         for (std::size_t i = 0; i < n; i++)
 101         {
 102             int const side = side_strategy.apply(*previous, *current, *next);
 103             if (side == 1)
 104             {
 105                 // Next is on the left side of clockwise ring:
 106                 // the piece is not convex
 107                 return false;
 108             }
 109
 110             previous = current;
 111             current = next;
 112
 113             // Advance next to next different point
 114             // (because there are non-equal points, this loop is not infinite)
 115             next++;
 116             while (equals::equals_point_point(*current, *next, equals_strategy))
 117             {
 118                 next++;
 119             }
 120         }
 121         return true;
 122     }
 123 };
 124
 125
 126 struct polygon_is_convex
 127 {
 128     template <typename Polygon, typename Strategies>
 129     static inline bool apply(Polygon const& polygon, Strategies const& strategies)
 130     {
 131         return boost::empty(interior_rings(polygon))
 132             && ring_is_convex::apply(exterior_ring(polygon), strategies);
 133     }
 134 };
 135
 136 struct multi_polygon_is_convex
 137 {
 138     template <typename MultiPolygon, typename Strategies>
 139     static inline bool apply(MultiPolygon const& multi_polygon, Strategies const& strategies)
 140     {
 141         auto const size = boost::size(multi_polygon);
 142         return size == 0 // For consistency with ring_is_convex
 143             || (size == 1 && polygon_is_convex::apply(range::front(multi_polygon), strategies));
 144     }
 145 };
 146
 147
 148 }} // namespace detail::is_convex
 149 #endif // DOXYGEN_NO_DETAIL
 150
 151
 152 #ifndef DOXYGEN_NO_DISPATCH
 153 namespace dispatch
 154 {
 155
 156 template
 157 <
 158     typename Geometry,
 159     typename Tag = typename tag<Geometry>::type
 160 >
 161 struct is_convex
 162 {
 163     template <typename Strategies>
 164     static inline bool apply(Geometry const&, Strategies const&)
 165     {
 166         // Convexity is not defined for PointLike and Linear geometries.
 167         // We could implement this because the following definitions would work:
 168         // - no line segment between two points on the interior or boundary ever goes outside.
 169         // - convex_hull of geometry is equal to the original geometry, this implies equal
 170         //   topological dimension.
 171         // For MultiPoint we'd have to check whether or not an arbitrary number of equal points
 172         //   is stored.
 173         // MultiPolygon we'd have to check for continuous chain of Linestrings which would require
 174         //   the use of relate(pt, seg) or distance(pt, pt) strategy.
 175         return false;
 176     }
 177 };
 178
 179 template <typename Box>
 180 struct is_convex<Box, box_tag>
 181 {
 182     template <typename Strategies>
 183     static inline bool apply(Box const& , Strategies const& )
 184     {
 185         // Any box is convex (TODO: consider spherical boxes)
 186         // TODO: in spherical and geographic the answer would be "false" most of the time.
 187         //   Assuming that:
 188         //   - it even makes sense to consider Box in spherical and geographic in this context
 189         //     because it's not a Polygon, e.g. it can degenerate to a Point.
 190         //   - line segments are defined by geodesics and box edges by parallels and meridians
 191         //   - we use this definition: A convex polygon is a simple polygon (not self-intersecting)
 192         //     in which no line segment between two points on the boundary ever goes outside the
 193         //     polygon.
 194         //   Then a geodesic segment would go into the exterior of a Box for all horizontal edges
 195         //   of a Box unless it was one of the poles (edge degenerated to a point) or equator and
 196         //   longitude difference was lesser than 360 (otherwise depending on the CS there would be
 197         //   no solution or there would be two possible solutions - segment going through one of
 198         //   the poles, at least in case of oblate spheroid, either way the answer would probably
 199         //   be "false").
 200         return true;
 201     }
 202 };
 203
 204 template <typename Ring>
 205 struct is_convex<Ring, ring_tag> : detail::is_convex::ring_is_convex
 206 {};
 207
 208 template <typename Polygon>
 209 struct is_convex<Polygon, polygon_tag> : detail::is_convex::polygon_is_convex
 210 {};
 211
 212 template <typename MultiPolygon>
 213 struct is_convex<MultiPolygon, multi_polygon_tag> : detail::is_convex::multi_polygon_is_convex
 214 {};
 215
 216
 217 } // namespace dispatch
 218 #endif // DOXYGEN_NO_DISPATCH
 219
 220 namespace resolve_strategy {
 221
 222 template
 223 <
 224     typename Strategies,
 225     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
 226 >
 227 struct is_convex
 228 {
 229     template <typename Geometry>
 230     static bool apply(Geometry const& geometry, Strategies const& strategies)
 231     {
 232         return dispatch::is_convex<Geometry>::apply(geometry, strategies);
 233     }
 234 };
 235
 236 template <typename Strategy>
 237 struct is_convex<Strategy, false>
 238 {
 239     template <typename Geometry>
 240     static bool apply(Geometry const& geometry, Strategy const& strategy)
 241     {
 242         using strategies::is_convex::services::strategy_converter;
 243         return dispatch::is_convex
 244             <
 245                 Geometry
 246             >::apply(geometry, strategy_converter<Strategy>::get(strategy));
 247     }
 248 };
 249
 250 template <>
 251 struct is_convex<default_strategy, false>
 252 {
 253     template <typename Geometry>
 254     static bool apply(Geometry const& geometry, default_strategy const& )
 255     {
 256         typedef typename strategies::is_convex::services::default_strategy
 257             <
 258                 Geometry
 259             >::type strategy_type;
 260
 261         return dispatch::is_convex<Geometry>::apply(geometry, strategy_type());
 262     }
 263 };
 264
 265 } // namespace resolve_strategy
 266
 267 namespace resolve_dynamic {
 268
 269 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
 270 struct is_convex
 271 {
 272     template <typename Strategy>
 273     static bool apply(Geometry const& geometry, Strategy const& strategy)
 274     {
 275         concepts::check<Geometry>();
 276         return resolve_strategy::is_convex<Strategy>::apply(geometry, strategy);
 277     }
 278 };
 279
 280 template <typename Geometry>
 281 struct is_convex<Geometry, dynamic_geometry_tag>
 282 {
 283     template <typename Strategy>
 284     static inline bool apply(Geometry const& geometry, Strategy const& strategy)
 285     {
 286         bool result = false;
 287         traits::visit<Geometry>::apply([&](auto const& g)
 288         {
 289             result = is_convex<util::remove_cref_t<decltype(g)>>::apply(g, strategy);
 290         }, geometry);
 291         return result;
 292     }
 293 };
 294
 295 // NOTE: This is a simple implementation checking if a GC contains single convex geometry.
 296 //   Technically a GC could store e.g. polygons touching with edges and together creating a convex
 297 //   region. To check this we'd require relate() strategy and the algorithm would be quite complex.
 298 template <typename Geometry>
 299 struct is_convex<Geometry, geometry_collection_tag>
 300 {
 301     template <typename Strategy>
 302     static inline bool apply(Geometry const& geometry, Strategy const& strategy)
 303     {
 304         bool result = false;
 305         bool is_first = true;
 306         detail::visit_breadth_first([&](auto const& g)
 307         {
 308             result = is_first
 309                   && is_convex<util::remove_cref_t<decltype(g)>>::apply(g, strategy);
 310             is_first = false;
 311             return result;
 312         }, geometry);
 313         return result;
 314     }
 315 };
 316
 317 } // namespace resolve_dynamic
 318
 319 // TODO: documentation / qbk
 320 template<typename Geometry>
 321 inline bool is_convex(Geometry const& geometry)
 322 {
 323     return resolve_dynamic::is_convex
 324             <
 325                 Geometry
 326             >::apply(geometry, geometry::default_strategy());
 327 }
 328
 329 // TODO: documentation / qbk
 330 template<typename Geometry, typename Strategy>
 331 inline bool is_convex(Geometry const& geometry, Strategy const& strategy)
 332 {
 333     return resolve_dynamic::is_convex<Geometry>::apply(geometry, strategy);
 334 }
 335
 336
 337 }} // namespace boost::geometry
 338
 339
 340 #endif // BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP