boost/geometry/algorithms/detail/sections/sectionalize.hpp

   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, 2018.
   9 // Modifications copyright (c) 2013-2018 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/core/ignore_unused.hpp>
  29 #include <boost/mpl/assert.hpp>
  30 #include <boost/mpl/vector_c.hpp>
  31 #include <boost/range.hpp>
  32 #include <boost/static_assert.hpp>
  33 #include <boost/type_traits/is_same.hpp>
  34 #include <boost/type_traits/is_fundamental.hpp>
  35
  36 #include <boost/geometry/algorithms/assign.hpp>
  37 #include <boost/geometry/algorithms/envelope.hpp>
  38 #include <boost/geometry/algorithms/expand.hpp>
  39
  40 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  41 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  42 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  43 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
  44
  45 #include <boost/geometry/core/access.hpp>
  46 #include <boost/geometry/core/closure.hpp>
  47 #include <boost/geometry/core/exterior_ring.hpp>
  48 #include <boost/geometry/core/point_order.hpp>
  49 #include <boost/geometry/core/tags.hpp>
  50
  51 #include <boost/geometry/geometries/concepts/check.hpp>
  52 #include <boost/geometry/util/math.hpp>
  53 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
  54 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
  55 #include <boost/geometry/views/closeable_view.hpp>
  56 #include <boost/geometry/views/reversible_view.hpp>
  57 #include <boost/geometry/geometries/segment.hpp>
  58
  59 #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
  60 #include <boost/geometry/strategies/envelope.hpp>
  61 #include <boost/geometry/strategies/expand.hpp>
  62
  63 namespace boost { namespace geometry
  64 {
  65
  66
  67 /*!
  68     \brief Structure containing section information
  69     \details Section information consists of a bounding box, direction
  70         information (if it is increasing or decreasing, per dimension),
  71         index information (begin-end, ring, multi) and the number of
  72         segments in this section
  73
  74     \tparam Box box-type
  75     \tparam DimensionCount number of dimensions for this section
  76     \ingroup sectionalize
  77  */
  78 template
  79 <
  80     typename Box,
  81     std::size_t DimensionCount
  82 >
  83 struct section
  84 {
  85     typedef Box box_type;
  86     static std::size_t const dimension_count = DimensionCount;
  87
  88     int directions[DimensionCount];
  89     ring_identifier ring_id;
  90     Box bounding_box;
  91
  92     // NOTE: size_type could be passed as template parameter
  93     // NOTE: these probably also could be of type std::size_t
  94     signed_size_type begin_index;
  95     signed_size_type end_index;
  96     std::size_t count;
  97     std::size_t range_count;
  98     bool duplicate;
  99     signed_size_type non_duplicate_index;
 100
 101     bool is_non_duplicate_first;
 102     bool is_non_duplicate_last;
 103
 104     inline section()
 105         : begin_index(-1)
 106         , end_index(-1)
 107         , count(0)
 108         , range_count(0)
 109         , duplicate(false)
 110         , non_duplicate_index(-1)
 111         , is_non_duplicate_first(false)
 112         , is_non_duplicate_last(false)
 113     {
 114         assign_inverse(bounding_box);
 115         for (std::size_t i = 0; i < DimensionCount; i++)
 116         {
 117             directions[i] = 0;
 118         }
 119     }
 120 };
 121
 122
 123 /*!
 124     \brief Structure containing a collection of sections
 125     \note Derived from a vector, proves to be faster than of deque
 126     \note vector might be templated in the future
 127     \ingroup sectionalize
 128  */
 129 template <typename Box, std::size_t DimensionCount>
 130 struct sections : std::vector<section<Box, DimensionCount> >
 131 {
 132     typedef Box box_type;
 133     static std::size_t const value = DimensionCount;
 134 };
 135
 136
 137 #ifndef DOXYGEN_NO_DETAIL
 138 namespace detail { namespace sectionalize
 139 {
 140
 141 // NOTE: This utility will NOT work for latitudes, dimension 1 in spherical
 142 // and geographic coordinate system because in these coordinate systems
 143 // e.g. a segment on northern hemisphere may go towards greater latitude
 144 // and then towards lesser latitude.
 145 template
 146 <
 147     typename Point,
 148     typename DimensionVector,
 149     std::size_t Index,
 150     std::size_t Count,
 151     typename CastedCSTag = typename tag_cast
 152                             <
 153                                 typename cs_tag<Point>::type,
 154                                 spherical_tag
 155                             >::type
 156 >
 157 struct get_direction_loop
 158 {
 159     typedef typename boost::mpl::at_c<DimensionVector, Index>::type dimension;
 160
 161     template <typename Segment>
 162     static inline void apply(Segment const& seg,
 163                 int directions[Count])
 164     {
 165         typedef typename coordinate_type<Segment>::type coordinate_type;
 166
 167         coordinate_type const c0 = geometry::get<0, dimension::value>(seg);
 168         coordinate_type const c1 = geometry::get<1, dimension::value>(seg);
 169
 170         directions[Index] = c1 > c0 ? 1 : c1 < c0 ? -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>
 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
 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>
 230     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 {
 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 {
 334     template <typename Box, typename Point, typename EnvelopeStrategy>
 335     static inline void apply(Box & box, Point const& prev, Point const& curr,
 336                              EnvelopeStrategy 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 ExpandStrategy>
 347     static inline void apply(Box & box, Point const& prev, Point const& curr,
 348                              ExpandStrategy 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>
 359     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>
 371     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     >
 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)
 400     {
 401         typedef typename strategy::envelope::services::default_strategy
 402             <
 403                 segment_tag,
 404                 typename cs_tag<typename Sections::box_type>::type
 405             >::type envelope_strategy_type;
 406
 407         typedef typename strategy::expand::services::default_strategy
 408             <
 409                 segment_tag,
 410                 typename cs_tag<typename Sections::box_type>::type
 411             >::type expand_strategy_type;
 412
 413         apply(sections, begin, end,
 414               robust_policy,
 415               envelope_strategy_type(),
 416               expand_strategy_type(),
 417               ring_id, max_count);
 418     }
 419
 420     template
 421     <
 422         typename Iterator,
 423         typename RobustPolicy,
 424         typename Sections,
 425         typename EnvelopeStrategy,
 426         typename ExpandStrategy
 427     >
 428     static inline void apply(Sections& sections,
 429                              Iterator begin, Iterator end,
 430                              RobustPolicy const& robust_policy,
 431                              EnvelopeStrategy const& envelope_strategy,
 432                              ExpandStrategy const& expand_strategy,
 433                              ring_identifier ring_id,
 434                              std::size_t max_count)
 435     {
 436         boost::ignore_unused(robust_policy);
 437
 438         typedef typename boost::range_value<Sections>::type section_type;
 439         BOOST_STATIC_ASSERT
 440             (
 441                 (static_cast<std::size_t>(section_type::dimension_count)
 442                  == static_cast<std::size_t>(boost::mpl::size<DimensionVector>::value))
 443             );
 444
 445         typedef typename geometry::robust_point_type
 446         <
 447             Point,
 448             RobustPolicy
 449         >::type robust_point_type;
 450
 451         std::size_t const count = std::distance(begin, end);
 452         if (count == 0)
 453         {
 454             return;
 455         }
 456
 457         signed_size_type index = 0;
 458         signed_size_type ndi = 0; // non duplicate index
 459         section_type section;
 460
 461         bool mark_first_non_duplicated = true;
 462         std::size_t last_non_duplicate_index = sections.size();
 463
 464         Iterator it = begin;
 465         robust_point_type previous_robust_point;
 466         geometry::recalculate(previous_robust_point, *it, robust_policy);
 467
 468         for(Iterator previous = it++;
 469             it != end;
 470             ++previous, ++it, index++)
 471         {
 472             robust_point_type current_robust_point;
 473             geometry::recalculate(current_robust_point, *it, robust_policy);
 474             model::referring_segment<robust_point_type> robust_segment(
 475                     previous_robust_point, current_robust_point);
 476
 477             int direction_classes[dimension_count] = {0};
 478             get_direction_loop
 479             <
 480                 Point, DimensionVector, 0, dimension_count
 481             >::apply(robust_segment, direction_classes);
 482
 483             // if "dir" == 0 for all point-dimensions, it is duplicate.
 484             // Those sections might be omitted, if wished, lateron
 485             bool duplicate = false;
 486
 487             if (direction_classes[0] == 0)
 488             {
 489                 // Recheck because ALL dimensions should be checked,
 490                 // not only first one.
 491                 // (dimension_count might be < dimension<P>::value)
 492                 if (check_duplicate_loop
 493                     <
 494                         0, geometry::dimension<Point>::type::value
 495                     >::apply(robust_segment)
 496                     )
 497                 {
 498                     duplicate = true;
 499
 500                     // Change direction-info to force new section
 501                     // Note that wo consecutive duplicate segments will generate
 502                     // only one duplicate-section.
 503                     // Actual value is not important as long as it is not -1,0,1
 504                     assign_loop
 505                     <
 506                         int, 0, dimension_count
 507                     >::apply(direction_classes, -99);
 508                 }
 509             }
 510
 511             if (section.count > 0
 512                 && (! compare_loop
 513                         <
 514                             int, 0, dimension_count
 515                         >::apply(direction_classes, section.directions)
 516                     || section.count > max_count)
 517                 )
 518             {
 519                 if (! section.duplicate)
 520                 {
 521                     last_non_duplicate_index = sections.size();
 522                 }
 523
 524                 sections.push_back(section);
 525                 section = section_type();
 526             }
 527
 528             if (section.count == 0)
 529             {
 530                 section.begin_index = index;
 531                 section.ring_id = ring_id;
 532                 section.duplicate = duplicate;
 533                 section.non_duplicate_index = ndi;
 534                 section.range_count = count;
 535
 536                 if (mark_first_non_duplicated && ! duplicate)
 537                 {
 538                     section.is_non_duplicate_first = true;
 539                     mark_first_non_duplicated = false;
 540                 }
 541
 542                 copy_loop
 543                     <
 544                         int, 0, dimension_count
 545                     >::apply(direction_classes, section.directions);
 546
 547                 // In cartesian this is envelope of previous point expanded with current point
 548                 // in non-cartesian this is envelope of a segment
 549                 box_first_in_section<typename cs_tag<robust_point_type>::type>
 550                     ::apply(section.bounding_box, previous_robust_point, current_robust_point, envelope_strategy);
 551             }
 552             else
 553             {
 554                 // In cartesian this is expand with current point
 555                 // in non-cartesian this is expand with a segment
 556                 box_next_in_section<typename cs_tag<robust_point_type>::type>
 557                     ::apply(section.bounding_box, previous_robust_point, current_robust_point, expand_strategy);
 558             }
 559
 560             section.end_index = index + 1;
 561             section.count++;
 562             if (! duplicate)
 563             {
 564                 ndi++;
 565             }
 566             previous_robust_point = current_robust_point;
 567         }
 568
 569         // Add last section if applicable
 570         if (section.count > 0)
 571         {
 572             if (! section.duplicate)
 573             {
 574                 last_non_duplicate_index = sections.size();
 575             }
 576
 577             sections.push_back(section);
 578         }
 579
 580         if (last_non_duplicate_index < sections.size()
 581             && ! sections[last_non_duplicate_index].duplicate)
 582         {
 583             sections[last_non_duplicate_index].is_non_duplicate_last = true;
 584         }
 585     }
 586 };
 587
 588
 589 template
 590 <
 591     closure_selector Closure,
 592     bool Reverse,
 593     typename Point,
 594     typename DimensionVector
 595 >
 596 struct sectionalize_range
 597 {
 598     template
 599     <
 600         typename Range,
 601         typename RobustPolicy,
 602         typename Sections,
 603         typename EnvelopeStrategy,
 604         typename ExpandStrategy
 605     >
 606     static inline void apply(Range const& range,
 607                              RobustPolicy const& robust_policy,
 608                              Sections& sections,
 609                              EnvelopeStrategy const& envelope_strategy,
 610                              ExpandStrategy const& expand_strategy,
 611                              ring_identifier ring_id,
 612                              std::size_t max_count)
 613     {
 614         typedef typename closeable_view<Range const, Closure>::type cview_type;
 615         typedef typename reversible_view
 616         <
 617             cview_type const,
 618             Reverse ? iterate_reverse : iterate_forward
 619         >::type view_type;
 620
 621         cview_type cview(range);
 622         view_type view(cview);
 623
 624         std::size_t const n = boost::size(view);
 625         if (n == 0)
 626         {
 627             // Zero points, no section
 628             return;
 629         }
 630
 631         if (n == 1)
 632         {
 633             // Line with one point ==> no sections
 634             return;
 635         }
 636
 637         sectionalize_part<Point, DimensionVector>::apply(sections,
 638             boost::begin(view), boost::end(view),
 639             robust_policy, envelope_strategy, expand_strategy,
 640             ring_id, max_count);
 641     }
 642 };
 643
 644 template
 645 <
 646     bool Reverse,
 647     typename DimensionVector
 648 >
 649 struct sectionalize_polygon
 650 {
 651     template
 652     <
 653         typename Polygon,
 654         typename RobustPolicy,
 655         typename Sections,
 656         typename EnvelopeStrategy,
 657         typename ExpandStrategy
 658     >
 659     static inline void apply(Polygon const& poly,
 660                 RobustPolicy const& robust_policy,
 661                 Sections& sections,
 662                 EnvelopeStrategy const& envelope_strategy,
 663                 ExpandStrategy const& expand_strategy,
 664                 ring_identifier ring_id,
 665                 std::size_t max_count)
 666     {
 667         typedef typename point_type<Polygon>::type point_type;
 668         typedef sectionalize_range
 669         <
 670                 closure<Polygon>::value, Reverse,
 671                 point_type, DimensionVector
 672         > per_range;
 673
 674         ring_id.ring_index = -1;
 675         per_range::apply(exterior_ring(poly), robust_policy, sections,
 676                          envelope_strategy, expand_strategy, ring_id, max_count);
 677
 678         ring_id.ring_index++;
 679         typename interior_return_type<Polygon const>::type
 680             rings = interior_rings(poly);
 681         for (typename detail::interior_iterator<Polygon const>::type
 682                 it = boost::begin(rings); it != boost::end(rings); ++it, ++ring_id.ring_index)
 683         {
 684             per_range::apply(*it, robust_policy, sections,
 685                              envelope_strategy, expand_strategy, ring_id, max_count);
 686         }
 687     }
 688 };
 689
 690 template <typename DimensionVector>
 691 struct sectionalize_box
 692 {
 693     template
 694     <
 695         typename Box,
 696         typename RobustPolicy,
 697         typename Sections,
 698         typename EnvelopeStrategy,
 699         typename ExpandStrategy
 700     >
 701     static inline void apply(Box const& box,
 702                 RobustPolicy const& robust_policy,
 703                 Sections& sections,
 704                 EnvelopeStrategy const& envelope_strategy,
 705                 ExpandStrategy const& expand_strategy,
 706                 ring_identifier const& ring_id, std::size_t max_count)
 707     {
 708         typedef typename point_type<Box>::type point_type;
 709
 710         assert_dimension<Box, 2>();
 711
 712         // Add all four sides of the 2D-box as separate section.
 713         // Easiest is to convert it to a polygon.
 714         // However, we don't have the polygon type
 715         // (or polygon would be a helper-type).
 716         // Therefore we mimic a linestring/std::vector of 5 points
 717
 718         // TODO: might be replaced by assign_box_corners_oriented
 719         // or just "convert"
 720         point_type ll, lr, ul, ur;
 721         geometry::detail::assign_box_corners(box, ll, lr, ul, ur);
 722
 723         std::vector<point_type> points;
 724         points.push_back(ll);
 725         points.push_back(ul);
 726         points.push_back(ur);
 727         points.push_back(lr);
 728         points.push_back(ll);
 729
 730         // NOTE: Use cartesian envelope strategy in all coordinate systems
 731         //       because edges of a box are not geodesic segments
 732         sectionalize_range
 733         <
 734                 closed, false,
 735             point_type,
 736             DimensionVector
 737         >::apply(points, robust_policy, sections,
 738                  envelope_strategy, expand_strategy,
 739                  ring_id, max_count);
 740     }
 741 };
 742
 743 template <typename DimensionVector, typename Policy>
 744 struct sectionalize_multi
 745 {
 746     template
 747     <
 748         typename MultiGeometry,
 749         typename RobustPolicy,
 750         typename Sections,
 751         typename EnvelopeStrategy,
 752         typename ExpandStrategy
 753     >
 754     static inline void apply(MultiGeometry const& multi,
 755                 RobustPolicy const& robust_policy,
 756                 Sections& sections,
 757                 EnvelopeStrategy const& envelope_strategy,
 758                 ExpandStrategy const& expand_strategy,
 759                 ring_identifier ring_id,
 760                 std::size_t max_count)
 761     {
 762         ring_id.multi_index = 0;
 763         for (typename boost::range_iterator<MultiGeometry const>::type
 764                     it = boost::begin(multi);
 765             it != boost::end(multi);
 766             ++it, ++ring_id.multi_index)
 767         {
 768             Policy::apply(*it, robust_policy, sections,
 769                           envelope_strategy, expand_strategy,
 770                           ring_id, max_count);
 771         }
 772     }
 773 };
 774
 775 template <typename Sections>
 776 inline void enlarge_sections(Sections& sections)
 777 {
 778     // Robustness issue. Increase sections a tiny bit such that all points are really within (and not on border)
 779     // Reason: turns might, rarely, be missed otherwise (case: "buffer_mp1")
 780     // Drawback: not really, range is now completely inside the section. Section is a tiny bit too large,
 781     // which might cause (a small number) of more comparisons
 782
 783     // NOTE: above is old comment to the not used code expanding the Boxes by relaxed_epsilon(10)
 784
 785     // Enlarge sections by scaled epsilon, this should be consistent with math::equals().
 786     // Points and Segments are equal-compared WRT machine epsilon, but Boxes aren't
 787     // Enlarging Boxes ensures that they correspond to the bound objects,
 788     // Segments in this case, since Sections are collections of Segments.
 789     for (typename boost::range_iterator<Sections>::type it = boost::begin(sections);
 790         it != boost::end(sections);
 791         ++it)
 792     {
 793         detail::expand_by_epsilon(it->bounding_box);
 794     }
 795 }
 796
 797
 798 }} // namespace detail::sectionalize
 799 #endif // DOXYGEN_NO_DETAIL
 800
 801
 802 #ifndef DOXYGEN_NO_DISPATCH
 803 namespace dispatch
 804 {
 805
 806 template
 807 <
 808     typename Tag,
 809     typename Geometry,
 810     bool Reverse,
 811     typename DimensionVector
 812 >
 813 struct sectionalize
 814 {
 815     BOOST_MPL_ASSERT_MSG
 816         (
 817             false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
 818             , (types<Geometry>)
 819         );
 820 };
 821
 822 template
 823 <
 824     typename Box,
 825     bool Reverse,
 826     typename DimensionVector
 827 >
 828 struct sectionalize<box_tag, Box, Reverse, DimensionVector>
 829     : detail::sectionalize::sectionalize_box<DimensionVector>
 830 {};
 831
 832 template
 833 <
 834     typename LineString,
 835     typename DimensionVector
 836 >
 837 struct sectionalize
 838     <
 839         linestring_tag,
 840         LineString,
 841         false,
 842         DimensionVector
 843     >
 844     : detail::sectionalize::sectionalize_range
 845         <
 846             closed, false,
 847             typename point_type<LineString>::type,
 848             DimensionVector
 849         >
 850 {};
 851
 852 template
 853 <
 854     typename Ring,
 855     bool Reverse,
 856     typename DimensionVector
 857 >
 858 struct sectionalize<ring_tag, Ring, Reverse, DimensionVector>
 859     : detail::sectionalize::sectionalize_range
 860         <
 861             geometry::closure<Ring>::value, Reverse,
 862             typename point_type<Ring>::type,
 863             DimensionVector
 864         >
 865 {};
 866
 867 template
 868 <
 869     typename Polygon,
 870     bool Reverse,
 871     typename DimensionVector
 872 >
 873 struct sectionalize<polygon_tag, Polygon, Reverse, DimensionVector>
 874     : detail::sectionalize::sectionalize_polygon
 875         <
 876             Reverse, DimensionVector
 877         >
 878 {};
 879
 880 template
 881 <
 882     typename MultiPolygon,
 883     bool Reverse,
 884     typename DimensionVector
 885 >
 886 struct sectionalize<multi_polygon_tag, MultiPolygon, Reverse, DimensionVector>
 887     : detail::sectionalize::sectionalize_multi
 888         <
 889             DimensionVector,
 890             detail::sectionalize::sectionalize_polygon
 891                 <
 892                     Reverse,
 893                     DimensionVector
 894                 >
 895         >
 896
 897 {};
 898
 899 template
 900 <
 901     typename MultiLinestring,
 902     bool Reverse,
 903     typename DimensionVector
 904 >
 905 struct sectionalize<multi_linestring_tag, MultiLinestring, Reverse, DimensionVector>
 906     : detail::sectionalize::sectionalize_multi
 907         <
 908             DimensionVector,
 909             detail::sectionalize::sectionalize_range
 910                 <
 911                     closed, false,
 912                     typename point_type<MultiLinestring>::type,
 913                     DimensionVector
 914                 >
 915         >
 916
 917 {};
 918
 919 } // namespace dispatch
 920 #endif
 921
 922
 923 /*!
 924     \brief Split a geometry into monotonic sections
 925     \ingroup sectionalize
 926     \tparam Geometry type of geometry to check
 927     \tparam Sections type of sections to create
 928     \param geometry geometry to create sections from
 929     \param robust_policy policy to handle robustness issues
 930     \param sections structure with sections
 931     \param envelope_strategy strategy for envelope calculation
 932     \param expand_strategy strategy for partitions
 933     \param source_index index to assign to the ring_identifiers
 934     \param max_count maximal number of points per section
 935         (defaults to 10, this seems to give the fastest results)
 936
 937  */
 938 template
 939 <
 940     bool Reverse,
 941     typename DimensionVector,
 942     typename Geometry,
 943     typename Sections,
 944     typename RobustPolicy,
 945     typename EnvelopeStrategy,
 946     typename ExpandStrategy
 947 >
 948 inline void sectionalize(Geometry const& geometry,
 949                 RobustPolicy const& robust_policy,
 950                 Sections& sections,
 951                 EnvelopeStrategy const& envelope_strategy,
 952                 ExpandStrategy const& expand_strategy,
 953                 int source_index = 0,
 954                 std::size_t max_count = 10)
 955 {
 956     BOOST_STATIC_ASSERT((! boost::is_fundamental<EnvelopeStrategy>::value));
 957
 958     concepts::check<Geometry const>();
 959
 960     typedef typename boost::range_value<Sections>::type section_type;
 961
 962     // Compiletime check for point type of section boxes
 963     // and point type related to robust policy
 964     typedef typename geometry::coordinate_type
 965     <
 966         typename section_type::box_type
 967     >::type ctype1;
 968     typedef typename geometry::coordinate_type
 969     <
 970         typename geometry::robust_point_type
 971         <
 972             typename geometry::point_type<Geometry>::type,
 973             RobustPolicy
 974         >::type
 975     >::type ctype2;
 976
 977     BOOST_MPL_ASSERT((boost::is_same<ctype1, ctype2>));
 978
 979
 980     sections.clear();
 981
 982     ring_identifier ring_id;
 983     ring_id.source_index = source_index;
 984
 985     dispatch::sectionalize
 986         <
 987             typename tag<Geometry>::type,
 988             Geometry,
 989             Reverse,
 990             DimensionVector
 991         >::apply(geometry, robust_policy, sections,
 992                  envelope_strategy, expand_strategy,
 993                  ring_id, max_count);
 994
 995     detail::sectionalize::enlarge_sections(sections);
 996 }
 997
 998
 999 template
1000 <
1001     bool Reverse,
1002     typename DimensionVector,
1003     typename Geometry,
1004     typename Sections,
1005     typename RobustPolicy
1006 >
1007 inline void sectionalize(Geometry const& geometry,
1008                          RobustPolicy const& robust_policy,
1009                          Sections& sections,
1010                          int source_index = 0,
1011                          std::size_t max_count = 10)
1012 {
1013     typedef typename strategy::envelope::services::default_strategy
1014         <
1015             typename tag<Geometry>::type,
1016             typename cs_tag<Geometry>::type
1017         >::type envelope_strategy_type;
1018
1019     typedef typename strategy::expand::services::default_strategy
1020         <
1021             typename boost::mpl::if_c
1022                 <
1023                     boost::is_same<typename tag<Geometry>::type, box_tag>::value,
1024                     box_tag,
1025                     segment_tag
1026                 >::type,
1027             typename cs_tag<Geometry>::type
1028         >::type expand_strategy_type;
1029
1030     boost::geometry::sectionalize
1031         <
1032             Reverse, DimensionVector
1033         >(geometry, robust_policy, sections,
1034           envelope_strategy_type(),
1035           expand_strategy_type(),
1036           source_index, max_count);
1037 }
1038
1039 }} // namespace boost::geometry
1040
1041
1042 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP