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
8 // This file was modified by Oracle on 2013, 2014, 2015, 2017.
9 // Modifications copyright (c) 2013-2017 Oracle and/or its affiliates.
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>
32 #include <boost/type_traits/is_same.hpp>
33 #include <boost/type_traits/is_fundamental.hpp>
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>
59 #include <boost/geometry/strategies/envelope.hpp>
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
sectionboost::geometry::section102 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
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.
143 template
144 <
145 typename Point,
146 typename DimensionVector,
147 std::size_t Index,
148 std::size_t Count,
149 typename CastedCSTag = typename tag_cast
150 <
151 typename cs_tag<Point>::type,
152 spherical_tag
153 >::type
154 >
155 struct get_direction_loop
156 {
157 typedef typename boost::mpl::at_c<DimensionVector, Index>::type dimension;
158
159 template <typename Segment>
applyboost::geometry::detail::sectionalize::get_direction_loop160 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 <
174 Point,
175 DimensionVector,
176 Index + 1,
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>
applyboost::geometry::detail::sectionalize::get_direction_loop194 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
216 >::apply(seg, directions);
217 }
218 };
219
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>
228 {
229 template <typename Segment>
applyboost::geometry::detail::sectionalize::get_direction_loop230 static inline void apply(Segment const&, int [Count])
231 {}
232 };
233
234
235 //! Copy one static array to another
236 template <typename T, std::size_t Index, std::size_t Count>
237 struct copy_loop
238 {
applyboost::geometry::detail::sectionalize::copy_loop239 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 {
applyboost::geometry::detail::sectionalize::copy_loop249 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 {
applyboost::geometry::detail::sectionalize::compare_loop257 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 {
applyboost::geometry::detail::sectionalize::compare_loop271 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>
applyboost::geometry::detail::sectionalize::check_duplicate_loop283 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>
applyboost::geometry::detail::sectionalize::check_duplicate_loop306 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 {
applyboost::geometry::detail::sectionalize::assign_loop316 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 {
applyboost::geometry::detail::sectionalize::assign_loop326 static inline void apply(T [Count], T const)
327 {
328 }
329 };
330
331 template <typename CSTag>
332 struct box_first_in_section
333 {
334 template <typename Box, typename Point, typename Strategy>
applyboost::geometry::detail::sectionalize::box_first_in_section335 static inline void apply(Box & box, Point const& prev, Point const& curr,
336 Strategy const& strategy)
337 {
338 geometry::model::referring_segment<Point const> seg(prev, curr);
339 geometry::envelope(seg, box, strategy);
340 }
341 };
342
343 template <>
344 struct box_first_in_section<cartesian_tag>
345 {
346 template <typename Box, typename Point, typename Strategy>
applyboost::geometry::detail::sectionalize::box_first_in_section347 static inline void apply(Box & box, Point const& prev, Point const& curr,
348 Strategy const& )
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 {
358 template <typename Box, typename Point, typename Strategy>
applyboost::geometry::detail::sectionalize::box_next_in_section359 static inline void apply(Box & box, Point const& prev, Point const& curr,
360 Strategy const& strategy)
361 {
362 geometry::model::referring_segment<Point const> seg(prev, curr);
363 geometry::expand(box, seg, strategy);
364 }
365 };
366
367 template <>
368 struct box_next_in_section<cartesian_tag>
369 {
370 template <typename Box, typename Point, typename Strategy>
applyboost::geometry::detail::sectionalize::box_next_in_section371 static inline void apply(Box & box, Point const& , Point const& curr,
372 Strategy const& )
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 >
applyboost::geometry::detail::sectionalize::sectionalize_part395 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)
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 >
applyboost::geometry::detail::sectionalize::sectionalize_part418 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)
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 <
469 Point, DimensionVector, 0, dimension_count
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>
539 ::apply(section.bounding_box, previous_robust_point, current_robust_point, strategy);
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>
546 ::apply(section.bounding_box, previous_robust_point, current_robust_point, strategy);
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,
591 typename Sections,
592 typename EnvelopeStrategy
593 >
applyboost::geometry::detail::sectionalize::sectionalize_range594 static inline void apply(Range const& range,
595 RobustPolicy const& robust_policy,
596 Sections& sections,
597 EnvelopeStrategy const& strategy,
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),
626 robust_policy, strategy, ring_id, max_count);
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,
641 typename Sections,
642 typename EnvelopeStrategy
643 >
applyboost::geometry::detail::sectionalize::sectionalize_polygon644 static inline void apply(Polygon const& poly,
645 RobustPolicy const& robust_policy,
646 Sections& sections,
647 EnvelopeStrategy const& strategy,
648 ring_identifier ring_id,
649 std::size_t max_count)
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;
659 per_range::apply(exterior_ring(poly), robust_policy, sections, strategy, ring_id, max_count);
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 {
667 per_range::apply(*it, robust_policy, sections, strategy, ring_id, max_count);
668 }
669 }
670 };
671
672 template <typename DimensionVector>
673 struct sectionalize_box
674 {
675 template
676 <
677 typename Box,
678 typename RobustPolicy,
679 typename Sections,
680 typename EnvelopeStrategy
681 >
applyboost::geometry::detail::sectionalize::sectionalize_box682 static inline void apply(Box const& box,
683 RobustPolicy const& robust_policy,
684 Sections& sections,
685 EnvelopeStrategy const& ,
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
710 // NOTE: Use cartesian envelope strategy in all coordinate systems
711 // because edges of a box are not geodesic segments
712 sectionalize_range
713 <
714 closed, false,
715 point_type,
716 DimensionVector
717 >::apply(points, robust_policy, sections,
718 strategy::envelope::cartesian_segment<>(),
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,
730 typename Sections,
731 typename EnvelopeStrategy
732 >
applyboost::geometry::detail::sectionalize::sectionalize_multi733 static inline void apply(MultiGeometry const& multi,
734 RobustPolicy const& robust_policy,
735 Sections& sections,
736 EnvelopeStrategy const& strategy,
737 ring_identifier ring_id,
738 std::size_t max_count)
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 {
746 Policy::apply(*it, robust_policy, sections, strategy, ring_id, max_count);
747 }
748 }
749 };
750
751 template <typename Sections>
enlarge_sections(Sections & 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,
918 typename RobustPolicy,
919 typename EnvelopeStrategy
920 >
sectionalize(Geometry const & geometry,RobustPolicy const & robust_policy,Sections & sections,EnvelopeStrategy const & strategy,int source_index=0,std::size_t max_count=10)921 inline void sectionalize(Geometry const& geometry,
922 RobustPolicy const& robust_policy,
923 Sections& sections,
924 EnvelopeStrategy const& strategy,
925 int source_index = 0,
926 std::size_t max_count = 10)
927 {
928 BOOST_STATIC_ASSERT((! boost::is_fundamental<EnvelopeStrategy>::value));
929
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
963 >::apply(geometry, robust_policy, sections, strategy, ring_id, max_count);
964
965 detail::sectionalize::enlarge_sections(sections);
966 }
967
968
969 template
970 <
971 bool Reverse,
972 typename DimensionVector,
973 typename Geometry,
974 typename Sections,
975 typename RobustPolicy
976 >
sectionalize(Geometry const & geometry,RobustPolicy const & robust_policy,Sections & sections,int source_index=0,std::size_t max_count=10)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
996 }} // namespace boost::geometry
997
998
999 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
1000