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