Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
Chris@16: // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
Chris@101: // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
Chris@101: 
Chris@101: // This file was modified by Oracle on 2013, 2014.
Chris@101: // Modifications copyright (c) 2013, 2014 Oracle and/or its affiliates.
Chris@101: 
Chris@101: // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
Chris@101: // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
Chris@16: 
Chris@16: // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
Chris@16: // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: #include <vector>
Chris@16: 
Chris@101: #include <boost/concept/requires.hpp>
Chris@16: #include <boost/mpl/assert.hpp>
Chris@101: #include <boost/mpl/vector_c.hpp>
Chris@16: #include <boost/range.hpp>
Chris@101: #include <boost/static_assert.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/assign.hpp>
Chris@16: #include <boost/geometry/algorithms/expand.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
Chris@101: #include <boost/geometry/algorithms/detail/recalculate.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/core/access.hpp>
Chris@16: #include <boost/geometry/core/closure.hpp>
Chris@16: #include <boost/geometry/core/exterior_ring.hpp>
Chris@16: #include <boost/geometry/core/point_order.hpp>
Chris@101: #include <boost/geometry/core/tags.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/geometries/concepts/check.hpp>
Chris@16: #include <boost/geometry/util/math.hpp>
Chris@101: #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
Chris@101: #include <boost/geometry/policies/robustness/robust_point_type.hpp>
Chris@16: #include <boost/geometry/views/closeable_view.hpp>
Chris@16: #include <boost/geometry/views/reversible_view.hpp>
Chris@16: #include <boost/geometry/geometries/segment.hpp>
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Structure containing section information
Chris@16:     \details Section information consists of a bounding box, direction
Chris@16:         information (if it is increasing or decreasing, per dimension),
Chris@16:         index information (begin-end, ring, multi) and the number of
Chris@16:         segments in this section
Chris@16: 
Chris@16:     \tparam Box box-type
Chris@16:     \tparam DimensionCount number of dimensions for this section
Chris@16:     \ingroup sectionalize
Chris@16:  */
Chris@101: template
Chris@101: <
Chris@101:     typename Box,
Chris@101:     std::size_t DimensionCount
Chris@101: >
Chris@16: struct section
Chris@16: {
Chris@16:     typedef Box box_type;
Chris@101:     static std::size_t const dimension_count = DimensionCount;
Chris@16: 
Chris@16:     int directions[DimensionCount];
Chris@16:     ring_identifier ring_id;
Chris@16:     Box bounding_box;
Chris@16: 
Chris@16:     int begin_index;
Chris@16:     int end_index;
Chris@16:     std::size_t count;
Chris@16:     std::size_t range_count;
Chris@16:     bool duplicate;
Chris@16:     int non_duplicate_index;
Chris@16: 
Chris@101:     bool is_non_duplicate_first;
Chris@101:     bool is_non_duplicate_last;
Chris@101: 
Chris@16:     inline section()
Chris@101:         : begin_index(-1)
Chris@16:         , end_index(-1)
Chris@16:         , count(0)
Chris@16:         , range_count(0)
Chris@16:         , duplicate(false)
Chris@16:         , non_duplicate_index(-1)
Chris@101:         , is_non_duplicate_first(false)
Chris@101:         , is_non_duplicate_last(false)
Chris@16:     {
Chris@16:         assign_inverse(bounding_box);
Chris@16:         for (std::size_t i = 0; i < DimensionCount; i++)
Chris@16:         {
Chris@16:             directions[i] = 0;
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Structure containing a collection of sections
Chris@16:     \note Derived from a vector, proves to be faster than of deque
Chris@16:     \note vector might be templated in the future
Chris@16:     \ingroup sectionalize
Chris@16:  */
Chris@16: template <typename Box, std::size_t DimensionCount>
Chris@16: struct sections : std::vector<section<Box, DimensionCount> >
Chris@16: {
Chris@16:     typedef Box box_type;
Chris@16:     static std::size_t const value = DimensionCount;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail { namespace sectionalize
Chris@16: {
Chris@16: 
Chris@101: template
Chris@101: <
Chris@101:     typename DimensionVector,
Chris@101:     std::size_t Index,
Chris@101:     std::size_t Count
Chris@101: >
Chris@16: struct get_direction_loop
Chris@16: {
Chris@101:     typedef typename boost::mpl::at_c<DimensionVector, Index>::type dimension;
Chris@16: 
Chris@101:     template <typename Segment>
Chris@16:     static inline void apply(Segment const& seg,
Chris@101:                 int directions[Count])
Chris@16:     {
Chris@101:         typedef typename coordinate_type<Segment>::type coordinate_type;
Chris@101: 
Chris@16:         coordinate_type const diff =
Chris@101:             geometry::get<1, dimension::value>(seg)
Chris@101:           - geometry::get<0, dimension::value>(seg);
Chris@16: 
Chris@16:         coordinate_type zero = coordinate_type();
Chris@101:         directions[Index] = diff > zero ? 1 : diff < zero ? -1 : 0;
Chris@16: 
Chris@16:         get_direction_loop
Chris@101:         <
Chris@101:             DimensionVector,
Chris@101:             Index + 1,
Chris@101:             Count
Chris@101:         >::apply(seg, directions);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@101: template <typename DimensionVector, std::size_t Count>
Chris@101: struct get_direction_loop<DimensionVector, Count, Count>
Chris@16: {
Chris@101:     template <typename Segment>
Chris@101:     static inline void apply(Segment const&, int [Count])
Chris@16:     {}
Chris@16: };
Chris@16: 
Chris@101: //! Copy one static array to another
Chris@101: template <typename T, std::size_t Index, std::size_t Count>
Chris@16: struct copy_loop
Chris@16: {
Chris@101:     static inline void apply(T const source[Count], T target[Count])
Chris@16:     {
Chris@101:         target[Index] = source[Index];
Chris@101:         copy_loop<T, Index + 1, Count>::apply(source, target);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@101: template <typename T, std::size_t Count>
Chris@101: struct copy_loop<T, Count, Count>
Chris@16: {
Chris@101:     static inline void apply(T const [Count], T [Count])
Chris@16:     {}
Chris@16: };
Chris@16: 
Chris@101: //! Compare two static arrays
Chris@101: template <typename T, std::size_t Index, std::size_t Count>
Chris@16: struct compare_loop
Chris@16: {
Chris@101:     static inline bool apply(T const array1[Count], T const array2[Count])
Chris@16:     {
Chris@101:         return array1[Index] != array2[Index]
Chris@16:             ? false
Chris@16:             : compare_loop
Chris@16:                 <
Chris@101:                     T, Index + 1, Count
Chris@101:                 >::apply(array1, array2);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@101: template <typename T, std::size_t Count>
Chris@101: struct compare_loop<T, Count, Count>
Chris@16: {
Chris@101:     static inline bool apply(T const [Count], T const [Count])
Chris@16:     {
Chris@16: 
Chris@16:         return true;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@101: template <std::size_t Dimension, std::size_t DimensionCount>
Chris@16: struct check_duplicate_loop
Chris@16: {
Chris@101:     template <typename Segment>
Chris@16:     static inline bool apply(Segment const& seg)
Chris@16:     {
Chris@16:         if (! geometry::math::equals
Chris@16:                 (
Chris@101:                     geometry::get<0, Dimension>(seg),
Chris@16:                     geometry::get<1, Dimension>(seg)
Chris@16:                 )
Chris@16:             )
Chris@16:         {
Chris@16:             return false;
Chris@16:         }
Chris@16: 
Chris@16:         return check_duplicate_loop
Chris@101:         <
Chris@101:                 Dimension + 1, DimensionCount
Chris@101:         >::apply(seg);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@101: template <std::size_t DimensionCount>
Chris@101: struct check_duplicate_loop<DimensionCount, DimensionCount>
Chris@16: {
Chris@101:     template <typename Segment>
Chris@16:     static inline bool apply(Segment const&)
Chris@16:     {
Chris@16:         return true;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@101: //! Assign a value to a static array
Chris@101: template <typename T, std::size_t Index, std::size_t Count>
Chris@16: struct assign_loop
Chris@16: {
Chris@101:     static inline void apply(T dims[Count], int const value)
Chris@16:     {
Chris@101:         dims[Index] = value;
Chris@101:         assign_loop<T, Index + 1, Count>::apply(dims, value);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@101: template <typename T, std::size_t Count>
Chris@101: struct assign_loop<T, Count, Count>
Chris@16: {
Chris@101:     static inline void apply(T [Count], int const)
Chris@16:     {
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: /// @brief Helper class to create sections of a part of a range, on the fly
Chris@16: template
Chris@16: <
Chris@16:     typename Point,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@16: struct sectionalize_part
Chris@16: {
Chris@101:     static const std::size_t dimension_count
Chris@101:         = boost::mpl::size<DimensionVector>::value;
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename Iterator,
Chris@101:         typename RobustPolicy,
Chris@101:         typename Sections
Chris@101:     >
Chris@101:     static inline void apply(Sections& sections,
Chris@101:                              Iterator begin, Iterator end,
Chris@101:                              RobustPolicy const& robust_policy,
Chris@101:                              ring_identifier ring_id,
Chris@101:                              std::size_t max_count)
Chris@101:     {
Chris@101:         boost::ignore_unused_variable_warning(robust_policy);
Chris@16: 
Chris@101:         typedef typename boost::range_value<Sections>::type section_type;
Chris@101:         BOOST_STATIC_ASSERT
Chris@101:             (
Chris@101:                 (static_cast<int>(section_type::dimension_count)
Chris@101:                  == static_cast<int>(boost::mpl::size<DimensionVector>::value))
Chris@101:             );
Chris@101: 
Chris@101:         typedef typename geometry::robust_point_type
Chris@101:         <
Chris@101:             Point,
Chris@101:             RobustPolicy
Chris@101:         >::type robust_point_type;
Chris@101: 
Chris@101:         std::size_t const count = std::distance(begin, end);
Chris@101:         if (count == 0)
Chris@16:         {
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@101:         int index = 0;
Chris@101:         int ndi = 0; // non duplicate index
Chris@101:         section_type section;
Chris@16: 
Chris@101:         bool mark_first_non_duplicated = true;
Chris@101:         std::size_t last_non_duplicate_index = sections.size();
Chris@16: 
Chris@101:         Iterator it = begin;
Chris@101:         robust_point_type previous_robust_point;
Chris@101:         geometry::recalculate(previous_robust_point, *it, robust_policy);
Chris@101:         
Chris@101:         for(Iterator previous = it++;
Chris@101:             it != end;
Chris@16:             ++previous, ++it, index++)
Chris@16:         {
Chris@101:             robust_point_type current_robust_point;
Chris@101:             geometry::recalculate(current_robust_point, *it, robust_policy);
Chris@101:             model::referring_segment<robust_point_type> robust_segment(
Chris@101:                     previous_robust_point, current_robust_point);
Chris@16: 
Chris@101:             int direction_classes[dimension_count] = {0};
Chris@16:             get_direction_loop
Chris@101:             <
Chris@101:                 DimensionVector, 0, dimension_count
Chris@101:             >::apply(robust_segment, direction_classes);
Chris@16: 
Chris@16:             // if "dir" == 0 for all point-dimensions, it is duplicate.
Chris@16:             // Those sections might be omitted, if wished, lateron
Chris@16:             bool duplicate = false;
Chris@16: 
Chris@16:             if (direction_classes[0] == 0)
Chris@16:             {
Chris@16:                 // Recheck because ALL dimensions should be checked,
Chris@16:                 // not only first one.
Chris@101:                 // (dimension_count might be < dimension<P>::value)
Chris@16:                 if (check_duplicate_loop
Chris@16:                     <
Chris@101:                         0, geometry::dimension<Point>::type::value
Chris@101:                     >::apply(robust_segment)
Chris@16:                     )
Chris@16:                 {
Chris@16:                     duplicate = true;
Chris@16: 
Chris@16:                     // Change direction-info to force new section
Chris@16:                     // Note that wo consecutive duplicate segments will generate
Chris@16:                     // only one duplicate-section.
Chris@16:                     // Actual value is not important as long as it is not -1,0,1
Chris@16:                     assign_loop
Chris@16:                     <
Chris@101:                         int, 0, dimension_count
Chris@16:                     >::apply(direction_classes, -99);
Chris@16:                 }
Chris@16:             }
Chris@16: 
Chris@16:             if (section.count > 0
Chris@101:                 && (! compare_loop
Chris@16:                         <
Chris@101:                             int, 0, dimension_count
Chris@16:                         >::apply(direction_classes, section.directions)
Chris@101:                     || section.count > max_count)
Chris@16:                 )
Chris@16:             {
Chris@101:                 if (! section.duplicate)
Chris@101:                 {
Chris@101:                     last_non_duplicate_index = sections.size();
Chris@101:                 }
Chris@101: 
Chris@16:                 sections.push_back(section);
Chris@16:                 section = section_type();
Chris@16:             }
Chris@16: 
Chris@16:             if (section.count == 0)
Chris@16:             {
Chris@16:                 section.begin_index = index;
Chris@16:                 section.ring_id = ring_id;
Chris@16:                 section.duplicate = duplicate;
Chris@16:                 section.non_duplicate_index = ndi;
Chris@101:                 section.range_count = count;
Chris@101: 
Chris@101:                 if (mark_first_non_duplicated && ! duplicate)
Chris@101:                 {
Chris@101:                     section.is_non_duplicate_first = true;
Chris@101:                     mark_first_non_duplicated = false;
Chris@101:                 }
Chris@16: 
Chris@16:                 copy_loop
Chris@16:                     <
Chris@101:                         int, 0, dimension_count
Chris@16:                     >::apply(direction_classes, section.directions);
Chris@101: 
Chris@101:                 geometry::expand(section.bounding_box, previous_robust_point);
Chris@16:             }
Chris@16: 
Chris@101:             geometry::expand(section.bounding_box, current_robust_point);
Chris@16:             section.end_index = index + 1;
Chris@16:             section.count++;
Chris@16:             if (! duplicate)
Chris@16:             {
Chris@16:                 ndi++;
Chris@16:             }
Chris@101:             previous_robust_point = current_robust_point;
Chris@101:         }
Chris@101: 
Chris@101:         // Add last section if applicable
Chris@101:         if (section.count > 0)
Chris@101:         {
Chris@101:             if (! section.duplicate)
Chris@101:             {
Chris@101:                 last_non_duplicate_index = sections.size();
Chris@101:             }
Chris@101: 
Chris@101:             sections.push_back(section);
Chris@101:         }
Chris@101: 
Chris@101:         if (last_non_duplicate_index < sections.size()
Chris@101:             && ! sections[last_non_duplicate_index].duplicate)
Chris@101:         {
Chris@101:             sections[last_non_duplicate_index].is_non_duplicate_last = true;
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@101:     closure_selector Closure,
Chris@101:     bool Reverse,
Chris@16:     typename Point,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@16: struct sectionalize_range
Chris@16: {
Chris@101:     template
Chris@101:     <
Chris@101:         typename Range,
Chris@101:         typename RobustPolicy,
Chris@101:         typename Sections
Chris@101:     >
Chris@101:     static inline void apply(Range const& range,
Chris@101:                              RobustPolicy const& robust_policy,
Chris@101:                              Sections& sections,
Chris@101:                              ring_identifier ring_id,
Chris@101:                              std::size_t max_count)
Chris@101:     {
Chris@101:         typedef typename closeable_view<Range const, Closure>::type cview_type;
Chris@101:         typedef typename reversible_view
Chris@16:         <
Chris@16:             cview_type const,
Chris@16:             Reverse ? iterate_reverse : iterate_forward
Chris@16:         >::type view_type;
Chris@16: 
Chris@16:         cview_type cview(range);
Chris@16:         view_type view(cview);
Chris@16: 
Chris@16:         std::size_t const n = boost::size(view);
Chris@16:         if (n == 0)
Chris@16:         {
Chris@16:             // Zero points, no section
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@16:         if (n == 1)
Chris@16:         {
Chris@16:             // Line with one point ==> no sections
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@101:         sectionalize_part<Point, DimensionVector>::apply(sections,
Chris@101:             boost::begin(view), boost::end(view),
Chris@101:             robust_policy, ring_id, max_count);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     bool Reverse,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@16: struct sectionalize_polygon
Chris@16: {
Chris@101:     template
Chris@101:     <
Chris@101:         typename Polygon,
Chris@101:         typename RobustPolicy,
Chris@101:         typename Sections
Chris@101:     >
Chris@101:     static inline void apply(Polygon const& poly,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 Sections& sections,
Chris@101:                 ring_identifier ring_id, std::size_t max_count)
Chris@16:     {
Chris@16:         typedef typename point_type<Polygon>::type point_type;
Chris@16:         typedef sectionalize_range
Chris@101:         <
Chris@101:                 closure<Polygon>::value, Reverse,
Chris@101:                 point_type, DimensionVector
Chris@101:         > per_range;
Chris@16: 
Chris@16:         ring_id.ring_index = -1;
Chris@101:         per_range::apply(exterior_ring(poly), robust_policy, sections, ring_id, max_count);
Chris@16: 
Chris@16:         ring_id.ring_index++;
Chris@101:         typename interior_return_type<Polygon const>::type
Chris@101:             rings = interior_rings(poly);
Chris@101:         for (typename detail::interior_iterator<Polygon const>::type
Chris@101:                 it = boost::begin(rings); it != boost::end(rings); ++it, ++ring_id.ring_index)
Chris@16:         {
Chris@101:             per_range::apply(*it, robust_policy, sections, ring_id, max_count);
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@101: template <typename DimensionVector>
Chris@16: struct sectionalize_box
Chris@16: {
Chris@101:     template
Chris@101:     <
Chris@101:         typename Box,
Chris@101:         typename RobustPolicy,
Chris@101:         typename Sections
Chris@101:     >
Chris@101:     static inline void apply(Box const& box,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 Sections& sections,
Chris@101:                 ring_identifier const& ring_id, std::size_t max_count)
Chris@16:     {
Chris@16:         typedef typename point_type<Box>::type point_type;
Chris@16: 
Chris@16:         assert_dimension<Box, 2>();
Chris@16: 
Chris@16:         // Add all four sides of the 2D-box as separate section.
Chris@16:         // Easiest is to convert it to a polygon.
Chris@16:         // However, we don't have the polygon type
Chris@16:         // (or polygon would be a helper-type).
Chris@16:         // Therefore we mimic a linestring/std::vector of 5 points
Chris@16: 
Chris@101:         // TODO: might be replaced by assign_box_corners_oriented
Chris@16:         // or just "convert"
Chris@16:         point_type ll, lr, ul, ur;
Chris@16:         geometry::detail::assign_box_corners(box, ll, lr, ul, ur);
Chris@16: 
Chris@16:         std::vector<point_type> points;
Chris@16:         points.push_back(ll);
Chris@16:         points.push_back(ul);
Chris@16:         points.push_back(ur);
Chris@16:         points.push_back(lr);
Chris@16:         points.push_back(ll);
Chris@16: 
Chris@16:         sectionalize_range
Chris@101:         <
Chris@101:                 closed, false,
Chris@101:             point_type,
Chris@101:             DimensionVector
Chris@101:         >::apply(points, robust_policy, sections,
Chris@101:                  ring_id, max_count);
Chris@101:     }
Chris@101: };
Chris@101: 
Chris@101: template <typename DimensionVector, typename Policy>
Chris@101: struct sectionalize_multi
Chris@101: {
Chris@101:     template
Chris@101:     <
Chris@101:         typename MultiGeometry,
Chris@101:         typename RobustPolicy,
Chris@101:         typename Sections
Chris@101:     >
Chris@101:     static inline void apply(MultiGeometry const& multi,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 Sections& sections, ring_identifier ring_id, std::size_t max_count)
Chris@101:     {
Chris@101:         ring_id.multi_index = 0;
Chris@101:         for (typename boost::range_iterator<MultiGeometry const>::type
Chris@101:                     it = boost::begin(multi);
Chris@101:             it != boost::end(multi);
Chris@101:             ++it, ++ring_id.multi_index)
Chris@101:         {
Chris@101:             Policy::apply(*it, robust_policy, sections, ring_id, max_count);
Chris@101:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Sections>
Chris@101: inline void enlarge_sections(Sections& sections)
Chris@16: {
Chris@16:     // Robustness issue. Increase sections a tiny bit such that all points are really within (and not on border)
Chris@16:     // Reason: turns might, rarely, be missed otherwise (case: "buffer_mp1")
Chris@16:     // Drawback: not really, range is now completely inside the section. Section is a tiny bit too large,
Chris@16:     // which might cause (a small number) of more comparisons
Chris@16:     // TODO: make dimension-agnostic
Chris@16:     for (typename boost::range_iterator<Sections>::type it = boost::begin(sections);
Chris@16:         it != boost::end(sections);
Chris@16:         ++it)
Chris@16:     {
Chris@16:         typedef typename boost::range_value<Sections>::type section_type;
Chris@16:         typedef typename section_type::box_type box_type;
Chris@16:         typedef typename geometry::coordinate_type<box_type>::type coordinate_type;
Chris@16:         coordinate_type const reps = math::relaxed_epsilon(10.0);
Chris@16:         geometry::set<0, 0>(it->bounding_box, geometry::get<0, 0>(it->bounding_box) - reps);
Chris@16:         geometry::set<0, 1>(it->bounding_box, geometry::get<0, 1>(it->bounding_box) - reps);
Chris@16:         geometry::set<1, 0>(it->bounding_box, geometry::get<1, 0>(it->bounding_box) + reps);
Chris@16:         geometry::set<1, 1>(it->bounding_box, geometry::get<1, 1>(it->bounding_box) + reps);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: }} // namespace detail::sectionalize
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DISPATCH
Chris@16: namespace dispatch
Chris@16: {
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Tag,
Chris@16:     typename Geometry,
Chris@16:     bool Reverse,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@16: struct sectionalize
Chris@16: {
Chris@16:     BOOST_MPL_ASSERT_MSG
Chris@16:         (
Chris@16:             false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
Chris@16:             , (types<Geometry>)
Chris@16:         );
Chris@16: };
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Box,
Chris@16:     bool Reverse,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@101: struct sectionalize<box_tag, Box, Reverse, DimensionVector>
Chris@101:     : detail::sectionalize::sectionalize_box<DimensionVector>
Chris@16: {};
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename LineString,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@16: struct sectionalize
Chris@16:     <
Chris@16:         linestring_tag,
Chris@16:         LineString,
Chris@16:         false,
Chris@101:         DimensionVector
Chris@16:     >
Chris@16:     : detail::sectionalize::sectionalize_range
Chris@16:         <
Chris@101:             closed, false,
Chris@16:             typename point_type<LineString>::type,
Chris@101:             DimensionVector
Chris@16:         >
Chris@16: {};
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Ring,
Chris@16:     bool Reverse,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@101: struct sectionalize<ring_tag, Ring, Reverse, DimensionVector>
Chris@16:     : detail::sectionalize::sectionalize_range
Chris@16:         <
Chris@101:             geometry::closure<Ring>::value, Reverse,
Chris@16:             typename point_type<Ring>::type,
Chris@101:             DimensionVector
Chris@16:         >
Chris@16: {};
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Polygon,
Chris@16:     bool Reverse,
Chris@101:     typename DimensionVector
Chris@16: >
Chris@101: struct sectionalize<polygon_tag, Polygon, Reverse, DimensionVector>
Chris@16:     : detail::sectionalize::sectionalize_polygon
Chris@16:         <
Chris@101:             Reverse, DimensionVector
Chris@16:         >
Chris@16: {};
Chris@16: 
Chris@101: template
Chris@101: <
Chris@101:     typename MultiPolygon,
Chris@101:     bool Reverse,
Chris@101:     typename DimensionVector
Chris@101: >
Chris@101: struct sectionalize<multi_polygon_tag, MultiPolygon, Reverse, DimensionVector>
Chris@101:     : detail::sectionalize::sectionalize_multi
Chris@101:         <
Chris@101:             DimensionVector,
Chris@101:             detail::sectionalize::sectionalize_polygon
Chris@101:                 <
Chris@101:                     Reverse,
Chris@101:                     DimensionVector
Chris@101:                 >
Chris@101:         >
Chris@101: 
Chris@101: {};
Chris@101: 
Chris@101: template
Chris@101: <
Chris@101:     typename MultiLinestring,
Chris@101:     bool Reverse,
Chris@101:     typename DimensionVector
Chris@101: >
Chris@101: struct sectionalize<multi_linestring_tag, MultiLinestring, Reverse, DimensionVector>
Chris@101:     : detail::sectionalize::sectionalize_multi
Chris@101:         <
Chris@101:             DimensionVector,
Chris@101:             detail::sectionalize::sectionalize_range
Chris@101:                 <
Chris@101:                     closed, false,
Chris@101:                     typename point_type<MultiLinestring>::type,
Chris@101:                     DimensionVector
Chris@101:                 >
Chris@101:         >
Chris@101: 
Chris@101: {};
Chris@101: 
Chris@16: } // namespace dispatch
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Split a geometry into monotonic sections
Chris@16:     \ingroup sectionalize
Chris@16:     \tparam Geometry type of geometry to check
Chris@16:     \tparam Sections type of sections to create
Chris@16:     \param geometry geometry to create sections from
Chris@101:     \param robust_policy policy to handle robustness issues
Chris@16:     \param sections structure with sections
Chris@16:     \param source_index index to assign to the ring_identifiers
Chris@101:     \param max_count maximal number of points per section
Chris@101:         (defaults to 10, this seems to give the fastest results)
Chris@101: 
Chris@16:  */
Chris@101: template
Chris@101: <
Chris@101:     bool Reverse,
Chris@101:     typename DimensionVector,
Chris@101:     typename Geometry,
Chris@101:     typename Sections,
Chris@101:     typename RobustPolicy
Chris@101: >
Chris@101: inline void sectionalize(Geometry const& geometry,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 Sections& sections,
Chris@101:                 int source_index = 0,
Chris@101:                 std::size_t max_count = 10)
Chris@16: {
Chris@16:     concept::check<Geometry const>();
Chris@16: 
Chris@101:     typedef typename boost::range_value<Sections>::type section_type;
Chris@101: 
Chris@101:     // Compiletime check for point type of section boxes
Chris@101:     // and point type related to robust policy
Chris@101:     typedef typename geometry::coordinate_type
Chris@101:     <
Chris@101:         typename section_type::box_type
Chris@101:     >::type ctype1;
Chris@101:     typedef typename geometry::coordinate_type
Chris@101:     <
Chris@101:         typename geometry::robust_point_type
Chris@101:         <
Chris@101:             typename geometry::point_type<Geometry>::type,
Chris@101:             RobustPolicy
Chris@101:         >::type
Chris@101:     >::type ctype2;
Chris@101: 
Chris@101:     BOOST_MPL_ASSERT((boost::is_same<ctype1, ctype2>));
Chris@101: 
Chris@101: 
Chris@101:     sections.clear();
Chris@101: 
Chris@101:     ring_identifier ring_id;
Chris@101:     ring_id.source_index = source_index;
Chris@101: 
Chris@101:     dispatch::sectionalize
Chris@16:         <
Chris@16:             typename tag<Geometry>::type,
Chris@16:             Geometry,
Chris@16:             Reverse,
Chris@101:             DimensionVector
Chris@101:         >::apply(geometry, robust_policy, sections, ring_id, max_count);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP