]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. | |
6 | // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland. | |
7 | ||
20effc67 TL |
8 | // This file was modified by Oracle on 2013-2020. |
9 | // Modifications copyright (c) 2013-2020 Oracle and/or its affiliates. | |
7c673cae FG |
10 | |
11 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
12 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
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_DETAIL_SECTIONS_SECTIONALIZE_HPP | |
22 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP | |
23 | ||
24 | #include <cstddef> | |
20effc67 | 25 | #include <type_traits> |
7c673cae FG |
26 | #include <vector> |
27 | ||
28 | #include <boost/concept/requires.hpp> | |
92f5a8d4 | 29 | #include <boost/core/ignore_unused.hpp> |
20effc67 TL |
30 | #include <boost/range/begin.hpp> |
31 | #include <boost/range/end.hpp> | |
32 | #include <boost/range/size.hpp> | |
33 | #include <boost/range/value_type.hpp> | |
7c673cae | 34 | |
92f5a8d4 TL |
35 | #include <boost/geometry/core/config.hpp> |
36 | ||
7c673cae FG |
37 | #include <boost/geometry/algorithms/assign.hpp> |
38 | #include <boost/geometry/algorithms/envelope.hpp> | |
39 | #include <boost/geometry/algorithms/expand.hpp> | |
20effc67 | 40 | #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> |
7c673cae FG |
41 | #include <boost/geometry/algorithms/detail/interior_iterator.hpp> |
42 | #include <boost/geometry/algorithms/detail/recalculate.hpp> | |
43 | #include <boost/geometry/algorithms/detail/ring_identifier.hpp> | |
44 | #include <boost/geometry/algorithms/detail/signed_size_type.hpp> | |
20effc67 | 45 | #include <boost/geometry/algorithms/detail/buffer/buffer_box.hpp> |
7c673cae FG |
46 | |
47 | #include <boost/geometry/core/access.hpp> | |
48 | #include <boost/geometry/core/closure.hpp> | |
49 | #include <boost/geometry/core/exterior_ring.hpp> | |
50 | #include <boost/geometry/core/point_order.hpp> | |
20effc67 | 51 | #include <boost/geometry/core/static_assert.hpp> |
7c673cae FG |
52 | #include <boost/geometry/core/tags.hpp> |
53 | ||
54 | #include <boost/geometry/geometries/concepts/check.hpp> | |
20effc67 | 55 | #include <boost/geometry/geometries/segment.hpp> |
7c673cae FG |
56 | #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> |
57 | #include <boost/geometry/policies/robustness/robust_point_type.hpp> | |
20effc67 TL |
58 | #include <boost/geometry/util/math.hpp> |
59 | #include <boost/geometry/util/normalize_spheroidal_coordinates.hpp> | |
60 | #include <boost/geometry/util/sequence.hpp> | |
7c673cae FG |
61 | #include <boost/geometry/views/closeable_view.hpp> |
62 | #include <boost/geometry/views/reversible_view.hpp> | |
92f5a8d4 | 63 | |
20effc67 TL |
64 | // TEMP |
65 | #include <boost/geometry/strategy/envelope.hpp> | |
66 | #include <boost/geometry/strategy/expand.hpp> | |
7c673cae FG |
67 | |
68 | namespace boost { namespace geometry | |
69 | { | |
70 | ||
71 | ||
72 | /*! | |
73 | \brief Structure containing section information | |
74 | \details Section information consists of a bounding box, direction | |
75 | information (if it is increasing or decreasing, per dimension), | |
76 | index information (begin-end, ring, multi) and the number of | |
77 | segments in this section | |
78 | ||
79 | \tparam Box box-type | |
80 | \tparam DimensionCount number of dimensions for this section | |
81 | \ingroup sectionalize | |
82 | */ | |
83 | template | |
84 | < | |
85 | typename Box, | |
86 | std::size_t DimensionCount | |
87 | > | |
88 | struct section | |
89 | { | |
90 | typedef Box box_type; | |
91 | static std::size_t const dimension_count = DimensionCount; | |
92 | ||
93 | int directions[DimensionCount]; | |
94 | ring_identifier ring_id; | |
95 | Box bounding_box; | |
96 | ||
97 | // NOTE: size_type could be passed as template parameter | |
98 | // NOTE: these probably also could be of type std::size_t | |
99 | signed_size_type begin_index; | |
100 | signed_size_type end_index; | |
101 | std::size_t count; | |
102 | std::size_t range_count; | |
103 | bool duplicate; | |
104 | signed_size_type non_duplicate_index; | |
105 | ||
106 | bool is_non_duplicate_first; | |
107 | bool is_non_duplicate_last; | |
108 | ||
109 | inline section() | |
110 | : begin_index(-1) | |
111 | , end_index(-1) | |
112 | , count(0) | |
113 | , range_count(0) | |
114 | , duplicate(false) | |
115 | , non_duplicate_index(-1) | |
116 | , is_non_duplicate_first(false) | |
117 | , is_non_duplicate_last(false) | |
118 | { | |
119 | assign_inverse(bounding_box); | |
120 | for (std::size_t i = 0; i < DimensionCount; i++) | |
121 | { | |
122 | directions[i] = 0; | |
123 | } | |
124 | } | |
125 | }; | |
126 | ||
127 | ||
128 | /*! | |
129 | \brief Structure containing a collection of sections | |
130 | \note Derived from a vector, proves to be faster than of deque | |
131 | \note vector might be templated in the future | |
132 | \ingroup sectionalize | |
133 | */ | |
134 | template <typename Box, std::size_t DimensionCount> | |
135 | struct sections : std::vector<section<Box, DimensionCount> > | |
136 | { | |
137 | typedef Box box_type; | |
138 | static std::size_t const value = DimensionCount; | |
139 | }; | |
140 | ||
141 | ||
142 | #ifndef DOXYGEN_NO_DETAIL | |
143 | namespace detail { namespace sectionalize | |
144 | { | |
145 | ||
b32b8144 FG |
146 | // NOTE: This utility will NOT work for latitudes, dimension 1 in spherical |
147 | // and geographic coordinate system because in these coordinate systems | |
148 | // e.g. a segment on northern hemisphere may go towards greater latitude | |
149 | // and then towards lesser latitude. | |
7c673cae FG |
150 | template |
151 | < | |
b32b8144 | 152 | typename Point, |
7c673cae FG |
153 | typename DimensionVector, |
154 | std::size_t Index, | |
b32b8144 FG |
155 | std::size_t Count, |
156 | typename CastedCSTag = typename tag_cast | |
157 | < | |
158 | typename cs_tag<Point>::type, | |
159 | spherical_tag | |
160 | >::type | |
7c673cae FG |
161 | > |
162 | struct get_direction_loop | |
163 | { | |
20effc67 | 164 | typedef typename util::sequence_element<Index, DimensionVector>::type dimension; |
7c673cae FG |
165 | |
166 | template <typename Segment> | |
167 | static inline void apply(Segment const& seg, | |
168 | int directions[Count]) | |
169 | { | |
170 | typedef typename coordinate_type<Segment>::type coordinate_type; | |
171 | ||
92f5a8d4 TL |
172 | coordinate_type const c0 = geometry::get<0, dimension::value>(seg); |
173 | coordinate_type const c1 = geometry::get<1, dimension::value>(seg); | |
7c673cae | 174 | |
92f5a8d4 | 175 | directions[Index] = c1 > c0 ? 1 : c1 < c0 ? -1 : 0; |
7c673cae FG |
176 | |
177 | get_direction_loop | |
178 | < | |
b32b8144 | 179 | Point, |
7c673cae FG |
180 | DimensionVector, |
181 | Index + 1, | |
b32b8144 FG |
182 | Count, |
183 | CastedCSTag | |
184 | >::apply(seg, directions); | |
185 | } | |
186 | }; | |
187 | ||
188 | template | |
189 | < | |
190 | typename Point, | |
191 | typename DimensionVector, | |
192 | std::size_t Count | |
193 | > | |
194 | struct get_direction_loop<Point, DimensionVector, 0, Count, spherical_tag> | |
195 | { | |
20effc67 | 196 | typedef typename util::sequence_element<0, DimensionVector>::type dimension; |
b32b8144 FG |
197 | |
198 | template <typename Segment> | |
199 | static inline void apply(Segment const& seg, | |
200 | int directions[Count]) | |
201 | { | |
202 | typedef typename coordinate_type<Segment>::type coordinate_type; | |
203 | typedef typename coordinate_system<Point>::type::units units_t; | |
204 | ||
205 | coordinate_type const diff = math::longitude_distance_signed | |
206 | < | |
207 | units_t, coordinate_type | |
208 | >(geometry::get<0, 0>(seg), | |
209 | geometry::get<1, 0>(seg)); | |
210 | ||
211 | coordinate_type zero = coordinate_type(); | |
212 | directions[0] = diff > zero ? 1 : diff < zero ? -1 : 0; | |
213 | ||
214 | get_direction_loop | |
215 | < | |
216 | Point, | |
217 | DimensionVector, | |
218 | 1, | |
219 | Count, | |
220 | spherical_tag | |
7c673cae FG |
221 | >::apply(seg, directions); |
222 | } | |
223 | }; | |
224 | ||
b32b8144 FG |
225 | template |
226 | < | |
227 | typename Point, | |
228 | typename DimensionVector, | |
229 | std::size_t Count, | |
230 | typename CastedCSTag | |
231 | > | |
232 | struct get_direction_loop<Point, DimensionVector, Count, Count, CastedCSTag> | |
7c673cae FG |
233 | { |
234 | template <typename Segment> | |
235 | static inline void apply(Segment const&, int [Count]) | |
236 | {} | |
237 | }; | |
238 | ||
b32b8144 | 239 | |
7c673cae FG |
240 | //! Copy one static array to another |
241 | template <typename T, std::size_t Index, std::size_t Count> | |
242 | struct copy_loop | |
243 | { | |
244 | static inline void apply(T const source[Count], T target[Count]) | |
245 | { | |
246 | target[Index] = source[Index]; | |
247 | copy_loop<T, Index + 1, Count>::apply(source, target); | |
248 | } | |
249 | }; | |
250 | ||
251 | template <typename T, std::size_t Count> | |
252 | struct copy_loop<T, Count, Count> | |
253 | { | |
254 | static inline void apply(T const [Count], T [Count]) | |
255 | {} | |
256 | }; | |
257 | ||
258 | //! Compare two static arrays | |
259 | template <typename T, std::size_t Index, std::size_t Count> | |
260 | struct compare_loop | |
261 | { | |
262 | static inline bool apply(T const array1[Count], T const array2[Count]) | |
263 | { | |
264 | return array1[Index] != array2[Index] | |
265 | ? false | |
266 | : compare_loop | |
267 | < | |
268 | T, Index + 1, Count | |
269 | >::apply(array1, array2); | |
270 | } | |
271 | }; | |
272 | ||
273 | template <typename T, std::size_t Count> | |
274 | struct compare_loop<T, Count, Count> | |
275 | { | |
276 | static inline bool apply(T const [Count], T const [Count]) | |
277 | { | |
278 | ||
279 | return true; | |
280 | } | |
281 | }; | |
282 | ||
283 | ||
284 | template <std::size_t Dimension, std::size_t DimensionCount> | |
285 | struct check_duplicate_loop | |
286 | { | |
287 | template <typename Segment> | |
288 | static inline bool apply(Segment const& seg) | |
289 | { | |
290 | if (! geometry::math::equals | |
291 | ( | |
292 | geometry::get<0, Dimension>(seg), | |
293 | geometry::get<1, Dimension>(seg) | |
294 | ) | |
295 | ) | |
296 | { | |
297 | return false; | |
298 | } | |
299 | ||
300 | return check_duplicate_loop | |
301 | < | |
302 | Dimension + 1, DimensionCount | |
303 | >::apply(seg); | |
304 | } | |
305 | }; | |
306 | ||
307 | template <std::size_t DimensionCount> | |
308 | struct check_duplicate_loop<DimensionCount, DimensionCount> | |
309 | { | |
310 | template <typename Segment> | |
311 | static inline bool apply(Segment const&) | |
312 | { | |
313 | return true; | |
314 | } | |
315 | }; | |
316 | ||
317 | //! Assign a value to a static array | |
318 | template <typename T, std::size_t Index, std::size_t Count> | |
319 | struct assign_loop | |
320 | { | |
321 | static inline void apply(T dims[Count], T const value) | |
322 | { | |
323 | dims[Index] = value; | |
324 | assign_loop<T, Index + 1, Count>::apply(dims, value); | |
325 | } | |
326 | }; | |
327 | ||
328 | template <typename T, std::size_t Count> | |
329 | struct assign_loop<T, Count, Count> | |
330 | { | |
331 | static inline void apply(T [Count], T const) | |
332 | { | |
333 | } | |
334 | }; | |
335 | ||
336 | template <typename CSTag> | |
337 | struct box_first_in_section | |
338 | { | |
92f5a8d4 | 339 | template <typename Box, typename Point, typename EnvelopeStrategy> |
b32b8144 | 340 | static inline void apply(Box & box, Point const& prev, Point const& curr, |
92f5a8d4 | 341 | EnvelopeStrategy const& strategy) |
7c673cae FG |
342 | { |
343 | geometry::model::referring_segment<Point const> seg(prev, curr); | |
b32b8144 | 344 | geometry::envelope(seg, box, strategy); |
7c673cae FG |
345 | } |
346 | }; | |
347 | ||
348 | template <> | |
349 | struct box_first_in_section<cartesian_tag> | |
350 | { | |
92f5a8d4 | 351 | template <typename Box, typename Point, typename ExpandStrategy> |
b32b8144 | 352 | static inline void apply(Box & box, Point const& prev, Point const& curr, |
92f5a8d4 | 353 | ExpandStrategy const& ) |
7c673cae FG |
354 | { |
355 | geometry::envelope(prev, box); | |
356 | geometry::expand(box, curr); | |
357 | } | |
358 | }; | |
359 | ||
360 | template <typename CSTag> | |
361 | struct box_next_in_section | |
362 | { | |
b32b8144 FG |
363 | template <typename Box, typename Point, typename Strategy> |
364 | static inline void apply(Box & box, Point const& prev, Point const& curr, | |
365 | Strategy const& strategy) | |
7c673cae FG |
366 | { |
367 | geometry::model::referring_segment<Point const> seg(prev, curr); | |
b32b8144 | 368 | geometry::expand(box, seg, strategy); |
7c673cae FG |
369 | } |
370 | }; | |
371 | ||
372 | template <> | |
373 | struct box_next_in_section<cartesian_tag> | |
374 | { | |
b32b8144 FG |
375 | template <typename Box, typename Point, typename Strategy> |
376 | static inline void apply(Box & box, Point const& , Point const& curr, | |
377 | Strategy const& ) | |
7c673cae FG |
378 | { |
379 | geometry::expand(box, curr); | |
380 | } | |
381 | }; | |
382 | ||
383 | /// @brief Helper class to create sections of a part of a range, on the fly | |
384 | template | |
385 | < | |
386 | typename Point, | |
387 | typename DimensionVector | |
388 | > | |
389 | struct sectionalize_part | |
390 | { | |
391 | static const std::size_t dimension_count | |
20effc67 | 392 | = util::sequence_size<DimensionVector>::value; |
7c673cae FG |
393 | |
394 | template | |
395 | < | |
396 | typename Iterator, | |
397 | typename RobustPolicy, | |
398 | typename Sections | |
399 | > | |
400 | static inline void apply(Sections& sections, | |
401 | Iterator begin, Iterator end, | |
402 | RobustPolicy const& robust_policy, | |
403 | ring_identifier ring_id, | |
404 | std::size_t max_count) | |
b32b8144 FG |
405 | { |
406 | typedef typename strategy::envelope::services::default_strategy | |
407 | < | |
92f5a8d4 | 408 | segment_tag, |
b32b8144 FG |
409 | typename cs_tag<typename Sections::box_type>::type |
410 | >::type envelope_strategy_type; | |
411 | ||
92f5a8d4 TL |
412 | typedef typename strategy::expand::services::default_strategy |
413 | < | |
414 | segment_tag, | |
415 | typename cs_tag<typename Sections::box_type>::type | |
416 | >::type expand_strategy_type; | |
417 | ||
b32b8144 | 418 | apply(sections, begin, end, |
92f5a8d4 TL |
419 | robust_policy, |
420 | envelope_strategy_type(), | |
421 | expand_strategy_type(), | |
b32b8144 FG |
422 | ring_id, max_count); |
423 | } | |
424 | ||
425 | template | |
426 | < | |
427 | typename Iterator, | |
428 | typename RobustPolicy, | |
429 | typename Sections, | |
92f5a8d4 TL |
430 | typename EnvelopeStrategy, |
431 | typename ExpandStrategy | |
b32b8144 FG |
432 | > |
433 | static inline void apply(Sections& sections, | |
434 | Iterator begin, Iterator end, | |
435 | RobustPolicy const& robust_policy, | |
92f5a8d4 TL |
436 | EnvelopeStrategy const& envelope_strategy, |
437 | ExpandStrategy const& expand_strategy, | |
b32b8144 FG |
438 | ring_identifier ring_id, |
439 | std::size_t max_count) | |
7c673cae | 440 | { |
92f5a8d4 | 441 | boost::ignore_unused(robust_policy); |
7c673cae FG |
442 | |
443 | typedef typename boost::range_value<Sections>::type section_type; | |
444 | BOOST_STATIC_ASSERT | |
445 | ( | |
20effc67 TL |
446 | section_type::dimension_count |
447 | == util::sequence_size<DimensionVector>::value | |
7c673cae FG |
448 | ); |
449 | ||
450 | typedef typename geometry::robust_point_type | |
451 | < | |
452 | Point, | |
453 | RobustPolicy | |
454 | >::type robust_point_type; | |
455 | ||
456 | std::size_t const count = std::distance(begin, end); | |
457 | if (count == 0) | |
458 | { | |
459 | return; | |
460 | } | |
461 | ||
462 | signed_size_type index = 0; | |
463 | signed_size_type ndi = 0; // non duplicate index | |
464 | section_type section; | |
465 | ||
466 | bool mark_first_non_duplicated = true; | |
467 | std::size_t last_non_duplicate_index = sections.size(); | |
468 | ||
469 | Iterator it = begin; | |
470 | robust_point_type previous_robust_point; | |
471 | geometry::recalculate(previous_robust_point, *it, robust_policy); | |
472 | ||
473 | for(Iterator previous = it++; | |
474 | it != end; | |
475 | ++previous, ++it, index++) | |
476 | { | |
477 | robust_point_type current_robust_point; | |
478 | geometry::recalculate(current_robust_point, *it, robust_policy); | |
479 | model::referring_segment<robust_point_type> robust_segment( | |
480 | previous_robust_point, current_robust_point); | |
481 | ||
482 | int direction_classes[dimension_count] = {0}; | |
483 | get_direction_loop | |
484 | < | |
b32b8144 | 485 | Point, DimensionVector, 0, dimension_count |
7c673cae FG |
486 | >::apply(robust_segment, direction_classes); |
487 | ||
488 | // if "dir" == 0 for all point-dimensions, it is duplicate. | |
489 | // Those sections might be omitted, if wished, lateron | |
490 | bool duplicate = false; | |
491 | ||
492 | if (direction_classes[0] == 0) | |
493 | { | |
494 | // Recheck because ALL dimensions should be checked, | |
495 | // not only first one. | |
496 | // (dimension_count might be < dimension<P>::value) | |
497 | if (check_duplicate_loop | |
498 | < | |
499 | 0, geometry::dimension<Point>::type::value | |
500 | >::apply(robust_segment) | |
501 | ) | |
502 | { | |
503 | duplicate = true; | |
504 | ||
505 | // Change direction-info to force new section | |
506 | // Note that wo consecutive duplicate segments will generate | |
507 | // only one duplicate-section. | |
508 | // Actual value is not important as long as it is not -1,0,1 | |
509 | assign_loop | |
510 | < | |
511 | int, 0, dimension_count | |
512 | >::apply(direction_classes, -99); | |
513 | } | |
514 | } | |
515 | ||
516 | if (section.count > 0 | |
517 | && (! compare_loop | |
518 | < | |
519 | int, 0, dimension_count | |
520 | >::apply(direction_classes, section.directions) | |
521 | || section.count > max_count) | |
522 | ) | |
523 | { | |
524 | if (! section.duplicate) | |
525 | { | |
526 | last_non_duplicate_index = sections.size(); | |
527 | } | |
528 | ||
529 | sections.push_back(section); | |
530 | section = section_type(); | |
531 | } | |
532 | ||
533 | if (section.count == 0) | |
534 | { | |
535 | section.begin_index = index; | |
536 | section.ring_id = ring_id; | |
537 | section.duplicate = duplicate; | |
538 | section.non_duplicate_index = ndi; | |
539 | section.range_count = count; | |
540 | ||
541 | if (mark_first_non_duplicated && ! duplicate) | |
542 | { | |
543 | section.is_non_duplicate_first = true; | |
544 | mark_first_non_duplicated = false; | |
545 | } | |
546 | ||
547 | copy_loop | |
548 | < | |
549 | int, 0, dimension_count | |
550 | >::apply(direction_classes, section.directions); | |
551 | ||
552 | // In cartesian this is envelope of previous point expanded with current point | |
553 | // in non-cartesian this is envelope of a segment | |
554 | box_first_in_section<typename cs_tag<robust_point_type>::type> | |
92f5a8d4 | 555 | ::apply(section.bounding_box, previous_robust_point, current_robust_point, envelope_strategy); |
7c673cae FG |
556 | } |
557 | else | |
558 | { | |
559 | // In cartesian this is expand with current point | |
560 | // in non-cartesian this is expand with a segment | |
561 | box_next_in_section<typename cs_tag<robust_point_type>::type> | |
92f5a8d4 | 562 | ::apply(section.bounding_box, previous_robust_point, current_robust_point, expand_strategy); |
7c673cae FG |
563 | } |
564 | ||
565 | section.end_index = index + 1; | |
566 | section.count++; | |
567 | if (! duplicate) | |
568 | { | |
569 | ndi++; | |
570 | } | |
571 | previous_robust_point = current_robust_point; | |
572 | } | |
573 | ||
574 | // Add last section if applicable | |
575 | if (section.count > 0) | |
576 | { | |
577 | if (! section.duplicate) | |
578 | { | |
579 | last_non_duplicate_index = sections.size(); | |
580 | } | |
581 | ||
582 | sections.push_back(section); | |
583 | } | |
584 | ||
585 | if (last_non_duplicate_index < sections.size() | |
586 | && ! sections[last_non_duplicate_index].duplicate) | |
587 | { | |
588 | sections[last_non_duplicate_index].is_non_duplicate_last = true; | |
589 | } | |
590 | } | |
591 | }; | |
592 | ||
593 | ||
594 | template | |
595 | < | |
596 | closure_selector Closure, | |
597 | bool Reverse, | |
598 | typename Point, | |
599 | typename DimensionVector | |
600 | > | |
601 | struct sectionalize_range | |
602 | { | |
603 | template | |
604 | < | |
605 | typename Range, | |
606 | typename RobustPolicy, | |
b32b8144 | 607 | typename Sections, |
92f5a8d4 TL |
608 | typename EnvelopeStrategy, |
609 | typename ExpandStrategy | |
7c673cae FG |
610 | > |
611 | static inline void apply(Range const& range, | |
612 | RobustPolicy const& robust_policy, | |
613 | Sections& sections, | |
92f5a8d4 TL |
614 | EnvelopeStrategy const& envelope_strategy, |
615 | ExpandStrategy const& expand_strategy, | |
7c673cae FG |
616 | ring_identifier ring_id, |
617 | std::size_t max_count) | |
618 | { | |
619 | typedef typename closeable_view<Range const, Closure>::type cview_type; | |
620 | typedef typename reversible_view | |
621 | < | |
622 | cview_type const, | |
623 | Reverse ? iterate_reverse : iterate_forward | |
624 | >::type view_type; | |
625 | ||
626 | cview_type cview(range); | |
627 | view_type view(cview); | |
628 | ||
629 | std::size_t const n = boost::size(view); | |
630 | if (n == 0) | |
631 | { | |
632 | // Zero points, no section | |
633 | return; | |
634 | } | |
635 | ||
636 | if (n == 1) | |
637 | { | |
638 | // Line with one point ==> no sections | |
639 | return; | |
640 | } | |
641 | ||
642 | sectionalize_part<Point, DimensionVector>::apply(sections, | |
643 | boost::begin(view), boost::end(view), | |
92f5a8d4 TL |
644 | robust_policy, envelope_strategy, expand_strategy, |
645 | ring_id, max_count); | |
7c673cae FG |
646 | } |
647 | }; | |
648 | ||
649 | template | |
650 | < | |
651 | bool Reverse, | |
652 | typename DimensionVector | |
653 | > | |
654 | struct sectionalize_polygon | |
655 | { | |
656 | template | |
657 | < | |
658 | typename Polygon, | |
659 | typename RobustPolicy, | |
b32b8144 | 660 | typename Sections, |
92f5a8d4 TL |
661 | typename EnvelopeStrategy, |
662 | typename ExpandStrategy | |
7c673cae FG |
663 | > |
664 | static inline void apply(Polygon const& poly, | |
665 | RobustPolicy const& robust_policy, | |
666 | Sections& sections, | |
92f5a8d4 TL |
667 | EnvelopeStrategy const& envelope_strategy, |
668 | ExpandStrategy const& expand_strategy, | |
b32b8144 FG |
669 | ring_identifier ring_id, |
670 | std::size_t max_count) | |
7c673cae FG |
671 | { |
672 | typedef typename point_type<Polygon>::type point_type; | |
673 | typedef sectionalize_range | |
674 | < | |
675 | closure<Polygon>::value, Reverse, | |
676 | point_type, DimensionVector | |
677 | > per_range; | |
678 | ||
679 | ring_id.ring_index = -1; | |
92f5a8d4 TL |
680 | per_range::apply(exterior_ring(poly), robust_policy, sections, |
681 | envelope_strategy, expand_strategy, ring_id, max_count); | |
7c673cae FG |
682 | |
683 | ring_id.ring_index++; | |
684 | typename interior_return_type<Polygon const>::type | |
685 | rings = interior_rings(poly); | |
686 | for (typename detail::interior_iterator<Polygon const>::type | |
687 | it = boost::begin(rings); it != boost::end(rings); ++it, ++ring_id.ring_index) | |
688 | { | |
92f5a8d4 TL |
689 | per_range::apply(*it, robust_policy, sections, |
690 | envelope_strategy, expand_strategy, ring_id, max_count); | |
7c673cae FG |
691 | } |
692 | } | |
693 | }; | |
694 | ||
695 | template <typename DimensionVector> | |
696 | struct sectionalize_box | |
697 | { | |
698 | template | |
699 | < | |
700 | typename Box, | |
701 | typename RobustPolicy, | |
b32b8144 | 702 | typename Sections, |
92f5a8d4 TL |
703 | typename EnvelopeStrategy, |
704 | typename ExpandStrategy | |
7c673cae FG |
705 | > |
706 | static inline void apply(Box const& box, | |
707 | RobustPolicy const& robust_policy, | |
708 | Sections& sections, | |
92f5a8d4 TL |
709 | EnvelopeStrategy const& envelope_strategy, |
710 | ExpandStrategy const& expand_strategy, | |
7c673cae FG |
711 | ring_identifier const& ring_id, std::size_t max_count) |
712 | { | |
713 | typedef typename point_type<Box>::type point_type; | |
714 | ||
715 | assert_dimension<Box, 2>(); | |
716 | ||
717 | // Add all four sides of the 2D-box as separate section. | |
718 | // Easiest is to convert it to a polygon. | |
719 | // However, we don't have the polygon type | |
720 | // (or polygon would be a helper-type). | |
721 | // Therefore we mimic a linestring/std::vector of 5 points | |
722 | ||
723 | // TODO: might be replaced by assign_box_corners_oriented | |
724 | // or just "convert" | |
725 | point_type ll, lr, ul, ur; | |
726 | geometry::detail::assign_box_corners(box, ll, lr, ul, ur); | |
727 | ||
728 | std::vector<point_type> points; | |
729 | points.push_back(ll); | |
730 | points.push_back(ul); | |
731 | points.push_back(ur); | |
732 | points.push_back(lr); | |
733 | points.push_back(ll); | |
734 | ||
b32b8144 FG |
735 | // NOTE: Use cartesian envelope strategy in all coordinate systems |
736 | // because edges of a box are not geodesic segments | |
7c673cae FG |
737 | sectionalize_range |
738 | < | |
739 | closed, false, | |
740 | point_type, | |
741 | DimensionVector | |
742 | >::apply(points, robust_policy, sections, | |
92f5a8d4 | 743 | envelope_strategy, expand_strategy, |
7c673cae FG |
744 | ring_id, max_count); |
745 | } | |
746 | }; | |
747 | ||
748 | template <typename DimensionVector, typename Policy> | |
749 | struct sectionalize_multi | |
750 | { | |
751 | template | |
752 | < | |
753 | typename MultiGeometry, | |
754 | typename RobustPolicy, | |
b32b8144 | 755 | typename Sections, |
92f5a8d4 TL |
756 | typename EnvelopeStrategy, |
757 | typename ExpandStrategy | |
7c673cae FG |
758 | > |
759 | static inline void apply(MultiGeometry const& multi, | |
760 | RobustPolicy const& robust_policy, | |
b32b8144 | 761 | Sections& sections, |
92f5a8d4 TL |
762 | EnvelopeStrategy const& envelope_strategy, |
763 | ExpandStrategy const& expand_strategy, | |
b32b8144 FG |
764 | ring_identifier ring_id, |
765 | std::size_t max_count) | |
7c673cae FG |
766 | { |
767 | ring_id.multi_index = 0; | |
768 | for (typename boost::range_iterator<MultiGeometry const>::type | |
769 | it = boost::begin(multi); | |
770 | it != boost::end(multi); | |
771 | ++it, ++ring_id.multi_index) | |
772 | { | |
92f5a8d4 TL |
773 | Policy::apply(*it, robust_policy, sections, |
774 | envelope_strategy, expand_strategy, | |
775 | ring_id, max_count); | |
7c673cae FG |
776 | } |
777 | } | |
778 | }; | |
779 | ||
92f5a8d4 TL |
780 | // TODO: If it depends on CS it should probably be made into strategy. |
781 | // For now implemented here because of ongoing work on robustness | |
782 | // the fact that it interferes with detail::buffer::buffer_box | |
783 | // and that we probably need a general strategy for defining epsilon in | |
784 | // various coordinate systems, e.g. for point comparison, enlargement of | |
785 | // bounding boxes, etc. | |
786 | template <typename CSTag> | |
787 | struct expand_by_epsilon | |
788 | : not_implemented<CSTag> | |
789 | {}; | |
790 | ||
791 | template <> | |
792 | struct expand_by_epsilon<cartesian_tag> | |
7c673cae | 793 | { |
92f5a8d4 TL |
794 | template <typename Box> |
795 | static inline void apply(Box & box) | |
796 | { | |
797 | detail::expand_by_epsilon(box); | |
798 | } | |
799 | }; | |
800 | ||
801 | template <> | |
802 | struct expand_by_epsilon<spherical_tag> | |
803 | { | |
804 | template <typename Box> | |
805 | static inline void apply(Box & box) | |
806 | { | |
807 | typedef typename coordinate_type<Box>::type coord_t; | |
20effc67 | 808 | static const coord_t eps = std::is_same<coord_t, float>::value |
92f5a8d4 TL |
809 | ? coord_t(1e-6) |
810 | : coord_t(1e-12); | |
811 | detail::expand_by_epsilon(box, eps); | |
812 | } | |
813 | }; | |
814 | ||
815 | // TODO: In geographic CS it should probably also depend on FormulaPolicy. | |
816 | template <> | |
817 | struct expand_by_epsilon<geographic_tag> | |
818 | : expand_by_epsilon<spherical_tag> | |
819 | {}; | |
820 | ||
821 | template <typename Sections, typename Strategy> | |
822 | inline void enlarge_sections(Sections& sections, Strategy const&) | |
823 | { | |
824 | // Enlarge sections slightly, this should be consistent with math::equals() | |
825 | // and with the tolerances used in general_form intersections. | |
826 | // This avoids missing turns. | |
7c673cae | 827 | |
7c673cae FG |
828 | // Points and Segments are equal-compared WRT machine epsilon, but Boxes aren't |
829 | // Enlarging Boxes ensures that they correspond to the bound objects, | |
830 | // Segments in this case, since Sections are collections of Segments. | |
92f5a8d4 TL |
831 | |
832 | // It makes section a tiny bit too large, which might cause (a small number) | |
833 | // of more comparisons | |
7c673cae FG |
834 | for (typename boost::range_iterator<Sections>::type it = boost::begin(sections); |
835 | it != boost::end(sections); | |
836 | ++it) | |
837 | { | |
92f5a8d4 TL |
838 | #if defined(BOOST_GEOMETRY_USE_RESCALING) |
839 | detail::sectionalize::expand_by_epsilon | |
840 | < | |
841 | typename Strategy::cs_tag | |
842 | >::apply(it->bounding_box); | |
843 | ||
844 | #else | |
845 | // Expand the box to avoid missing any intersection. The amount is | |
846 | // should be larger than epsilon. About the value itself: the smaller | |
847 | // it is, the higher the risk to miss intersections. The larger it is, | |
848 | // the more comparisons are made. So it should be on the high side. | |
849 | detail::buffer::buffer_box(it->bounding_box, 0.001, it->bounding_box); | |
850 | #endif | |
7c673cae FG |
851 | } |
852 | } | |
853 | ||
854 | ||
855 | }} // namespace detail::sectionalize | |
856 | #endif // DOXYGEN_NO_DETAIL | |
857 | ||
858 | ||
859 | #ifndef DOXYGEN_NO_DISPATCH | |
860 | namespace dispatch | |
861 | { | |
862 | ||
863 | template | |
864 | < | |
865 | typename Tag, | |
866 | typename Geometry, | |
867 | bool Reverse, | |
868 | typename DimensionVector | |
869 | > | |
870 | struct sectionalize | |
871 | { | |
20effc67 TL |
872 | BOOST_GEOMETRY_STATIC_ASSERT_FALSE( |
873 | "Not or not yet implemented for this Geometry type.", | |
874 | Tag, Geometry); | |
7c673cae FG |
875 | }; |
876 | ||
877 | template | |
878 | < | |
879 | typename Box, | |
880 | bool Reverse, | |
881 | typename DimensionVector | |
882 | > | |
883 | struct sectionalize<box_tag, Box, Reverse, DimensionVector> | |
884 | : detail::sectionalize::sectionalize_box<DimensionVector> | |
885 | {}; | |
886 | ||
887 | template | |
888 | < | |
889 | typename LineString, | |
890 | typename DimensionVector | |
891 | > | |
892 | struct sectionalize | |
893 | < | |
894 | linestring_tag, | |
895 | LineString, | |
896 | false, | |
897 | DimensionVector | |
898 | > | |
899 | : detail::sectionalize::sectionalize_range | |
900 | < | |
901 | closed, false, | |
902 | typename point_type<LineString>::type, | |
903 | DimensionVector | |
904 | > | |
905 | {}; | |
906 | ||
907 | template | |
908 | < | |
909 | typename Ring, | |
910 | bool Reverse, | |
911 | typename DimensionVector | |
912 | > | |
913 | struct sectionalize<ring_tag, Ring, Reverse, DimensionVector> | |
914 | : detail::sectionalize::sectionalize_range | |
915 | < | |
916 | geometry::closure<Ring>::value, Reverse, | |
917 | typename point_type<Ring>::type, | |
918 | DimensionVector | |
919 | > | |
920 | {}; | |
921 | ||
922 | template | |
923 | < | |
924 | typename Polygon, | |
925 | bool Reverse, | |
926 | typename DimensionVector | |
927 | > | |
928 | struct sectionalize<polygon_tag, Polygon, Reverse, DimensionVector> | |
929 | : detail::sectionalize::sectionalize_polygon | |
930 | < | |
931 | Reverse, DimensionVector | |
932 | > | |
933 | {}; | |
934 | ||
935 | template | |
936 | < | |
937 | typename MultiPolygon, | |
938 | bool Reverse, | |
939 | typename DimensionVector | |
940 | > | |
941 | struct sectionalize<multi_polygon_tag, MultiPolygon, Reverse, DimensionVector> | |
942 | : detail::sectionalize::sectionalize_multi | |
943 | < | |
944 | DimensionVector, | |
945 | detail::sectionalize::sectionalize_polygon | |
946 | < | |
947 | Reverse, | |
948 | DimensionVector | |
949 | > | |
950 | > | |
951 | ||
952 | {}; | |
953 | ||
954 | template | |
955 | < | |
956 | typename MultiLinestring, | |
957 | bool Reverse, | |
958 | typename DimensionVector | |
959 | > | |
960 | struct sectionalize<multi_linestring_tag, MultiLinestring, Reverse, DimensionVector> | |
961 | : detail::sectionalize::sectionalize_multi | |
962 | < | |
963 | DimensionVector, | |
964 | detail::sectionalize::sectionalize_range | |
965 | < | |
966 | closed, false, | |
967 | typename point_type<MultiLinestring>::type, | |
968 | DimensionVector | |
969 | > | |
970 | > | |
971 | ||
972 | {}; | |
973 | ||
974 | } // namespace dispatch | |
975 | #endif | |
976 | ||
977 | ||
978 | /*! | |
979 | \brief Split a geometry into monotonic sections | |
980 | \ingroup sectionalize | |
981 | \tparam Geometry type of geometry to check | |
982 | \tparam Sections type of sections to create | |
983 | \param geometry geometry to create sections from | |
984 | \param robust_policy policy to handle robustness issues | |
985 | \param sections structure with sections | |
92f5a8d4 TL |
986 | \param envelope_strategy strategy for envelope calculation |
987 | \param expand_strategy strategy for partitions | |
7c673cae FG |
988 | \param source_index index to assign to the ring_identifiers |
989 | \param max_count maximal number of points per section | |
990 | (defaults to 10, this seems to give the fastest results) | |
991 | ||
992 | */ | |
993 | template | |
994 | < | |
995 | bool Reverse, | |
996 | typename DimensionVector, | |
997 | typename Geometry, | |
998 | typename Sections, | |
b32b8144 | 999 | typename RobustPolicy, |
92f5a8d4 TL |
1000 | typename EnvelopeStrategy, |
1001 | typename ExpandStrategy | |
7c673cae FG |
1002 | > |
1003 | inline void sectionalize(Geometry const& geometry, | |
1004 | RobustPolicy const& robust_policy, | |
1005 | Sections& sections, | |
92f5a8d4 TL |
1006 | EnvelopeStrategy const& envelope_strategy, |
1007 | ExpandStrategy const& expand_strategy, | |
7c673cae FG |
1008 | int source_index = 0, |
1009 | std::size_t max_count = 10) | |
1010 | { | |
20effc67 | 1011 | BOOST_STATIC_ASSERT((! std::is_fundamental<EnvelopeStrategy>::value)); |
b32b8144 | 1012 | |
7c673cae FG |
1013 | concepts::check<Geometry const>(); |
1014 | ||
1015 | typedef typename boost::range_value<Sections>::type section_type; | |
1016 | ||
1017 | // Compiletime check for point type of section boxes | |
1018 | // and point type related to robust policy | |
1019 | typedef typename geometry::coordinate_type | |
1020 | < | |
1021 | typename section_type::box_type | |
1022 | >::type ctype1; | |
1023 | typedef typename geometry::coordinate_type | |
1024 | < | |
1025 | typename geometry::robust_point_type | |
1026 | < | |
1027 | typename geometry::point_type<Geometry>::type, | |
1028 | RobustPolicy | |
1029 | >::type | |
1030 | >::type ctype2; | |
1031 | ||
20effc67 | 1032 | BOOST_STATIC_ASSERT((std::is_same<ctype1, ctype2>::value)); |
7c673cae FG |
1033 | |
1034 | ||
1035 | sections.clear(); | |
1036 | ||
1037 | ring_identifier ring_id; | |
1038 | ring_id.source_index = source_index; | |
1039 | ||
1040 | dispatch::sectionalize | |
1041 | < | |
1042 | typename tag<Geometry>::type, | |
1043 | Geometry, | |
1044 | Reverse, | |
1045 | DimensionVector | |
92f5a8d4 TL |
1046 | >::apply(geometry, robust_policy, sections, |
1047 | envelope_strategy, expand_strategy, | |
1048 | ring_id, max_count); | |
7c673cae | 1049 | |
92f5a8d4 | 1050 | detail::sectionalize::enlarge_sections(sections, envelope_strategy); |
7c673cae FG |
1051 | } |
1052 | ||
1053 | ||
b32b8144 FG |
1054 | template |
1055 | < | |
1056 | bool Reverse, | |
1057 | typename DimensionVector, | |
1058 | typename Geometry, | |
1059 | typename Sections, | |
1060 | typename RobustPolicy | |
1061 | > | |
1062 | inline void sectionalize(Geometry const& geometry, | |
1063 | RobustPolicy const& robust_policy, | |
1064 | Sections& sections, | |
1065 | int source_index = 0, | |
1066 | std::size_t max_count = 10) | |
1067 | { | |
1068 | typedef typename strategy::envelope::services::default_strategy | |
1069 | < | |
92f5a8d4 | 1070 | typename tag<Geometry>::type, |
b32b8144 FG |
1071 | typename cs_tag<Geometry>::type |
1072 | >::type envelope_strategy_type; | |
1073 | ||
92f5a8d4 TL |
1074 | typedef typename strategy::expand::services::default_strategy |
1075 | < | |
20effc67 | 1076 | std::conditional_t |
92f5a8d4 | 1077 | < |
20effc67 | 1078 | std::is_same<typename tag<Geometry>::type, box_tag>::value, |
92f5a8d4 TL |
1079 | box_tag, |
1080 | segment_tag | |
20effc67 | 1081 | >, |
92f5a8d4 TL |
1082 | typename cs_tag<Geometry>::type |
1083 | >::type expand_strategy_type; | |
1084 | ||
b32b8144 FG |
1085 | boost::geometry::sectionalize |
1086 | < | |
1087 | Reverse, DimensionVector | |
1088 | >(geometry, robust_policy, sections, | |
1089 | envelope_strategy_type(), | |
92f5a8d4 | 1090 | expand_strategy_type(), |
b32b8144 FG |
1091 | source_index, max_count); |
1092 | } | |
1093 | ||
7c673cae FG |
1094 | }} // namespace boost::geometry |
1095 | ||
1096 | ||
1097 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP |