]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2014 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. | |
6 | // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. | |
7 | ||
20effc67 TL |
8 | // This file was modified by Oracle on 2014-2020. |
9 | // Modifications copyright (c) 2014-2020, Oracle and/or its affiliates. | |
7c673cae FG |
10 | |
11 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
20effc67 | 12 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
7c673cae FG |
13 | |
14 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
15 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
16 | ||
17 | // Use, modification and distribution is subject to the Boost Software License, | |
18 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
19 | // http://www.boost.org/LICENSE_1_0.txt) | |
20 | ||
21 | #ifndef BOOST_GEOMETRY_ALGORITHMS_FOR_EACH_HPP | |
22 | #define BOOST_GEOMETRY_ALGORITHMS_FOR_EACH_HPP | |
23 | ||
24 | ||
25 | #include <algorithm> | |
26 | ||
20effc67 TL |
27 | #include <boost/range/begin.hpp> |
28 | #include <boost/range/end.hpp> | |
29 | #include <boost/range/reference.hpp> | |
30 | #include <boost/range/value_type.hpp> | |
7c673cae FG |
31 | |
32 | #include <boost/geometry/algorithms/detail/interior_iterator.hpp> | |
33 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
34 | #include <boost/geometry/core/closure.hpp> | |
35 | #include <boost/geometry/core/exterior_ring.hpp> | |
36 | #include <boost/geometry/core/interior_rings.hpp> | |
37 | #include <boost/geometry/core/point_type.hpp> | |
38 | #include <boost/geometry/core/tag_cast.hpp> | |
39 | #include <boost/geometry/core/tags.hpp> | |
40 | ||
41 | #include <boost/geometry/geometries/concepts/check.hpp> | |
42 | ||
43 | #include <boost/geometry/geometries/segment.hpp> | |
44 | ||
7c673cae | 45 | #include <boost/geometry/util/range.hpp> |
20effc67 TL |
46 | #include <boost/geometry/util/type_traits.hpp> |
47 | ||
48 | #include <boost/geometry/views/detail/indexed_point_view.hpp> | |
7c673cae FG |
49 | |
50 | ||
51 | namespace boost { namespace geometry | |
52 | { | |
53 | ||
54 | #ifndef DOXYGEN_NO_DETAIL | |
55 | namespace detail { namespace for_each | |
56 | { | |
57 | ||
58 | ||
20effc67 | 59 | struct fe_point_point |
7c673cae FG |
60 | { |
61 | template <typename Point, typename Functor> | |
20effc67 | 62 | static inline bool apply(Point& point, Functor&& f) |
7c673cae | 63 | { |
20effc67 | 64 | return f(point); |
7c673cae FG |
65 | } |
66 | }; | |
67 | ||
68 | ||
20effc67 | 69 | struct fe_segment_point |
7c673cae FG |
70 | { |
71 | template <typename Point, typename Functor> | |
20effc67 | 72 | static inline bool apply(Point& , Functor&& ) |
7c673cae FG |
73 | { |
74 | // TODO: if non-const, we should extract the points from the segment | |
75 | // and call the functor on those two points | |
20effc67 TL |
76 | |
77 | //model::referring_segment<Point> s(point, point); | |
78 | //return f(s); | |
79 | ||
80 | return true; | |
7c673cae FG |
81 | } |
82 | }; | |
83 | ||
84 | ||
20effc67 | 85 | struct fe_point_segment |
7c673cae | 86 | { |
20effc67 TL |
87 | template <typename Segment, typename Functor> |
88 | static inline bool apply(Segment& s, Functor&& f) | |
7c673cae | 89 | { |
20effc67 TL |
90 | // Or should we guarantee that the type of points is |
91 | // point_type<Segment>::type ? | |
92 | geometry::detail::indexed_point_view<Segment, 0> p0(s); | |
93 | geometry::detail::indexed_point_view<Segment, 1> p1(s); | |
94 | return f(p0) && f(p1); | |
95 | } | |
96 | }; | |
97 | ||
98 | struct fe_segment_segment | |
99 | { | |
100 | template <typename Segment, typename Functor> | |
101 | static inline bool apply(Segment& s, Functor&& f) | |
102 | { | |
103 | // Or should we guarantee that the type of segment is | |
104 | // referring_segment<...> ? | |
105 | return f(s); | |
106 | } | |
107 | }; | |
7c673cae | 108 | |
7c673cae | 109 | |
20effc67 TL |
110 | template <typename Range> |
111 | struct fe_range_value | |
112 | { | |
113 | typedef util::transcribe_const_t | |
114 | < | |
115 | Range, | |
116 | typename boost::range_value<Range>::type | |
117 | > type; | |
118 | }; | |
119 | ||
120 | template <typename Range> | |
121 | struct fe_point_type | |
122 | { | |
123 | typedef util::transcribe_const_t | |
124 | < | |
125 | Range, | |
126 | typename point_type<Range>::type | |
127 | > type; | |
128 | }; | |
129 | ||
130 | ||
131 | template <typename Range> | |
132 | struct fe_point_type_is_referencable | |
133 | { | |
134 | static const bool value = | |
135 | std::is_const<Range>::value | |
136 | || std::is_same | |
137 | < | |
138 | typename boost::range_reference<Range>::type, | |
139 | typename fe_point_type<Range>::type& | |
140 | >::value; | |
141 | }; | |
142 | ||
143 | ||
144 | template | |
145 | < | |
146 | typename Range, | |
147 | bool UseReferences = fe_point_type_is_referencable<Range>::value | |
148 | > | |
149 | struct fe_point_call_f | |
150 | { | |
151 | template <typename Iterator, typename Functor> | |
152 | static inline bool apply(Iterator it, Functor&& f) | |
153 | { | |
154 | // Implementation for real references (both const and mutable) | |
155 | // and const proxy references. | |
156 | typedef typename fe_point_type<Range>::type point_type; | |
157 | point_type& p = *it; | |
158 | return f(p); | |
159 | } | |
160 | }; | |
161 | ||
162 | template <typename Range> | |
163 | struct fe_point_call_f<Range, false> | |
164 | { | |
165 | template <typename Iterator, typename Functor> | |
166 | static inline bool apply(Iterator it, Functor&& f) | |
167 | { | |
168 | // Implementation for proxy mutable references. | |
169 | // Temporary point has to be created and assigned afterwards. | |
170 | typedef typename fe_point_type<Range>::type point_type; | |
171 | point_type p = *it; | |
172 | bool result = f(p); | |
173 | *it = p; | |
174 | return result; | |
175 | } | |
176 | }; | |
177 | ||
178 | ||
179 | struct fe_point_range | |
180 | { | |
181 | template <typename Range, typename Functor> | |
182 | static inline bool apply(Range& range, Functor&& f) | |
183 | { | |
184 | auto const end = boost::end(range); | |
185 | for (auto it = boost::begin(range); it != end; ++it) | |
7c673cae | 186 | { |
20effc67 TL |
187 | if (! fe_point_call_f<Range>::apply(it, f)) |
188 | { | |
189 | return false; | |
190 | } | |
7c673cae | 191 | } |
20effc67 TL |
192 | |
193 | return true; | |
194 | } | |
195 | }; | |
196 | ||
197 | ||
198 | template | |
199 | < | |
200 | typename Range, | |
201 | bool UseReferences = fe_point_type_is_referencable<Range>::value | |
202 | > | |
203 | struct fe_segment_call_f | |
204 | { | |
205 | template <typename Iterator, typename Functor> | |
206 | static inline bool apply(Iterator it0, Iterator it1, Functor&& f) | |
207 | { | |
208 | // Implementation for real references (both const and mutable) | |
209 | // and const proxy references. | |
210 | // If const proxy references are returned by iterators | |
211 | // then const real references here prevents temporary | |
212 | // objects from being destroyed. | |
213 | typedef typename fe_point_type<Range>::type point_type; | |
214 | point_type& p0 = *it0; | |
215 | point_type& p1 = *it1; | |
216 | model::referring_segment<point_type> s(p0, p1); | |
217 | return f(s); | |
218 | } | |
219 | }; | |
220 | ||
221 | template <typename Range> | |
222 | struct fe_segment_call_f<Range, false> | |
223 | { | |
224 | template <typename Iterator, typename Functor> | |
225 | static inline bool apply(Iterator it0, Iterator it1, Functor&& f) | |
226 | { | |
227 | // Mutable proxy references returned by iterators. | |
228 | // Temporary points have to be created and assigned afterwards. | |
229 | typedef typename fe_point_type<Range>::type point_type; | |
230 | point_type p0 = *it0; | |
231 | point_type p1 = *it1; | |
232 | model::referring_segment<point_type> s(p0, p1); | |
233 | bool result = f(s); | |
234 | *it0 = p0; | |
235 | *it1 = p1; | |
236 | return result; | |
7c673cae FG |
237 | } |
238 | }; | |
239 | ||
240 | ||
241 | template <closure_selector Closure> | |
20effc67 | 242 | struct fe_segment_range_with_closure |
7c673cae FG |
243 | { |
244 | template <typename Range, typename Functor> | |
20effc67 | 245 | static inline bool apply(Range& range, Functor&& f) |
7c673cae | 246 | { |
20effc67 TL |
247 | auto it = boost::begin(range); |
248 | auto const end = boost::end(range); | |
249 | if (it == end) | |
250 | { | |
251 | return true; | |
252 | } | |
7c673cae | 253 | |
20effc67 TL |
254 | auto previous = it++; |
255 | if (it == end) | |
92f5a8d4 | 256 | { |
20effc67 | 257 | return fe_segment_call_f<Range>::apply(previous, previous, f); |
92f5a8d4 TL |
258 | } |
259 | ||
20effc67 | 260 | while (it != end) |
7c673cae | 261 | { |
20effc67 TL |
262 | if (! fe_segment_call_f<Range>::apply(previous, it, f)) |
263 | { | |
264 | return false; | |
265 | } | |
7c673cae FG |
266 | previous = it++; |
267 | } | |
20effc67 TL |
268 | |
269 | return true; | |
7c673cae FG |
270 | } |
271 | }; | |
272 | ||
273 | ||
274 | template <> | |
20effc67 | 275 | struct fe_segment_range_with_closure<open> |
7c673cae FG |
276 | { |
277 | template <typename Range, typename Functor> | |
20effc67 TL |
278 | static inline bool apply(Range& range, Functor&& f) |
279 | { | |
280 | fe_segment_range_with_closure<closed>::apply(range, f); | |
7c673cae | 281 | |
20effc67 TL |
282 | auto const begin = boost::begin(range); |
283 | auto end = boost::end(range); | |
284 | if (begin == end) | |
285 | { | |
286 | return true; | |
287 | } | |
288 | ||
289 | --end; | |
290 | ||
291 | if (begin == end) | |
292 | { | |
293 | // single point ranges already handled in closed case above | |
294 | return true; | |
295 | } | |
7c673cae | 296 | |
20effc67 | 297 | return fe_segment_call_f<Range>::apply(end, begin, f); |
7c673cae FG |
298 | } |
299 | }; | |
300 | ||
301 | ||
20effc67 | 302 | struct fe_segment_range |
7c673cae FG |
303 | { |
304 | template <typename Range, typename Functor> | |
20effc67 | 305 | static inline bool apply(Range& range, Functor&& f) |
7c673cae | 306 | { |
20effc67 | 307 | return fe_segment_range_with_closure |
7c673cae FG |
308 | < |
309 | closure<Range>::value | |
310 | >::apply(range, f); | |
311 | } | |
312 | }; | |
313 | ||
314 | ||
20effc67 TL |
315 | template <typename RangePolicy> |
316 | struct for_each_polygon | |
7c673cae FG |
317 | { |
318 | template <typename Polygon, typename Functor> | |
20effc67 | 319 | static inline bool apply(Polygon& poly, Functor&& f) |
7c673cae | 320 | { |
20effc67 | 321 | if (! RangePolicy::apply(exterior_ring(poly), f)) |
7c673cae | 322 | { |
20effc67 | 323 | return false; |
7c673cae | 324 | } |
7c673cae FG |
325 | |
326 | typename interior_return_type<Polygon>::type | |
327 | rings = interior_rings(poly); | |
328 | ||
20effc67 TL |
329 | auto const end = boost::end(rings); |
330 | for (auto it = boost::begin(rings); it != end; ++it) | |
7c673cae | 331 | { |
20effc67 TL |
332 | // NOTE: Currently lvalue iterator required |
333 | if (! RangePolicy::apply(*it, f)) | |
334 | { | |
335 | return false; | |
336 | } | |
7c673cae | 337 | } |
20effc67 TL |
338 | |
339 | return true; | |
7c673cae FG |
340 | } |
341 | ||
342 | }; | |
343 | ||
344 | // Implementation of multi, for both point and segment, | |
345 | // just calling the single version. | |
20effc67 | 346 | template <typename SinglePolicy> |
7c673cae FG |
347 | struct for_each_multi |
348 | { | |
349 | template <typename MultiGeometry, typename Functor> | |
20effc67 | 350 | static inline bool apply(MultiGeometry& multi, Functor&& f) |
7c673cae | 351 | { |
20effc67 TL |
352 | auto const end = boost::end(multi); |
353 | for (auto it = boost::begin(multi); it != end; ++it) | |
7c673cae | 354 | { |
20effc67 TL |
355 | // NOTE: Currently lvalue iterator required |
356 | if (! SinglePolicy::apply(*it, f)) | |
357 | { | |
358 | return false; | |
359 | } | |
7c673cae | 360 | } |
20effc67 TL |
361 | |
362 | return true; | |
7c673cae FG |
363 | } |
364 | }; | |
365 | ||
366 | }} // namespace detail::for_each | |
367 | #endif // DOXYGEN_NO_DETAIL | |
368 | ||
369 | ||
370 | #ifndef DOXYGEN_NO_DISPATCH | |
371 | namespace dispatch | |
372 | { | |
373 | ||
374 | template | |
375 | < | |
376 | typename Geometry, | |
377 | typename Tag = typename tag_cast<typename tag<Geometry>::type, multi_tag>::type | |
378 | > | |
379 | struct for_each_point: not_implemented<Tag> | |
380 | {}; | |
381 | ||
382 | ||
383 | template <typename Point> | |
384 | struct for_each_point<Point, point_tag> | |
20effc67 TL |
385 | : detail::for_each::fe_point_point |
386 | {}; | |
387 | ||
388 | ||
389 | template <typename Segment> | |
390 | struct for_each_point<Segment, segment_tag> | |
391 | : detail::for_each::fe_point_segment | |
7c673cae FG |
392 | {}; |
393 | ||
394 | ||
395 | template <typename Linestring> | |
396 | struct for_each_point<Linestring, linestring_tag> | |
20effc67 | 397 | : detail::for_each::fe_point_range |
7c673cae FG |
398 | {}; |
399 | ||
400 | ||
401 | template <typename Ring> | |
402 | struct for_each_point<Ring, ring_tag> | |
20effc67 | 403 | : detail::for_each::fe_point_range |
7c673cae FG |
404 | {}; |
405 | ||
406 | ||
407 | template <typename Polygon> | |
408 | struct for_each_point<Polygon, polygon_tag> | |
20effc67 TL |
409 | : detail::for_each::for_each_polygon |
410 | < | |
411 | detail::for_each::fe_point_range | |
412 | > | |
413 | {}; | |
414 | ||
415 | ||
416 | template <typename MultiGeometry> | |
417 | struct for_each_point<MultiGeometry, multi_tag> | |
418 | : detail::for_each::for_each_multi | |
419 | < | |
420 | // Specify the dispatch of the single-version as policy | |
421 | for_each_point | |
422 | < | |
423 | typename detail::for_each::fe_range_value | |
424 | < | |
425 | MultiGeometry | |
426 | >::type | |
427 | > | |
428 | > | |
7c673cae FG |
429 | {}; |
430 | ||
431 | ||
432 | template | |
433 | < | |
434 | typename Geometry, | |
20effc67 | 435 | typename Tag = typename tag<Geometry>::type |
7c673cae FG |
436 | > |
437 | struct for_each_segment: not_implemented<Tag> | |
438 | {}; | |
439 | ||
440 | template <typename Point> | |
441 | struct for_each_segment<Point, point_tag> | |
20effc67 TL |
442 | : detail::for_each::fe_segment_point // empty |
443 | {}; | |
444 | ||
445 | ||
446 | template <typename Segment> | |
447 | struct for_each_segment<Segment, segment_tag> | |
448 | : detail::for_each::fe_segment_segment | |
7c673cae FG |
449 | {}; |
450 | ||
451 | ||
452 | template <typename Linestring> | |
453 | struct for_each_segment<Linestring, linestring_tag> | |
20effc67 | 454 | : detail::for_each::fe_segment_range |
7c673cae FG |
455 | {}; |
456 | ||
457 | ||
458 | template <typename Ring> | |
459 | struct for_each_segment<Ring, ring_tag> | |
20effc67 | 460 | : detail::for_each::fe_segment_range |
7c673cae FG |
461 | {}; |
462 | ||
463 | ||
464 | template <typename Polygon> | |
465 | struct for_each_segment<Polygon, polygon_tag> | |
20effc67 TL |
466 | : detail::for_each::for_each_polygon |
467 | < | |
468 | detail::for_each::fe_segment_range | |
469 | > | |
7c673cae FG |
470 | {}; |
471 | ||
472 | ||
20effc67 TL |
473 | template <typename MultiPoint> |
474 | struct for_each_segment<MultiPoint, multi_point_tag> | |
475 | : detail::for_each::fe_segment_point // empty | |
476 | {}; | |
477 | ||
478 | ||
479 | template <typename MultiLinestring> | |
480 | struct for_each_segment<MultiLinestring, multi_linestring_tag> | |
7c673cae FG |
481 | : detail::for_each::for_each_multi |
482 | < | |
20effc67 | 483 | detail::for_each::fe_segment_range |
7c673cae FG |
484 | > |
485 | {}; | |
486 | ||
20effc67 TL |
487 | template <typename MultiPolygon> |
488 | struct for_each_segment<MultiPolygon, multi_polygon_tag> | |
7c673cae FG |
489 | : detail::for_each::for_each_multi |
490 | < | |
20effc67 | 491 | detail::for_each::for_each_polygon |
7c673cae | 492 | < |
20effc67 | 493 | detail::for_each::fe_segment_range |
7c673cae FG |
494 | > |
495 | > | |
496 | {}; | |
497 | ||
498 | ||
499 | } // namespace dispatch | |
500 | #endif // DOXYGEN_NO_DISPATCH | |
501 | ||
502 | ||
20effc67 TL |
503 | template<typename Geometry, typename UnaryPredicate> |
504 | inline bool all_points_of(Geometry& geometry, UnaryPredicate p) | |
505 | { | |
506 | concepts::check<Geometry>(); | |
507 | ||
508 | return dispatch::for_each_point<Geometry>::apply(geometry, p); | |
509 | } | |
510 | ||
511 | ||
512 | template<typename Geometry, typename UnaryPredicate> | |
513 | inline bool all_segments_of(Geometry const& geometry, UnaryPredicate p) | |
514 | { | |
515 | concepts::check<Geometry const>(); | |
516 | ||
517 | return dispatch::for_each_segment<Geometry const>::apply(geometry, p); | |
518 | } | |
519 | ||
520 | ||
521 | template<typename Geometry, typename UnaryPredicate> | |
522 | inline bool any_point_of(Geometry& geometry, UnaryPredicate p) | |
523 | { | |
524 | concepts::check<Geometry>(); | |
525 | ||
526 | return ! dispatch::for_each_point<Geometry>::apply(geometry, [&](auto&& pt) | |
527 | { | |
528 | return ! p(pt); | |
529 | }); | |
530 | } | |
531 | ||
532 | ||
533 | template<typename Geometry, typename UnaryPredicate> | |
534 | inline bool any_segment_of(Geometry const& geometry, UnaryPredicate p) | |
535 | { | |
536 | concepts::check<Geometry const>(); | |
537 | ||
538 | return ! dispatch::for_each_segment<Geometry const>::apply(geometry, [&](auto&& s) | |
539 | { | |
540 | return ! p(s); | |
541 | }); | |
542 | } | |
543 | ||
544 | template<typename Geometry, typename UnaryPredicate> | |
545 | inline bool none_point_of(Geometry& geometry, UnaryPredicate p) | |
546 | { | |
547 | concepts::check<Geometry>(); | |
548 | ||
549 | return dispatch::for_each_point<Geometry>::apply(geometry, [&](auto&& pt) | |
550 | { | |
551 | return ! p(pt); | |
552 | }); | |
553 | } | |
554 | ||
555 | ||
556 | template<typename Geometry, typename UnaryPredicate> | |
557 | inline bool none_segment_of(Geometry const& geometry, UnaryPredicate p) | |
558 | { | |
559 | concepts::check<Geometry const>(); | |
560 | ||
561 | return dispatch::for_each_segment<Geometry const>::apply(geometry, [&](auto&& s) | |
562 | { | |
563 | return ! p(s); | |
564 | }); | |
565 | } | |
566 | ||
567 | ||
7c673cae FG |
568 | /*! |
569 | \brief \brf_for_each{point} | |
570 | \details \det_for_each{point} | |
571 | \ingroup for_each | |
572 | \param geometry \param_geometry | |
573 | \param f \par_for_each_f{point} | |
574 | \tparam Geometry \tparam_geometry | |
575 | \tparam Functor \tparam_functor | |
576 | ||
577 | \qbk{[include reference/algorithms/for_each_point.qbk]} | |
578 | \qbk{[heading Example]} | |
579 | \qbk{[for_each_point] [for_each_point_output]} | |
580 | \qbk{[for_each_point_const] [for_each_point_const_output]} | |
581 | */ | |
582 | template<typename Geometry, typename Functor> | |
583 | inline Functor for_each_point(Geometry& geometry, Functor f) | |
584 | { | |
585 | concepts::check<Geometry>(); | |
586 | ||
20effc67 TL |
587 | dispatch::for_each_point<Geometry>::apply(geometry, [&](auto&& pt) |
588 | { | |
589 | f(pt); | |
590 | // TODO: Implement separate function? | |
591 | return true; | |
592 | }); | |
7c673cae FG |
593 | return f; |
594 | } | |
595 | ||
596 | ||
597 | /*! | |
598 | \brief \brf_for_each{segment} | |
599 | \details \det_for_each{segment} | |
600 | \ingroup for_each | |
601 | \param geometry \param_geometry | |
602 | \param f \par_for_each_f{segment} | |
603 | \tparam Geometry \tparam_geometry | |
604 | \tparam Functor \tparam_functor | |
605 | ||
606 | \qbk{[include reference/algorithms/for_each_segment.qbk]} | |
607 | \qbk{[heading Example]} | |
608 | \qbk{[for_each_segment_const] [for_each_segment_const_output]} | |
609 | */ | |
610 | template<typename Geometry, typename Functor> | |
611 | inline Functor for_each_segment(Geometry& geometry, Functor f) | |
612 | { | |
613 | concepts::check<Geometry>(); | |
614 | ||
20effc67 TL |
615 | dispatch::for_each_segment<Geometry>::apply(geometry, [&](auto&& s) |
616 | { | |
617 | f(s); | |
618 | // TODO: Implement separate function? | |
619 | return true; | |
620 | }); | |
7c673cae FG |
621 | return f; |
622 | } | |
623 | ||
624 | ||
625 | }} // namespace boost::geometry | |
626 | ||
627 | ||
628 | #endif // BOOST_GEOMETRY_ALGORITHMS_FOR_EACH_HPP |