ceph/src/boost/libs/geometry/include/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 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP
  11
  12
  13 #include <boost/geometry/core/access.hpp>
  14 #include <boost/geometry/core/closure.hpp>
  15 #include <boost/geometry/core/cs.hpp>
  16 #include <boost/geometry/core/coordinate_dimension.hpp>
  17 #include <boost/geometry/core/point_type.hpp>
  18 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  19 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
  20 #include <boost/geometry/strategies/side.hpp>
  21 #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp>
  22 #include <boost/geometry/views/detail/normalized_view.hpp>
  23
  24 namespace boost { namespace geometry
  25 {
  26
  27
  28 #ifndef DOXYGEN_NO_DETAIL
  29 namespace detail { namespace is_convex
  30 {
  31
  32 struct ring_is_convex
  33 {
  34     template <typename Ring>
  35     static inline bool apply(Ring const& ring)
  36     {
  37         typedef typename geometry::point_type<Ring>::type point_type;
  38         typedef typename strategy::side::services::default_strategy
  39         <
  40             typename cs_tag<point_type>::type
  41         >::type side_strategy_type;
  42
  43         std::size_t n = boost::size(ring);
  44         if (boost::size(ring) < core_detail::closure::minimum_ring_size
  45                                     <
  46                                         geometry::closure<Ring>::value
  47                                     >::value)
  48         {
  49             // (Too) small rings are considered as non-concave, is convex
  50             return true;
  51         }
  52
  53         // Walk in clockwise direction, consider ring as closed
  54         // (though closure is not important in this algorithm - any dupped
  55         //  point is skipped)
  56         typedef detail::normalized_view<Ring const> view_type;
  57         view_type view(ring);
  58
  59         typedef geometry::ever_circling_range_iterator<view_type const> it_type;
  60         it_type previous(view);
  61         it_type current(view);
  62         current++;
  63
  64         std::size_t index = 1;
  65         while (equals::equals_point_point(*current, *previous) && index < n)
  66         {
  67             current++;
  68             index++;
  69         }
  70
  71         if (index == n)
  72         {
  73             // All points are apparently equal
  74             return true;
  75         }
  76
  77         it_type next = current;
  78         next++;
  79         while (equals::equals_point_point(*current, *next))
  80         {
  81             next++;
  82         }
  83
  84         // We have now three different points on the ring
  85         // Walk through all points, use a counter because of the ever-circling
  86         // iterator
  87         for (std::size_t i = 0; i < n; i++)
  88         {
  89             int const side = side_strategy_type::apply(*previous, *current, *next);
  90             if (side == 1)
  91             {
  92                 // Next is on the left side of clockwise ring:
  93                 // the piece is not convex
  94                 return false;
  95             }
  96
  97             previous = current;
  98             current = next;
  99
 100             // Advance next to next different point
 101             // (because there are non-equal points, this loop is not infinite)
 102             next++;
 103             while (equals::equals_point_point(*current, *next))
 104             {
 105                 next++;
 106             }
 107         }
 108         return true;
 109     }
 110 };
 111
 112
 113 }} // namespace detail::is_convex
 114 #endif // DOXYGEN_NO_DETAIL
 115
 116
 117 #ifndef DOXYGEN_NO_DISPATCH
 118 namespace dispatch
 119 {
 120
 121 template
 122 <
 123     typename Geometry,
 124     typename Tag = typename tag<Geometry>::type
 125 >
 126 struct is_convex : not_implemented<Tag>
 127 {};
 128
 129 template <typename Box>
 130 struct is_convex<Box, box_tag>
 131 {
 132     static inline bool apply(Box const& )
 133     {
 134         // Any box is convex (TODO: consider spherical boxes)
 135         return true;
 136     }
 137 };
 138
 139 template <typename Box>
 140 struct is_convex<Box, ring_tag> : detail::is_convex::ring_is_convex
 141 {};
 142
 143
 144 } // namespace dispatch
 145 #endif // DOXYGEN_NO_DISPATCH
 146
 147 // TODO: variants
 148
 149 // TODO: documentation / qbk
 150 template<typename Geometry>
 151 inline bool is_convex(Geometry const& geometry)
 152 {
 153     return dispatch::is_convex<Geometry>::apply(geometry);
 154 }
 155
 156
 157 }} // namespace boost::geometry
 158
 159
 160 #endif // BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP