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.
   6 // Modifications copyright (c) 2017 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/variant/apply_visitor.hpp>
  19 #include <boost/variant/static_visitor.hpp>
  20 #include <boost/variant/variant_fwd.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/equals/point_point.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/point_type.hpp>
  28 #include <boost/geometry/geometries/concepts/check.hpp>
  29 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
  30 #include <boost/geometry/strategies/default_strategy.hpp>
  31 #include <boost/geometry/strategies/side.hpp>
  32 #include <boost/geometry/views/detail/normalized_view.hpp>
  33
  34
  35 namespace boost { namespace geometry
  36 {
  37
  38
  39 #ifndef DOXYGEN_NO_DETAIL
  40 namespace detail { namespace is_convex
  41 {
  42
  43 struct ring_is_convex
  44 {
  45     template <typename Ring, typename SideStrategy>
  46     static inline bool apply(Ring const& ring, SideStrategy const& strategy)
  47     {
  48         std::size_t n = boost::size(ring);
  49         if (boost::size(ring) < core_detail::closure::minimum_ring_size
  50                                     <
  51                                         geometry::closure<Ring>::value
  52                                     >::value)
  53         {
  54             // (Too) small rings are considered as non-concave, is convex
  55             return true;
  56         }
  57
  58         // Walk in clockwise direction, consider ring as closed
  59         // (though closure is not important in this algorithm - any dupped
  60         //  point is skipped)
  61         typedef detail::normalized_view<Ring const> view_type;
  62         view_type view(ring);
  63
  64         typedef geometry::ever_circling_range_iterator<view_type const> it_type;
  65         it_type previous(view);
  66         it_type current(view);
  67         current++;
  68
  69         std::size_t index = 1;
  70         while (equals::equals_point_point(*current, *previous) && index < n)
  71         {
  72             current++;
  73             index++;
  74         }
  75
  76         if (index == n)
  77         {
  78             // All points are apparently equal
  79             return true;
  80         }
  81
  82         it_type next = current;
  83         next++;
  84         while (equals::equals_point_point(*current, *next))
  85         {
  86             next++;
  87         }
  88
  89         // We have now three different points on the ring
  90         // Walk through all points, use a counter because of the ever-circling
  91         // iterator
  92         for (std::size_t i = 0; i < n; i++)
  93         {
  94             int const side = strategy.apply(*previous, *current, *next);
  95             if (side == 1)
  96             {
  97                 // Next is on the left side of clockwise ring:
  98                 // the piece is not convex
  99                 return false;
 100             }
 101
 102             previous = current;
 103             current = next;
 104
 105             // Advance next to next different point
 106             // (because there are non-equal points, this loop is not infinite)
 107             next++;
 108             while (equals::equals_point_point(*current, *next))
 109             {
 110                 next++;
 111             }
 112         }
 113         return true;
 114     }
 115 };
 116
 117
 118 }} // namespace detail::is_convex
 119 #endif // DOXYGEN_NO_DETAIL
 120
 121
 122 #ifndef DOXYGEN_NO_DISPATCH
 123 namespace dispatch
 124 {
 125
 126 template
 127 <
 128     typename Geometry,
 129     typename Tag = typename tag<Geometry>::type
 130 >
 131 struct is_convex : not_implemented<Tag>
 132 {};
 133
 134 template <typename Box>
 135 struct is_convex<Box, box_tag>
 136 {
 137     template <typename Strategy>
 138     static inline bool apply(Box const& , Strategy const& )
 139     {
 140         // Any box is convex (TODO: consider spherical boxes)
 141         return true;
 142     }
 143 };
 144
 145 template <typename Box>
 146 struct is_convex<Box, ring_tag> : detail::is_convex::ring_is_convex
 147 {};
 148
 149
 150 } // namespace dispatch
 151 #endif // DOXYGEN_NO_DISPATCH
 152
 153 namespace resolve_variant {
 154
 155 template <typename Geometry>
 156 struct is_convex
 157 {
 158     template <typename Strategy>
 159     static bool apply(Geometry const& geometry, Strategy const& strategy)
 160     {
 161         concepts::check<Geometry>();
 162         return dispatch::is_convex<Geometry>::apply(geometry, strategy);
 163     }
 164
 165     static bool apply(Geometry const& geometry, geometry::default_strategy const&)
 166     {
 167         typedef typename strategy::side::services::default_strategy
 168             <
 169                 typename cs_tag<Geometry>::type
 170             >::type side_strategy;
 171
 172         return apply(geometry, side_strategy());
 173     }
 174 };
 175
 176 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 177 struct is_convex<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 178 {
 179     template <typename Strategy>
 180     struct visitor: boost::static_visitor<bool>
 181     {
 182         Strategy const& m_strategy;
 183
 184         visitor(Strategy const& strategy) : m_strategy(strategy) {}
 185
 186         template <typename Geometry>
 187         bool operator()(Geometry const& geometry) const
 188         {
 189             return is_convex<Geometry>::apply(geometry, m_strategy);
 190         }
 191     };
 192
 193     template <typename Strategy>
 194     static inline bool apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
 195                              Strategy const& strategy)
 196     {
 197         return boost::apply_visitor(visitor<Strategy>(strategy), geometry);
 198     }
 199 };
 200
 201 } // namespace resolve_variant
 202
 203 // TODO: documentation / qbk
 204 template<typename Geometry>
 205 inline bool is_convex(Geometry const& geometry)
 206 {
 207     return resolve_variant::is_convex
 208             <
 209                 Geometry
 210             >::apply(geometry, geometry::default_strategy());
 211 }
 212
 213 // TODO: documentation / qbk
 214 template<typename Geometry, typename Strategy>
 215 inline bool is_convex(Geometry const& geometry, Strategy const& strategy)
 216 {
 217     return resolve_variant::is_convex<Geometry>::apply(geometry, strategy);
 218 }
 219
 220
 221 }} // namespace boost::geometry
 222
 223
 224 #endif // BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP