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