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