1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // This file was modified by Oracle on 2014, 2018.
6 // Modifications copyright (c) 2014, 2018 Oracle and/or its affiliates.
7
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9
10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
12
13 // Use, modification and distribution is subject to the Boost Software License,
14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
15 // http://www.boost.org/LICENSE_1_0.txt)
16
17 #ifndef BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP
18 #define BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP
19
20
21 #include <cstddef>
22 #include <algorithm>
23 #include <vector>
24
25 #include <boost/range/begin.hpp>
26 #include <boost/range/end.hpp>
27
28 #include <boost/geometry/algorithms/detail/for_each_range.hpp>
29 #include <boost/geometry/core/assert.hpp>
30 #include <boost/geometry/core/cs.hpp>
31 #include <boost/geometry/core/point_type.hpp>
32 #include <boost/geometry/policies/compare.hpp>
33 #include <boost/geometry/strategies/convex_hull.hpp>
34 #include <boost/geometry/strategies/side.hpp>
35 #include <boost/geometry/views/detail/range_type.hpp>
36
37
38 namespace boost { namespace geometry
39 {
40
41 namespace strategy { namespace convex_hull
42 {
43
44 #ifndef DOXYGEN_NO_DETAIL
45 namespace detail
46 {
47
48
49 template
50 <
51 typename InputRange,
52 typename RangeIterator,
53 typename StrategyLess,
54 typename StrategyGreater
55 >
56 struct get_extremes
57 {
58 typedef typename point_type<InputRange>::type point_type;
59
60 point_type left, right;
61
62 bool first;
63
64 StrategyLess less;
65 StrategyGreater greater;
66
get_extremesboost::geometry::strategy::convex_hull::detail::get_extremes67 inline get_extremes()
68 : first(true)
69 {}
70
applyboost::geometry::strategy::convex_hull::detail::get_extremes71 inline void apply(InputRange const& range)
72 {
73 if (boost::size(range) == 0)
74 {
75 return;
76 }
77
78 // First iterate through this range
79 // (this two-stage approach avoids many point copies,
80 // because iterators are kept in memory. Because iterators are
81 // not persistent (in MSVC) this approach is not applicable
82 // for more ranges together)
83
84 RangeIterator left_it = boost::begin(range);
85 RangeIterator right_it = boost::begin(range);
86
87 for (RangeIterator it = boost::begin(range) + 1;
88 it != boost::end(range);
89 ++it)
90 {
91 if (less(*it, *left_it))
92 {
93 left_it = it;
94 }
95
96 if (greater(*it, *right_it))
97 {
98 right_it = it;
99 }
100 }
101
102 // Then compare with earlier
103 if (first)
104 {
105 // First time, assign left/right
106 left = *left_it;
107 right = *right_it;
108 first = false;
109 }
110 else
111 {
112 // Next time, check if this range was left/right from
113 // the extremes already collected
114 if (less(*left_it, left))
115 {
116 left = *left_it;
117 }
118
119 if (greater(*right_it, right))
120 {
121 right = *right_it;
122 }
123 }
124 }
125 };
126
127
128 template
129 <
130 typename InputRange,
131 typename RangeIterator,
132 typename Container,
133 typename SideStrategy
134 >
135 struct assign_range
136 {
137 Container lower_points, upper_points;
138
139 typedef typename point_type<InputRange>::type point_type;
140
141 point_type const& most_left;
142 point_type const& most_right;
143
assign_rangeboost::geometry::strategy::convex_hull::detail::assign_range144 inline assign_range(point_type const& left, point_type const& right)
145 : most_left(left)
146 , most_right(right)
147 {}
148
applyboost::geometry::strategy::convex_hull::detail::assign_range149 inline void apply(InputRange const& range)
150 {
151 typedef SideStrategy side;
152
153 // Put points in one of the two output sequences
154 for (RangeIterator it = boost::begin(range);
155 it != boost::end(range);
156 ++it)
157 {
158 // check if it is lying most_left or most_right from the line
159
160 int dir = side::apply(most_left, most_right, *it);
161 switch(dir)
162 {
163 case 1 : // left side
164 upper_points.push_back(*it);
165 break;
166 case -1 : // right side
167 lower_points.push_back(*it);
168 break;
169
170 // 0: on line most_left-most_right,
171 // or most_left, or most_right,
172 // -> all never part of hull
173 }
174 }
175 }
176 };
177
178 template <typename Range>
sort(Range & range)179 static inline void sort(Range& range)
180 {
181 typedef typename boost::range_value<Range>::type point_type;
182 typedef geometry::less<point_type> comparator;
183
184 std::sort(boost::begin(range), boost::end(range), comparator());
185 }
186
187 } // namespace detail
188 #endif // DOXYGEN_NO_DETAIL
189
190
191 /*!
192 \brief Graham scan strategy to calculate convex hull
193 \ingroup strategies
194 */
195 template <typename InputGeometry, typename OutputPoint>
196 class graham_andrew
197 {
198 public :
199 typedef OutputPoint point_type;
200 typedef InputGeometry geometry_type;
201
202 private:
203
204 typedef typename cs_tag<point_type>::type cs_tag;
205
206 typedef typename std::vector<point_type> container_type;
207 typedef typename std::vector<point_type>::const_iterator iterator;
208 typedef typename std::vector<point_type>::const_reverse_iterator rev_iterator;
209
210
211 class partitions
212 {
213 friend class graham_andrew;
214
215 container_type m_lower_hull;
216 container_type m_upper_hull;
217 container_type m_copied_input;
218 };
219
220
221 public:
222 typedef partitions state_type;
223
224
apply(InputGeometry const & geometry,partitions & state) const225 inline void apply(InputGeometry const& geometry, partitions& state) const
226 {
227 // First pass.
228 // Get min/max (in most cases left / right) points
229 // This makes use of the geometry::less/greater predicates
230
231 // For the left boundary it is important that multiple points
232 // are sorted from bottom to top. Therefore the less predicate
233 // does not take the x-only template parameter (this fixes ticket #6019.
234 // For the right boundary it is not necessary (though also not harmful),
235 // because points are sorted from bottom to top in a later stage.
236 // For symmetry and to get often more balanced lower/upper halves
237 // we keep it.
238
239 typedef typename geometry::detail::range_type<InputGeometry>::type range_type;
240
241 typedef typename boost::range_iterator
242 <
243 range_type const
244 >::type range_iterator;
245
246 detail::get_extremes
247 <
248 range_type,
249 range_iterator,
250 geometry::less<point_type>,
251 geometry::greater<point_type>
252 > extremes;
253 geometry::detail::for_each_range(geometry, extremes);
254
255 // Bounding left/right points
256 // Second pass, now that extremes are found, assign all points
257 // in either lower, either upper
258 detail::assign_range
259 <
260 range_type,
261 range_iterator,
262 container_type,
263 typename strategy::side::services::default_strategy<cs_tag>::type
264 > assigner(extremes.left, extremes.right);
265
266 geometry::detail::for_each_range(geometry, assigner);
267
268
269 // Sort both collections, first on x(, then on y)
270 detail::sort(assigner.lower_points);
271 detail::sort(assigner.upper_points);
272
273 //std::cout << boost::size(assigner.lower_points) << std::endl;
274 //std::cout << boost::size(assigner.upper_points) << std::endl;
275
276 // And decide which point should be in the final hull
277 build_half_hull<-1>(assigner.lower_points, state.m_lower_hull,
278 extremes.left, extremes.right);
279 build_half_hull<1>(assigner.upper_points, state.m_upper_hull,
280 extremes.left, extremes.right);
281 }
282
283
284 template <typename OutputIterator>
result(partitions const & state,OutputIterator out,bool clockwise,bool closed) const285 inline void result(partitions const& state,
286 OutputIterator out,
287 bool clockwise,
288 bool closed) const
289 {
290 if (clockwise)
291 {
292 output_ranges(state.m_upper_hull, state.m_lower_hull, out, closed);
293 }
294 else
295 {
296 output_ranges(state.m_lower_hull, state.m_upper_hull, out, closed);
297 }
298 }
299
300
301 private:
302
303 template <int Factor>
build_half_hull(container_type const & input,container_type & output,point_type const & left,point_type const & right)304 static inline void build_half_hull(container_type const& input,
305 container_type& output,
306 point_type const& left, point_type const& right)
307 {
308 output.push_back(left);
309 for(iterator it = input.begin(); it != input.end(); ++it)
310 {
311 add_to_hull<Factor>(*it, output);
312 }
313 add_to_hull<Factor>(right, output);
314 }
315
316
317 template <int Factor>
add_to_hull(point_type const & p,container_type & output)318 static inline void add_to_hull(point_type const& p, container_type& output)
319 {
320 typedef typename strategy::side::services::default_strategy<cs_tag>::type side;
321
322 output.push_back(p);
323 std::size_t output_size = output.size();
324 while (output_size >= 3)
325 {
326 rev_iterator rit = output.rbegin();
327 point_type const last = *rit++;
328 point_type const& last2 = *rit++;
329
330 if (Factor * side::apply(*rit, last, last2) <= 0)
331 {
332 // Remove last two points from stack, and add last again
333 // This is much faster then erasing the one but last.
334 output.pop_back();
335 output.pop_back();
336 output.push_back(last);
337 output_size--;
338 }
339 else
340 {
341 return;
342 }
343 }
344 }
345
346
347 template <typename OutputIterator>
output_ranges(container_type const & first,container_type const & second,OutputIterator out,bool closed)348 static inline void output_ranges(container_type const& first, container_type const& second,
349 OutputIterator out, bool closed)
350 {
351 std::copy(boost::begin(first), boost::end(first), out);
352
353 BOOST_GEOMETRY_ASSERT(closed ? !boost::empty(second) : boost::size(second) > 1);
354 std::copy(++boost::rbegin(second), // skip the first Point
355 closed ? boost::rend(second) : --boost::rend(second), // skip the last Point if open
356 out);
357
358 typedef typename boost::range_size<container_type>::type size_type;
359 size_type const count = boost::size(first) + boost::size(second) - 1;
360 // count describes a closed case but comparison with min size of closed
361 // gives the result compatible also with open
362 // here core_detail::closure::minimum_ring_size<closed> could be used
363 if (count < 4)
364 {
365 // there should be only one missing
366 *out++ = *boost::begin(first);
367 }
368 }
369 };
370
371 }} // namespace strategy::convex_hull
372
373
374 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
375 template <typename InputGeometry, typename OutputPoint>
376 struct strategy_convex_hull<InputGeometry, OutputPoint, cartesian_tag>
377 {
378 typedef strategy::convex_hull::graham_andrew<InputGeometry, OutputPoint> type;
379 };
380 #endif
381
382 }} // namespace boost::geometry
383
384
385 #endif // BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP
386