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