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>
applyboost::geometry::detail::is_convex::ring_is_convex46     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>
applyboost::geometry::dispatch::is_convex138     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>
applyboost::geometry::resolve_variant::is_convex159     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 
applyboost::geometry::resolve_variant::is_convex165     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 
visitorboost::geometry::resolve_variant::is_convex::visitor184         visitor(Strategy const& strategy) : m_strategy(strategy) {}
185 
186         template <typename Geometry>
operator ()boost::geometry::resolve_variant::is_convex::visitor187         bool operator()(Geometry const& geometry) const
188         {
189             return is_convex<Geometry>::apply(geometry, m_strategy);
190         }
191     };
192 
193     template <typename Strategy>
applyboost::geometry::resolve_variant::is_convex194     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>
is_convex(Geometry const & 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>
is_convex(Geometry const & geometry,Strategy const & 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
225