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.
9 // Modifications copyright (c) 2013-2015 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
33 #include <boost/geometry/algorithms/assign.hpp>
34 #include <boost/geometry/algorithms/expand.hpp>
35
36 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
37 #include <boost/geometry/algorithms/detail/recalculate.hpp>
38 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
39 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
40
41 #include <boost/geometry/core/access.hpp>
42 #include <boost/geometry/core/closure.hpp>
43 #include <boost/geometry/core/exterior_ring.hpp>
44 #include <boost/geometry/core/point_order.hpp>
45 #include <boost/geometry/core/tags.hpp>
46
47 #include <boost/geometry/geometries/concepts/check.hpp>
48 #include <boost/geometry/util/math.hpp>
49 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
50 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
51 #include <boost/geometry/views/closeable_view.hpp>
52 #include <boost/geometry/views/reversible_view.hpp>
53 #include <boost/geometry/geometries/segment.hpp>
54
55 namespace boost { namespace geometry
56 {
57
58
59 /*!
60 \brief Structure containing section information
61 \details Section information consists of a bounding box, direction
62 information (if it is increasing or decreasing, per dimension),
63 index information (begin-end, ring, multi) and the number of
64 segments in this section
65
66 \tparam Box box-type
67 \tparam DimensionCount number of dimensions for this section
68 \ingroup sectionalize
69 */
70 template
71 <
72 typename Box,
73 std::size_t DimensionCount
74 >
75 struct section
76 {
77 typedef Box box_type;
78 static std::size_t const dimension_count = DimensionCount;
79
80 int directions[DimensionCount];
81 ring_identifier ring_id;
82 Box bounding_box;
83
84 // NOTE: size_type could be passed as template parameter
85 // NOTE: these probably also could be of type std::size_t
86 signed_size_type begin_index;
87 signed_size_type end_index;
88 std::size_t count;
89 std::size_t range_count;
90 bool duplicate;
91 signed_size_type non_duplicate_index;
92
93 bool is_non_duplicate_first;
94 bool is_non_duplicate_last;
95
sectionboost::geometry::section96 inline section()
97 : begin_index(-1)
98 , end_index(-1)
99 , count(0)
100 , range_count(0)
101 , duplicate(false)
102 , non_duplicate_index(-1)
103 , is_non_duplicate_first(false)
104 , is_non_duplicate_last(false)
105 {
106 assign_inverse(bounding_box);
107 for (std::size_t i = 0; i < DimensionCount; i++)
108 {
109 directions[i] = 0;
110 }
111 }
112 };
113
114
115 /*!
116 \brief Structure containing a collection of sections
117 \note Derived from a vector, proves to be faster than of deque
118 \note vector might be templated in the future
119 \ingroup sectionalize
120 */
121 template <typename Box, std::size_t DimensionCount>
122 struct sections : std::vector<section<Box, DimensionCount> >
123 {
124 typedef Box box_type;
125 static std::size_t const value = DimensionCount;
126 };
127
128
129 #ifndef DOXYGEN_NO_DETAIL
130 namespace detail { namespace sectionalize
131 {
132
133 template
134 <
135 typename DimensionVector,
136 std::size_t Index,
137 std::size_t Count
138 >
139 struct get_direction_loop
140 {
141 typedef typename boost::mpl::at_c<DimensionVector, Index>::type dimension;
142
143 template <typename Segment>
applyboost::geometry::detail::sectionalize::get_direction_loop144 static inline void apply(Segment const& seg,
145 int directions[Count])
146 {
147 typedef typename coordinate_type<Segment>::type coordinate_type;
148
149 coordinate_type const diff =
150 geometry::get<1, dimension::value>(seg)
151 - geometry::get<0, dimension::value>(seg);
152
153 coordinate_type zero = coordinate_type();
154 directions[Index] = diff > zero ? 1 : diff < zero ? -1 : 0;
155
156 get_direction_loop
157 <
158 DimensionVector,
159 Index + 1,
160 Count
161 >::apply(seg, directions);
162 }
163 };
164
165 template <typename DimensionVector, std::size_t Count>
166 struct get_direction_loop<DimensionVector, Count, Count>
167 {
168 template <typename Segment>
applyboost::geometry::detail::sectionalize::get_direction_loop169 static inline void apply(Segment const&, int [Count])
170 {}
171 };
172
173 //! Copy one static array to another
174 template <typename T, std::size_t Index, std::size_t Count>
175 struct copy_loop
176 {
applyboost::geometry::detail::sectionalize::copy_loop177 static inline void apply(T const source[Count], T target[Count])
178 {
179 target[Index] = source[Index];
180 copy_loop<T, Index + 1, Count>::apply(source, target);
181 }
182 };
183
184 template <typename T, std::size_t Count>
185 struct copy_loop<T, Count, Count>
186 {
applyboost::geometry::detail::sectionalize::copy_loop187 static inline void apply(T const [Count], T [Count])
188 {}
189 };
190
191 //! Compare two static arrays
192 template <typename T, std::size_t Index, std::size_t Count>
193 struct compare_loop
194 {
applyboost::geometry::detail::sectionalize::compare_loop195 static inline bool apply(T const array1[Count], T const array2[Count])
196 {
197 return array1[Index] != array2[Index]
198 ? false
199 : compare_loop
200 <
201 T, Index + 1, Count
202 >::apply(array1, array2);
203 }
204 };
205
206 template <typename T, std::size_t Count>
207 struct compare_loop<T, Count, Count>
208 {
applyboost::geometry::detail::sectionalize::compare_loop209 static inline bool apply(T const [Count], T const [Count])
210 {
211
212 return true;
213 }
214 };
215
216
217 template <std::size_t Dimension, std::size_t DimensionCount>
218 struct check_duplicate_loop
219 {
220 template <typename Segment>
applyboost::geometry::detail::sectionalize::check_duplicate_loop221 static inline bool apply(Segment const& seg)
222 {
223 if (! geometry::math::equals
224 (
225 geometry::get<0, Dimension>(seg),
226 geometry::get<1, Dimension>(seg)
227 )
228 )
229 {
230 return false;
231 }
232
233 return check_duplicate_loop
234 <
235 Dimension + 1, DimensionCount
236 >::apply(seg);
237 }
238 };
239
240 template <std::size_t DimensionCount>
241 struct check_duplicate_loop<DimensionCount, DimensionCount>
242 {
243 template <typename Segment>
applyboost::geometry::detail::sectionalize::check_duplicate_loop244 static inline bool apply(Segment const&)
245 {
246 return true;
247 }
248 };
249
250 //! Assign a value to a static array
251 template <typename T, std::size_t Index, std::size_t Count>
252 struct assign_loop
253 {
applyboost::geometry::detail::sectionalize::assign_loop254 static inline void apply(T dims[Count], T const value)
255 {
256 dims[Index] = value;
257 assign_loop<T, Index + 1, Count>::apply(dims, value);
258 }
259 };
260
261 template <typename T, std::size_t Count>
262 struct assign_loop<T, Count, Count>
263 {
applyboost::geometry::detail::sectionalize::assign_loop264 static inline void apply(T [Count], T const)
265 {
266 }
267 };
268
269 /// @brief Helper class to create sections of a part of a range, on the fly
270 template
271 <
272 typename Point,
273 typename DimensionVector
274 >
275 struct sectionalize_part
276 {
277 static const std::size_t dimension_count
278 = boost::mpl::size<DimensionVector>::value;
279
280 template
281 <
282 typename Iterator,
283 typename RobustPolicy,
284 typename Sections
285 >
applyboost::geometry::detail::sectionalize::sectionalize_part286 static inline void apply(Sections& sections,
287 Iterator begin, Iterator end,
288 RobustPolicy const& robust_policy,
289 ring_identifier ring_id,
290 std::size_t max_count)
291 {
292 boost::ignore_unused_variable_warning(robust_policy);
293
294 typedef typename boost::range_value<Sections>::type section_type;
295 BOOST_STATIC_ASSERT
296 (
297 (static_cast<std::size_t>(section_type::dimension_count)
298 == static_cast<std::size_t>(boost::mpl::size<DimensionVector>::value))
299 );
300
301 typedef typename geometry::robust_point_type
302 <
303 Point,
304 RobustPolicy
305 >::type robust_point_type;
306
307 std::size_t const count = std::distance(begin, end);
308 if (count == 0)
309 {
310 return;
311 }
312
313 signed_size_type index = 0;
314 signed_size_type ndi = 0; // non duplicate index
315 section_type section;
316
317 bool mark_first_non_duplicated = true;
318 std::size_t last_non_duplicate_index = sections.size();
319
320 Iterator it = begin;
321 robust_point_type previous_robust_point;
322 geometry::recalculate(previous_robust_point, *it, robust_policy);
323
324 for(Iterator previous = it++;
325 it != end;
326 ++previous, ++it, index++)
327 {
328 robust_point_type current_robust_point;
329 geometry::recalculate(current_robust_point, *it, robust_policy);
330 model::referring_segment<robust_point_type> robust_segment(
331 previous_robust_point, current_robust_point);
332
333 int direction_classes[dimension_count] = {0};
334 get_direction_loop
335 <
336 DimensionVector, 0, dimension_count
337 >::apply(robust_segment, direction_classes);
338
339 // if "dir" == 0 for all point-dimensions, it is duplicate.
340 // Those sections might be omitted, if wished, lateron
341 bool duplicate = false;
342
343 if (direction_classes[0] == 0)
344 {
345 // Recheck because ALL dimensions should be checked,
346 // not only first one.
347 // (dimension_count might be < dimension<P>::value)
348 if (check_duplicate_loop
349 <
350 0, geometry::dimension<Point>::type::value
351 >::apply(robust_segment)
352 )
353 {
354 duplicate = true;
355
356 // Change direction-info to force new section
357 // Note that wo consecutive duplicate segments will generate
358 // only one duplicate-section.
359 // Actual value is not important as long as it is not -1,0,1
360 assign_loop
361 <
362 int, 0, dimension_count
363 >::apply(direction_classes, -99);
364 }
365 }
366
367 if (section.count > 0
368 && (! compare_loop
369 <
370 int, 0, dimension_count
371 >::apply(direction_classes, section.directions)
372 || section.count > max_count)
373 )
374 {
375 if (! section.duplicate)
376 {
377 last_non_duplicate_index = sections.size();
378 }
379
380 sections.push_back(section);
381 section = section_type();
382 }
383
384 if (section.count == 0)
385 {
386 section.begin_index = index;
387 section.ring_id = ring_id;
388 section.duplicate = duplicate;
389 section.non_duplicate_index = ndi;
390 section.range_count = count;
391
392 if (mark_first_non_duplicated && ! duplicate)
393 {
394 section.is_non_duplicate_first = true;
395 mark_first_non_duplicated = false;
396 }
397
398 copy_loop
399 <
400 int, 0, dimension_count
401 >::apply(direction_classes, section.directions);
402
403 geometry::expand(section.bounding_box, previous_robust_point);
404 }
405
406 geometry::expand(section.bounding_box, current_robust_point);
407 section.end_index = index + 1;
408 section.count++;
409 if (! duplicate)
410 {
411 ndi++;
412 }
413 previous_robust_point = current_robust_point;
414 }
415
416 // Add last section if applicable
417 if (section.count > 0)
418 {
419 if (! section.duplicate)
420 {
421 last_non_duplicate_index = sections.size();
422 }
423
424 sections.push_back(section);
425 }
426
427 if (last_non_duplicate_index < sections.size()
428 && ! sections[last_non_duplicate_index].duplicate)
429 {
430 sections[last_non_duplicate_index].is_non_duplicate_last = true;
431 }
432 }
433 };
434
435
436 template
437 <
438 closure_selector Closure,
439 bool Reverse,
440 typename Point,
441 typename DimensionVector
442 >
443 struct sectionalize_range
444 {
445 template
446 <
447 typename Range,
448 typename RobustPolicy,
449 typename Sections
450 >
applyboost::geometry::detail::sectionalize::sectionalize_range451 static inline void apply(Range const& range,
452 RobustPolicy const& robust_policy,
453 Sections& sections,
454 ring_identifier ring_id,
455 std::size_t max_count)
456 {
457 typedef typename closeable_view<Range const, Closure>::type cview_type;
458 typedef typename reversible_view
459 <
460 cview_type const,
461 Reverse ? iterate_reverse : iterate_forward
462 >::type view_type;
463
464 cview_type cview(range);
465 view_type view(cview);
466
467 std::size_t const n = boost::size(view);
468 if (n == 0)
469 {
470 // Zero points, no section
471 return;
472 }
473
474 if (n == 1)
475 {
476 // Line with one point ==> no sections
477 return;
478 }
479
480 sectionalize_part<Point, DimensionVector>::apply(sections,
481 boost::begin(view), boost::end(view),
482 robust_policy, ring_id, max_count);
483 }
484 };
485
486 template
487 <
488 bool Reverse,
489 typename DimensionVector
490 >
491 struct sectionalize_polygon
492 {
493 template
494 <
495 typename Polygon,
496 typename RobustPolicy,
497 typename Sections
498 >
applyboost::geometry::detail::sectionalize::sectionalize_polygon499 static inline void apply(Polygon const& poly,
500 RobustPolicy const& robust_policy,
501 Sections& sections,
502 ring_identifier ring_id, std::size_t max_count)
503 {
504 typedef typename point_type<Polygon>::type point_type;
505 typedef sectionalize_range
506 <
507 closure<Polygon>::value, Reverse,
508 point_type, DimensionVector
509 > per_range;
510
511 ring_id.ring_index = -1;
512 per_range::apply(exterior_ring(poly), robust_policy, sections, ring_id, max_count);
513
514 ring_id.ring_index++;
515 typename interior_return_type<Polygon const>::type
516 rings = interior_rings(poly);
517 for (typename detail::interior_iterator<Polygon const>::type
518 it = boost::begin(rings); it != boost::end(rings); ++it, ++ring_id.ring_index)
519 {
520 per_range::apply(*it, robust_policy, sections, ring_id, max_count);
521 }
522 }
523 };
524
525 template <typename DimensionVector>
526 struct sectionalize_box
527 {
528 template
529 <
530 typename Box,
531 typename RobustPolicy,
532 typename Sections
533 >
applyboost::geometry::detail::sectionalize::sectionalize_box534 static inline void apply(Box const& box,
535 RobustPolicy const& robust_policy,
536 Sections& sections,
537 ring_identifier const& ring_id, std::size_t max_count)
538 {
539 typedef typename point_type<Box>::type point_type;
540
541 assert_dimension<Box, 2>();
542
543 // Add all four sides of the 2D-box as separate section.
544 // Easiest is to convert it to a polygon.
545 // However, we don't have the polygon type
546 // (or polygon would be a helper-type).
547 // Therefore we mimic a linestring/std::vector of 5 points
548
549 // TODO: might be replaced by assign_box_corners_oriented
550 // or just "convert"
551 point_type ll, lr, ul, ur;
552 geometry::detail::assign_box_corners(box, ll, lr, ul, ur);
553
554 std::vector<point_type> points;
555 points.push_back(ll);
556 points.push_back(ul);
557 points.push_back(ur);
558 points.push_back(lr);
559 points.push_back(ll);
560
561 sectionalize_range
562 <
563 closed, false,
564 point_type,
565 DimensionVector
566 >::apply(points, robust_policy, sections,
567 ring_id, max_count);
568 }
569 };
570
571 template <typename DimensionVector, typename Policy>
572 struct sectionalize_multi
573 {
574 template
575 <
576 typename MultiGeometry,
577 typename RobustPolicy,
578 typename Sections
579 >
applyboost::geometry::detail::sectionalize::sectionalize_multi580 static inline void apply(MultiGeometry const& multi,
581 RobustPolicy const& robust_policy,
582 Sections& sections, ring_identifier ring_id, std::size_t max_count)
583 {
584 ring_id.multi_index = 0;
585 for (typename boost::range_iterator<MultiGeometry const>::type
586 it = boost::begin(multi);
587 it != boost::end(multi);
588 ++it, ++ring_id.multi_index)
589 {
590 Policy::apply(*it, robust_policy, sections, ring_id, max_count);
591 }
592 }
593 };
594
595 template <typename Sections>
enlarge_sections(Sections & sections)596 inline void enlarge_sections(Sections& sections)
597 {
598 // Robustness issue. Increase sections a tiny bit such that all points are really within (and not on border)
599 // Reason: turns might, rarely, be missed otherwise (case: "buffer_mp1")
600 // Drawback: not really, range is now completely inside the section. Section is a tiny bit too large,
601 // which might cause (a small number) of more comparisons
602 // TODO: make dimension-agnostic
603 for (typename boost::range_iterator<Sections>::type it = boost::begin(sections);
604 it != boost::end(sections);
605 ++it)
606 {
607 typedef typename boost::range_value<Sections>::type section_type;
608 typedef typename section_type::box_type box_type;
609 typedef typename geometry::coordinate_type<box_type>::type coordinate_type;
610 coordinate_type const reps = math::relaxed_epsilon(10.0);
611 geometry::set<0, 0>(it->bounding_box, geometry::get<0, 0>(it->bounding_box) - reps);
612 geometry::set<0, 1>(it->bounding_box, geometry::get<0, 1>(it->bounding_box) - reps);
613 geometry::set<1, 0>(it->bounding_box, geometry::get<1, 0>(it->bounding_box) + reps);
614 geometry::set<1, 1>(it->bounding_box, geometry::get<1, 1>(it->bounding_box) + reps);
615 }
616 }
617
618
619 }} // namespace detail::sectionalize
620 #endif // DOXYGEN_NO_DETAIL
621
622
623 #ifndef DOXYGEN_NO_DISPATCH
624 namespace dispatch
625 {
626
627 template
628 <
629 typename Tag,
630 typename Geometry,
631 bool Reverse,
632 typename DimensionVector
633 >
634 struct sectionalize
635 {
636 BOOST_MPL_ASSERT_MSG
637 (
638 false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
639 , (types<Geometry>)
640 );
641 };
642
643 template
644 <
645 typename Box,
646 bool Reverse,
647 typename DimensionVector
648 >
649 struct sectionalize<box_tag, Box, Reverse, DimensionVector>
650 : detail::sectionalize::sectionalize_box<DimensionVector>
651 {};
652
653 template
654 <
655 typename LineString,
656 typename DimensionVector
657 >
658 struct sectionalize
659 <
660 linestring_tag,
661 LineString,
662 false,
663 DimensionVector
664 >
665 : detail::sectionalize::sectionalize_range
666 <
667 closed, false,
668 typename point_type<LineString>::type,
669 DimensionVector
670 >
671 {};
672
673 template
674 <
675 typename Ring,
676 bool Reverse,
677 typename DimensionVector
678 >
679 struct sectionalize<ring_tag, Ring, Reverse, DimensionVector>
680 : detail::sectionalize::sectionalize_range
681 <
682 geometry::closure<Ring>::value, Reverse,
683 typename point_type<Ring>::type,
684 DimensionVector
685 >
686 {};
687
688 template
689 <
690 typename Polygon,
691 bool Reverse,
692 typename DimensionVector
693 >
694 struct sectionalize<polygon_tag, Polygon, Reverse, DimensionVector>
695 : detail::sectionalize::sectionalize_polygon
696 <
697 Reverse, DimensionVector
698 >
699 {};
700
701 template
702 <
703 typename MultiPolygon,
704 bool Reverse,
705 typename DimensionVector
706 >
707 struct sectionalize<multi_polygon_tag, MultiPolygon, Reverse, DimensionVector>
708 : detail::sectionalize::sectionalize_multi
709 <
710 DimensionVector,
711 detail::sectionalize::sectionalize_polygon
712 <
713 Reverse,
714 DimensionVector
715 >
716 >
717
718 {};
719
720 template
721 <
722 typename MultiLinestring,
723 bool Reverse,
724 typename DimensionVector
725 >
726 struct sectionalize<multi_linestring_tag, MultiLinestring, Reverse, DimensionVector>
727 : detail::sectionalize::sectionalize_multi
728 <
729 DimensionVector,
730 detail::sectionalize::sectionalize_range
731 <
732 closed, false,
733 typename point_type<MultiLinestring>::type,
734 DimensionVector
735 >
736 >
737
738 {};
739
740 } // namespace dispatch
741 #endif
742
743
744 /*!
745 \brief Split a geometry into monotonic sections
746 \ingroup sectionalize
747 \tparam Geometry type of geometry to check
748 \tparam Sections type of sections to create
749 \param geometry geometry to create sections from
750 \param robust_policy policy to handle robustness issues
751 \param sections structure with sections
752 \param source_index index to assign to the ring_identifiers
753 \param max_count maximal number of points per section
754 (defaults to 10, this seems to give the fastest results)
755
756 */
757 template
758 <
759 bool Reverse,
760 typename DimensionVector,
761 typename Geometry,
762 typename Sections,
763 typename RobustPolicy
764 >
sectionalize(Geometry const & geometry,RobustPolicy const & robust_policy,Sections & sections,int source_index=0,std::size_t max_count=10)765 inline void sectionalize(Geometry const& geometry,
766 RobustPolicy const& robust_policy,
767 Sections& sections,
768 int source_index = 0,
769 std::size_t max_count = 10)
770 {
771 concept::check<Geometry const>();
772
773 typedef typename boost::range_value<Sections>::type section_type;
774
775 // Compiletime check for point type of section boxes
776 // and point type related to robust policy
777 typedef typename geometry::coordinate_type
778 <
779 typename section_type::box_type
780 >::type ctype1;
781 typedef typename geometry::coordinate_type
782 <
783 typename geometry::robust_point_type
784 <
785 typename geometry::point_type<Geometry>::type,
786 RobustPolicy
787 >::type
788 >::type ctype2;
789
790 BOOST_MPL_ASSERT((boost::is_same<ctype1, ctype2>));
791
792
793 sections.clear();
794
795 ring_identifier ring_id;
796 ring_id.source_index = source_index;
797
798 dispatch::sectionalize
799 <
800 typename tag<Geometry>::type,
801 Geometry,
802 Reverse,
803 DimensionVector
804 >::apply(geometry, robust_policy, sections, ring_id, max_count);
805 }
806
807
808 }} // namespace boost::geometry
809
810
811 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
812