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, 2018. 6 // Modifications copyright (c) 2017-2018 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> applyboost::geometry::detail::is_convex::ring_is_convex46 static inline bool apply(Ring const& ring, SideStrategy const& strategy) 47 { 48 typename SideStrategy::equals_point_point_strategy_type 49 eq_pp_strategy = strategy.get_equals_point_point_strategy(); 50 51 std::size_t n = boost::size(ring); 52 if (boost::size(ring) < core_detail::closure::minimum_ring_size 53 < 54 geometry::closure<Ring>::value 55 >::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 typedef detail::normalized_view<Ring const> view_type; 65 view_type view(ring); 66 67 typedef geometry::ever_circling_range_iterator<view_type const> it_type; 68 it_type previous(view); 69 it_type current(view); 70 current++; 71 72 std::size_t index = 1; 73 while (equals::equals_point_point(*current, *previous, eq_pp_strategy) 74 && index < n) 75 { 76 current++; 77 index++; 78 } 79 80 if (index == n) 81 { 82 // All points are apparently equal 83 return true; 84 } 85 86 it_type next = current; 87 next++; 88 while (equals::equals_point_point(*current, *next, eq_pp_strategy)) 89 { 90 next++; 91 } 92 93 // We have now three different points on the ring 94 // Walk through all points, use a counter because of the ever-circling 95 // iterator 96 for (std::size_t i = 0; i < n; i++) 97 { 98 int const side = strategy.apply(*previous, *current, *next); 99 if (side == 1) 100 { 101 // Next is on the left side of clockwise ring: 102 // the piece is not convex 103 return false; 104 } 105 106 previous = current; 107 current = next; 108 109 // Advance next to next different point 110 // (because there are non-equal points, this loop is not infinite) 111 next++; 112 while (equals::equals_point_point(*current, *next, eq_pp_strategy)) 113 { 114 next++; 115 } 116 } 117 return true; 118 } 119 }; 120 121 122 }} // namespace detail::is_convex 123 #endif // DOXYGEN_NO_DETAIL 124 125 126 #ifndef DOXYGEN_NO_DISPATCH 127 namespace dispatch 128 { 129 130 template 131 < 132 typename Geometry, 133 typename Tag = typename tag<Geometry>::type 134 > 135 struct is_convex : not_implemented<Tag> 136 {}; 137 138 template <typename Box> 139 struct is_convex<Box, box_tag> 140 { 141 template <typename Strategy> applyboost::geometry::dispatch::is_convex142 static inline bool apply(Box const& , Strategy const& ) 143 { 144 // Any box is convex (TODO: consider spherical boxes) 145 return true; 146 } 147 }; 148 149 template <typename Box> 150 struct is_convex<Box, ring_tag> : detail::is_convex::ring_is_convex 151 {}; 152 153 154 } // namespace dispatch 155 #endif // DOXYGEN_NO_DISPATCH 156 157 namespace resolve_variant { 158 159 template <typename Geometry> 160 struct is_convex 161 { 162 template <typename Strategy> applyboost::geometry::resolve_variant::is_convex163 static bool apply(Geometry const& geometry, Strategy const& strategy) 164 { 165 concepts::check<Geometry>(); 166 return dispatch::is_convex<Geometry>::apply(geometry, strategy); 167 } 168 applyboost::geometry::resolve_variant::is_convex169 static bool apply(Geometry const& geometry, geometry::default_strategy const&) 170 { 171 typedef typename strategy::side::services::default_strategy 172 < 173 typename cs_tag<Geometry>::type 174 >::type side_strategy; 175 176 return apply(geometry, side_strategy()); 177 } 178 }; 179 180 template <BOOST_VARIANT_ENUM_PARAMS(typename T)> 181 struct is_convex<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > 182 { 183 template <typename Strategy> 184 struct visitor: boost::static_visitor<bool> 185 { 186 Strategy const& m_strategy; 187 visitorboost::geometry::resolve_variant::is_convex::visitor188 visitor(Strategy const& strategy) : m_strategy(strategy) {} 189 190 template <typename Geometry> operator ()boost::geometry::resolve_variant::is_convex::visitor191 bool operator()(Geometry const& geometry) const 192 { 193 return is_convex<Geometry>::apply(geometry, m_strategy); 194 } 195 }; 196 197 template <typename Strategy> applyboost::geometry::resolve_variant::is_convex198 static inline bool apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, 199 Strategy const& strategy) 200 { 201 return boost::apply_visitor(visitor<Strategy>(strategy), geometry); 202 } 203 }; 204 205 } // namespace resolve_variant 206 207 // TODO: documentation / qbk 208 template<typename Geometry> is_convex(Geometry const & geometry)209 inline bool is_convex(Geometry const& geometry) 210 { 211 return resolve_variant::is_convex 212 < 213 Geometry 214 >::apply(geometry, geometry::default_strategy()); 215 } 216 217 // TODO: documentation / qbk 218 template<typename Geometry, typename Strategy> is_convex(Geometry const & geometry,Strategy const & strategy)219 inline bool is_convex(Geometry const& geometry, Strategy const& strategy) 220 { 221 return resolve_variant::is_convex<Geometry>::apply(geometry, strategy); 222 } 223 224 225 }} // namespace boost::geometry 226 227 228 #endif // BOOST_GEOMETRY_ALGORITHMS_IS_CONVEX_HPP 229