| // Boost.Geometry (aka GGL, Generic Geometry Library) |
| |
| // Copyright (c) 2007-2011 Barend Gehrels, Amsterdam, the Netherlands. |
| // Copyright (c) 2008-2011 Bruno Lalande, Paris, France. |
| // Copyright (c) 2009-2011 Mateusz Loskot, London, UK. |
| |
| // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library |
| // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. |
| |
| // Use, modification and distribution is subject to the Boost Software License, |
| // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP |
| #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP |
| |
| #include <cstddef> |
| #include <vector> |
| |
| #include <boost/mpl/assert.hpp> |
| #include <boost/range.hpp> |
| #include <boost/typeof/typeof.hpp> |
| |
| #include <boost/geometry/algorithms/assign.hpp> |
| #include <boost/geometry/algorithms/expand.hpp> |
| |
| #include <boost/geometry/algorithms/detail/ring_identifier.hpp> |
| |
| #include <boost/geometry/core/access.hpp> |
| #include <boost/geometry/core/closure.hpp> |
| #include <boost/geometry/core/exterior_ring.hpp> |
| #include <boost/geometry/core/point_order.hpp> |
| |
| #include <boost/geometry/geometries/concepts/check.hpp> |
| #include <boost/geometry/util/math.hpp> |
| #include <boost/geometry/views/closeable_view.hpp> |
| #include <boost/geometry/views/reversible_view.hpp> |
| #include <boost/geometry/geometries/segment.hpp> |
| |
| |
| namespace boost { namespace geometry |
| { |
| |
| |
| /*! |
| \brief Structure containing section information |
| \details Section information consists of a bounding box, direction |
| information (if it is increasing or decreasing, per dimension), |
| index information (begin-end, ring, multi) and the number of |
| segments in this section |
| |
| \tparam Box box-type |
| \tparam DimensionCount number of dimensions for this section |
| \ingroup sectionalize |
| */ |
| template <typename Box, std::size_t DimensionCount> |
| struct section |
| { |
| typedef Box box_type; |
| |
| int id; // might be obsolete now, BSG 14-03-2011 TODO decide about this |
| |
| int directions[DimensionCount]; |
| ring_identifier ring_id; |
| Box bounding_box; |
| |
| int begin_index; |
| int end_index; |
| std::size_t count; |
| std::size_t range_count; |
| bool duplicate; |
| int non_duplicate_index; |
| |
| inline section() |
| : id(-1) |
| , begin_index(-1) |
| , end_index(-1) |
| , count(0) |
| , range_count(0) |
| , duplicate(false) |
| , non_duplicate_index(-1) |
| { |
| assign_inverse(bounding_box); |
| for (register std::size_t i = 0; i < DimensionCount; i++) |
| { |
| directions[i] = 0; |
| } |
| } |
| }; |
| |
| |
| /*! |
| \brief Structure containing a collection of sections |
| \note Derived from a vector, proves to be faster than of deque |
| \note vector might be templated in the future |
| \ingroup sectionalize |
| */ |
| template <typename Box, std::size_t DimensionCount> |
| struct sections : std::vector<section<Box, DimensionCount> > |
| { |
| typedef Box box_type; |
| static std::size_t const value = DimensionCount; |
| }; |
| |
| |
| #ifndef DOXYGEN_NO_DETAIL |
| namespace detail { namespace sectionalize |
| { |
| |
| template <typename Segment, std::size_t Dimension, std::size_t DimensionCount> |
| struct get_direction_loop |
| { |
| typedef typename coordinate_type<Segment>::type coordinate_type; |
| |
| static inline void apply(Segment const& seg, |
| int directions[DimensionCount]) |
| { |
| coordinate_type const diff = |
| geometry::get<1, Dimension>(seg) - geometry::get<0, Dimension>(seg); |
| |
| coordinate_type zero = coordinate_type(); |
| directions[Dimension] = diff > zero ? 1 : diff < zero ? -1 : 0; |
| |
| get_direction_loop |
| < |
| Segment, Dimension + 1, DimensionCount |
| >::apply(seg, directions); |
| } |
| }; |
| |
| template <typename Segment, std::size_t DimensionCount> |
| struct get_direction_loop<Segment, DimensionCount, DimensionCount> |
| { |
| static inline void apply(Segment const&, int [DimensionCount]) |
| {} |
| }; |
| |
| template <typename T, std::size_t Dimension, std::size_t DimensionCount> |
| struct copy_loop |
| { |
| static inline void apply(T const source[DimensionCount], |
| T target[DimensionCount]) |
| { |
| target[Dimension] = source[Dimension]; |
| copy_loop<T, Dimension + 1, DimensionCount>::apply(source, target); |
| } |
| }; |
| |
| template <typename T, std::size_t DimensionCount> |
| struct copy_loop<T, DimensionCount, DimensionCount> |
| { |
| static inline void apply(T const [DimensionCount], T [DimensionCount]) |
| {} |
| }; |
| |
| template <typename T, std::size_t Dimension, std::size_t DimensionCount> |
| struct compare_loop |
| { |
| static inline bool apply(T const source[DimensionCount], |
| T const target[DimensionCount]) |
| { |
| bool const not_equal = target[Dimension] != source[Dimension]; |
| |
| return not_equal |
| ? false |
| : compare_loop |
| < |
| T, Dimension + 1, DimensionCount |
| >::apply(source, target); |
| } |
| }; |
| |
| template <typename T, std::size_t DimensionCount> |
| struct compare_loop<T, DimensionCount, DimensionCount> |
| { |
| static inline bool apply(T const [DimensionCount], |
| T const [DimensionCount]) |
| { |
| |
| return true; |
| } |
| }; |
| |
| |
| template <typename Segment, std::size_t Dimension, std::size_t DimensionCount> |
| struct check_duplicate_loop |
| { |
| typedef typename coordinate_type<Segment>::type coordinate_type; |
| |
| static inline bool apply(Segment const& seg) |
| { |
| coordinate_type const diff = |
| geometry::get<1, Dimension>(seg) - geometry::get<0, Dimension>(seg); |
| |
| coordinate_type const zero = 0; |
| if (! geometry::math::equals(diff, zero)) |
| { |
| return false; |
| } |
| |
| return check_duplicate_loop |
| < |
| Segment, Dimension + 1, DimensionCount |
| >::apply(seg); |
| } |
| }; |
| |
| template <typename Segment, std::size_t DimensionCount> |
| struct check_duplicate_loop<Segment, DimensionCount, DimensionCount> |
| { |
| static inline bool apply(Segment const&) |
| { |
| return true; |
| } |
| }; |
| |
| template <typename T, std::size_t Dimension, std::size_t DimensionCount> |
| struct assign_loop |
| { |
| static inline void apply(T dims[DimensionCount], int const value) |
| { |
| dims[Dimension] = value; |
| assign_loop<T, Dimension + 1, DimensionCount>::apply(dims, value); |
| } |
| }; |
| |
| template <typename T, std::size_t DimensionCount> |
| struct assign_loop<T, DimensionCount, DimensionCount> |
| { |
| static inline void apply(T [DimensionCount], int const) |
| { |
| } |
| }; |
| |
| /// @brief Helper class to create sections of a part of a range, on the fly |
| template |
| < |
| typename Range, // Can be closeable_view |
| typename Point, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize_part |
| { |
| typedef model::referring_segment<Point const> segment_type; |
| typedef typename boost::range_value<Sections>::type section_type; |
| |
| typedef typename boost::range_iterator<Range const>::type iterator_type; |
| |
| static inline void apply(Sections& sections, section_type& section, |
| int& index, int& ndi, |
| Range const& range, |
| ring_identifier ring_id) |
| { |
| if (boost::size(range) <= index) |
| { |
| return; |
| } |
| |
| if (index == 0) |
| { |
| ndi = 0; |
| } |
| |
| iterator_type it = boost::begin(range); |
| it += index; |
| |
| for(iterator_type previous = it++; |
| it != boost::end(range); |
| ++previous, ++it, index++) |
| { |
| segment_type segment(*previous, *it); |
| |
| int direction_classes[DimensionCount] = {0}; |
| get_direction_loop |
| < |
| segment_type, 0, DimensionCount |
| >::apply(segment, direction_classes); |
| |
| // if "dir" == 0 for all point-dimensions, it is duplicate. |
| // Those sections might be omitted, if wished, lateron |
| bool duplicate = false; |
| |
| if (direction_classes[0] == 0) |
| { |
| // Recheck because ALL dimensions should be checked, |
| // not only first one. |
| // (DimensionCount might be < dimension<P>::value) |
| if (check_duplicate_loop |
| < |
| segment_type, 0, geometry::dimension<Point>::type::value |
| >::apply(segment) |
| ) |
| { |
| duplicate = true; |
| |
| // Change direction-info to force new section |
| // Note that wo consecutive duplicate segments will generate |
| // only one duplicate-section. |
| // Actual value is not important as long as it is not -1,0,1 |
| assign_loop |
| < |
| int, 0, DimensionCount |
| >::apply(direction_classes, -99); |
| } |
| } |
| |
| if (section.count > 0 |
| && (!compare_loop |
| < |
| int, 0, DimensionCount |
| >::apply(direction_classes, section.directions) |
| || section.count > MaxCount |
| ) |
| ) |
| { |
| sections.push_back(section); |
| section = section_type(); |
| } |
| |
| if (section.count == 0) |
| { |
| section.begin_index = index; |
| section.ring_id = ring_id; |
| section.duplicate = duplicate; |
| section.non_duplicate_index = ndi; |
| section.range_count = boost::size(range); |
| |
| copy_loop |
| < |
| int, 0, DimensionCount |
| >::apply(direction_classes, section.directions); |
| geometry::expand(section.bounding_box, *previous); |
| } |
| |
| geometry::expand(section.bounding_box, *it); |
| section.end_index = index + 1; |
| section.count++; |
| if (! duplicate) |
| { |
| ndi++; |
| } |
| } |
| } |
| }; |
| |
| |
| template |
| < |
| typename Range, closure_selector Closure, bool Reverse, |
| typename Point, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize_range |
| { |
| typedef typename closeable_view<Range const, Closure>::type cview_type; |
| typedef typename reversible_view |
| < |
| cview_type const, |
| Reverse ? iterate_reverse : iterate_forward |
| >::type view_type; |
| |
| static inline void apply(Range const& range, Sections& sections, |
| ring_identifier ring_id) |
| { |
| typedef model::referring_segment<Point const> segment_type; |
| |
| cview_type cview(range); |
| view_type view(cview); |
| |
| std::size_t const n = boost::size(view); |
| if (n == 0) |
| { |
| // Zero points, no section |
| return; |
| } |
| |
| if (n == 1) |
| { |
| // Line with one point ==> no sections |
| return; |
| } |
| |
| int index = 0; |
| int ndi = 0; // non duplicate index |
| |
| typedef typename boost::range_value<Sections>::type section_type; |
| section_type section; |
| |
| sectionalize_part |
| < |
| view_type, Point, Sections, |
| DimensionCount, MaxCount |
| >::apply(sections, section, index, ndi, |
| view, ring_id); |
| |
| // Add last section if applicable |
| if (section.count > 0) |
| { |
| sections.push_back(section); |
| } |
| } |
| }; |
| |
| template |
| < |
| typename Polygon, |
| bool Reverse, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize_polygon |
| { |
| static inline void apply(Polygon const& poly, Sections& sections, |
| ring_identifier ring_id) |
| { |
| typedef typename point_type<Polygon>::type point_type; |
| typedef typename ring_type<Polygon>::type ring_type; |
| typedef sectionalize_range |
| < |
| ring_type, closure<Polygon>::value, Reverse, |
| point_type, Sections, DimensionCount, MaxCount |
| > sectionalizer_type; |
| |
| ring_id.ring_index = -1; |
| sectionalizer_type::apply(exterior_ring(poly), sections, ring_id);//-1, multi_index); |
| |
| ring_id.ring_index++; |
| typename interior_return_type<Polygon const>::type rings |
| = interior_rings(poly); |
| for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); |
| ++it, ++ring_id.ring_index) |
| { |
| sectionalizer_type::apply(*it, sections, ring_id); |
| } |
| } |
| }; |
| |
| template |
| < |
| typename Box, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize_box |
| { |
| static inline void apply(Box const& box, Sections& sections, ring_identifier const& ring_id) |
| { |
| typedef typename point_type<Box>::type point_type; |
| |
| assert_dimension<Box, 2>(); |
| |
| // Add all four sides of the 2D-box as separate section. |
| // Easiest is to convert it to a polygon. |
| // However, we don't have the polygon type |
| // (or polygon would be a helper-type). |
| // Therefore we mimic a linestring/std::vector of 5 points |
| |
| // TODO: might be replaced by assign_box_corners_oriented |
| // or just "convert" |
| point_type ll, lr, ul, ur; |
| geometry::detail::assign_box_corners(box, ll, lr, ul, ur); |
| |
| std::vector<point_type> points; |
| points.push_back(ll); |
| points.push_back(ul); |
| points.push_back(ur); |
| points.push_back(lr); |
| points.push_back(ll); |
| |
| sectionalize_range |
| < |
| std::vector<point_type>, closed, false, |
| point_type, |
| Sections, |
| DimensionCount, |
| MaxCount |
| >::apply(points, sections, ring_id); |
| } |
| }; |
| |
| template <typename Sections> |
| inline void set_section_unique_ids(Sections& sections) |
| { |
| // Set ID's. |
| int index = 0; |
| for (typename boost::range_iterator<Sections>::type it = boost::begin(sections); |
| it != boost::end(sections); |
| ++it) |
| { |
| it->id = index++; |
| } |
| } |
| |
| |
| }} // namespace detail::sectionalize |
| #endif // DOXYGEN_NO_DETAIL |
| |
| |
| #ifndef DOXYGEN_NO_DISPATCH |
| namespace dispatch |
| { |
| |
| template |
| < |
| typename Tag, |
| typename Geometry, |
| bool Reverse, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize |
| { |
| BOOST_MPL_ASSERT_MSG |
| ( |
| false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE |
| , (types<Geometry>) |
| ); |
| }; |
| |
| template |
| < |
| typename Box, |
| bool Reverse, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize<box_tag, Box, Reverse, Sections, DimensionCount, MaxCount> |
| : detail::sectionalize::sectionalize_box |
| < |
| Box, |
| Sections, |
| DimensionCount, |
| MaxCount |
| > |
| {}; |
| |
| template |
| < |
| typename LineString, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize |
| < |
| linestring_tag, |
| LineString, |
| false, |
| Sections, |
| DimensionCount, |
| MaxCount |
| > |
| : detail::sectionalize::sectionalize_range |
| < |
| LineString, closed, false, |
| typename point_type<LineString>::type, |
| Sections, |
| DimensionCount, |
| MaxCount |
| > |
| {}; |
| |
| template |
| < |
| typename Ring, |
| bool Reverse, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize<ring_tag, Ring, Reverse, Sections, DimensionCount, MaxCount> |
| : detail::sectionalize::sectionalize_range |
| < |
| Ring, geometry::closure<Ring>::value, Reverse, |
| typename point_type<Ring>::type, |
| Sections, |
| DimensionCount, |
| MaxCount |
| > |
| {}; |
| |
| template |
| < |
| typename Polygon, |
| bool Reverse, |
| typename Sections, |
| std::size_t DimensionCount, |
| std::size_t MaxCount |
| > |
| struct sectionalize<polygon_tag, Polygon, Reverse, Sections, DimensionCount, MaxCount> |
| : detail::sectionalize::sectionalize_polygon |
| < |
| Polygon, Reverse, Sections, DimensionCount, MaxCount |
| > |
| {}; |
| |
| } // namespace dispatch |
| #endif |
| |
| |
| /*! |
| \brief Split a geometry into monotonic sections |
| \ingroup sectionalize |
| \tparam Geometry type of geometry to check |
| \tparam Sections type of sections to create |
| \param geometry geometry to create sections from |
| \param sections structure with sections |
| \param source_index index to assign to the ring_identifiers |
| */ |
| template<bool Reverse, typename Geometry, typename Sections> |
| inline void sectionalize(Geometry const& geometry, Sections& sections, int source_index = 0) |
| { |
| concept::check<Geometry const>(); |
| |
| // TODO: review use of this constant (see below) as causing problems with GCC 4.6 --mloskot |
| // A maximum of 10 segments per section seems to give the fastest results |
| //static std::size_t const max_segments_per_section = 10; |
| typedef dispatch::sectionalize |
| < |
| typename tag<Geometry>::type, |
| Geometry, |
| Reverse, |
| Sections, |
| Sections::value, |
| 10 // TODO: max_segments_per_section |
| > sectionalizer_type; |
| |
| sections.clear(); |
| ring_identifier ring_id; |
| ring_id.source_index = source_index; |
| sectionalizer_type::apply(geometry, sections, ring_id); |
| detail::sectionalize::set_section_unique_ids(sections); |
| } |
| |
| |
| }} // namespace boost::geometry |
| |
| |
| #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_SECTIONS_SECTIONALIZE_HPP |