Chris@102: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@102: 
Chris@102: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@102: 
Chris@102: // This file was modified by Oracle on 2014.
Chris@102: // Modifications copyright (c) 2014, Oracle and/or its affiliates.
Chris@102: 
Chris@102: // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
Chris@102: 
Chris@102: // Use, modification and distribution is subject to the Boost Software License,
Chris@102: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@102: // http://www.boost.org/LICENSE_1_0.txt)
Chris@102: 
Chris@102: #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
Chris@102: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
Chris@102: 
Chris@102: #include <boost/geometry/core/closure.hpp>
Chris@102: #include <boost/geometry/core/geometry_id.hpp>
Chris@102: #include <boost/geometry/core/is_areal.hpp>
Chris@102: #include <boost/geometry/core/point_order.hpp>
Chris@102: #include <boost/geometry/core/tags.hpp>
Chris@102: #include <boost/geometry/geometries/concepts/check.hpp>
Chris@102: 
Chris@102: // TODO: those headers probably may be removed
Chris@102: #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/algorithms/detail/intersection/interface.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/algorithms/covered_by.hpp>
Chris@102: #include <boost/geometry/algorithms/envelope.hpp>
Chris@102: #include <boost/geometry/algorithms/num_points.hpp>
Chris@102: 
Chris@102: // TODO: remove this after moving num_point from multi directory
Chris@102: #include <boost/geometry/multi/algorithms/num_points.hpp>
Chris@102: 
Chris@102: namespace boost { namespace geometry
Chris@102: {
Chris@102: 
Chris@102: #ifndef DOXYGEN_NO_DETAIL
Chris@102: namespace detail { namespace intersection
Chris@102: {
Chris@102: 
Chris@102: 
Chris@102: template <typename PointOut>
Chris@102: struct intersection_multi_linestring_multi_linestring_point
Chris@102: {
Chris@102:     template
Chris@102:     <
Chris@102:         typename MultiLinestring1, typename MultiLinestring2,
Chris@102:         typename RobustPolicy,
Chris@102:         typename OutputIterator, typename Strategy
Chris@102:     >
Chris@102:     static inline OutputIterator apply(MultiLinestring1 const& ml1,
Chris@102:             MultiLinestring2 const& ml2,
Chris@102:             RobustPolicy const& robust_policy,
Chris@102:             OutputIterator out,
Chris@102:             Strategy const& strategy)
Chris@102:     {
Chris@102:         // Note, this loop is quadratic w.r.t. number of linestrings per input.
Chris@102:         // Future Enhancement: first do the sections of each, then intersect.
Chris@102:         for (typename boost::range_iterator
Chris@102:                 <
Chris@102:                     MultiLinestring1 const
Chris@102:                 >::type it1 = boost::begin(ml1);
Chris@102:             it1 != boost::end(ml1);
Chris@102:             ++it1)
Chris@102:         {
Chris@102:             for (typename boost::range_iterator
Chris@102:                     <
Chris@102:                         MultiLinestring2 const
Chris@102:                     >::type it2 = boost::begin(ml2);
Chris@102:                 it2 != boost::end(ml2);
Chris@102:                 ++it2)
Chris@102:             {
Chris@102:                 out = intersection_linestring_linestring_point<PointOut>
Chris@102:                       ::apply(*it1, *it2, robust_policy, out, strategy);
Chris@102:             }
Chris@102:         }
Chris@102: 
Chris@102:         return out;
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: template <typename PointOut>
Chris@102: struct intersection_linestring_multi_linestring_point
Chris@102: {
Chris@102:     template
Chris@102:     <
Chris@102:         typename Linestring, typename MultiLinestring,
Chris@102:         typename RobustPolicy,
Chris@102:         typename OutputIterator, typename Strategy
Chris@102:     >
Chris@102:     static inline OutputIterator apply(Linestring const& linestring,
Chris@102:             MultiLinestring const& ml,
Chris@102:             RobustPolicy const& robust_policy,
Chris@102:             OutputIterator out,
Chris@102:             Strategy const& strategy)
Chris@102:     {
Chris@102:         for (typename boost::range_iterator
Chris@102:                 <
Chris@102:                     MultiLinestring const
Chris@102:                 >::type it = boost::begin(ml);
Chris@102:             it != boost::end(ml);
Chris@102:             ++it)
Chris@102:         {
Chris@102:             out = intersection_linestring_linestring_point<PointOut>
Chris@102:                   ::apply(linestring, *it, robust_policy, out, strategy);
Chris@102:         }
Chris@102: 
Chris@102:         return out;
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: // This loop is quite similar to the loop above, but beacuse the iterator
Chris@102: // is second (above) or first (below) argument, it is not trivial to merge them.
Chris@102: template
Chris@102: <
Chris@102:     bool ReverseAreal,
Chris@102:     typename LineStringOut,
Chris@102:     overlay_type OverlayType
Chris@102: >
Chris@102: struct intersection_of_multi_linestring_with_areal
Chris@102: {
Chris@102:     template
Chris@102:     <
Chris@102:         typename MultiLinestring, typename Areal,
Chris@102:         typename RobustPolicy,
Chris@102:         typename OutputIterator, typename Strategy
Chris@102:     >
Chris@102:     static inline OutputIterator apply(MultiLinestring const& ml, Areal const& areal,
Chris@102:             RobustPolicy const& robust_policy,
Chris@102:             OutputIterator out,
Chris@102:             Strategy const& strategy)
Chris@102:     {
Chris@102:         for (typename boost::range_iterator
Chris@102:                 <
Chris@102:                     MultiLinestring const
Chris@102:                 >::type it = boost::begin(ml);
Chris@102:             it != boost::end(ml);
Chris@102:             ++it)
Chris@102:         {
Chris@102:             out = intersection_of_linestring_with_areal
Chris@102:                 <
Chris@102:                     ReverseAreal, LineStringOut, OverlayType
Chris@102:                 >::apply(*it, areal, robust_policy, out, strategy);
Chris@102:         }
Chris@102: 
Chris@102:         return out;
Chris@102: 
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: // This one calls the one above with reversed arguments
Chris@102: template
Chris@102: <
Chris@102:     bool ReverseAreal,
Chris@102:     typename LineStringOut,
Chris@102:     overlay_type OverlayType
Chris@102: >
Chris@102: struct intersection_of_areal_with_multi_linestring
Chris@102: {
Chris@102:     template
Chris@102:     <
Chris@102:         typename Areal, typename MultiLinestring,
Chris@102:         typename RobustPolicy,
Chris@102:         typename OutputIterator, typename Strategy
Chris@102:     >
Chris@102:     static inline OutputIterator apply(Areal const& areal, MultiLinestring const& ml,
Chris@102:             RobustPolicy const& robust_policy,
Chris@102:             OutputIterator out,
Chris@102:             Strategy const& strategy)
Chris@102:     {
Chris@102:         return intersection_of_multi_linestring_with_areal
Chris@102:             <
Chris@102:                 ReverseAreal, LineStringOut, OverlayType
Chris@102:             >::apply(ml, areal, robust_policy, out, strategy);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: 
Chris@102: template <typename LinestringOut>
Chris@102: struct clip_multi_linestring
Chris@102: {
Chris@102:     template
Chris@102:     <
Chris@102:         typename MultiLinestring, typename Box,
Chris@102:         typename RobustPolicy,
Chris@102:         typename OutputIterator, typename Strategy
Chris@102:     >
Chris@102:     static inline OutputIterator apply(MultiLinestring const& multi_linestring,
Chris@102:             Box const& box,
Chris@102:             RobustPolicy const& robust_policy,
Chris@102:             OutputIterator out, Strategy const& )
Chris@102:     {
Chris@102:         typedef typename point_type<LinestringOut>::type point_type;
Chris@102:         strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
Chris@102:         for (typename boost::range_iterator<MultiLinestring const>::type it
Chris@102:             = boost::begin(multi_linestring);
Chris@102:             it != boost::end(multi_linestring); ++it)
Chris@102:         {
Chris@102:             out = detail::intersection::clip_range_with_box
Chris@102:                 <LinestringOut>(box, *it, robust_policy, out, lb_strategy);
Chris@102:         }
Chris@102:         return out;
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: 
Chris@102: }} // namespace detail::intersection
Chris@102: #endif // DOXYGEN_NO_DETAIL
Chris@102: 
Chris@102: 
Chris@102: #ifndef DOXYGEN_NO_DISPATCH
Chris@102: namespace dispatch
Chris@102: {
Chris@102: 
Chris@102: 
Chris@102: // Linear
Chris@102: template
Chris@102: <
Chris@102:     typename MultiLinestring1, typename MultiLinestring2,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         MultiLinestring1, MultiLinestring2,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         Reverse1, Reverse2, ReverseOut,
Chris@102:         multi_linestring_tag, multi_linestring_tag, point_tag,
Chris@102:         false, false, false
Chris@102:     > : detail::intersection::intersection_multi_linestring_multi_linestring_point
Chris@102:             <
Chris@102:                 GeometryOut
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename Linestring, typename MultiLinestring,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         Linestring, MultiLinestring,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         Reverse1, Reverse2, ReverseOut,
Chris@102:         linestring_tag, multi_linestring_tag, point_tag,
Chris@102:         false, false, false
Chris@102:     > : detail::intersection::intersection_linestring_multi_linestring_point
Chris@102:             <
Chris@102:                 GeometryOut
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename MultiLinestring, typename Box,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool Reverse1, bool Reverse2, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         MultiLinestring, Box,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         Reverse1, Reverse2, ReverseOut,
Chris@102:         multi_linestring_tag, box_tag, linestring_tag,
Chris@102:         false, true, false
Chris@102:     > : detail::intersection::clip_multi_linestring
Chris@102:             <
Chris@102:                 GeometryOut
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename Linestring, typename MultiPolygon,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool ReverseLinestring, bool ReverseMultiPolygon, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         Linestring, MultiPolygon,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         ReverseLinestring, ReverseMultiPolygon, ReverseOut,
Chris@102:         linestring_tag, multi_polygon_tag, linestring_tag,
Chris@102:         false, true, false
Chris@102:     > : detail::intersection::intersection_of_linestring_with_areal
Chris@102:             <
Chris@102:                 ReverseMultiPolygon,
Chris@102:                 GeometryOut,
Chris@102:                 OverlayType
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: // Derives from areal/mls because runtime arguments are in that order.
Chris@102: // areal/mls reverses it itself to mls/areal
Chris@102: template
Chris@102: <
Chris@102:     typename Polygon, typename MultiLinestring,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool ReversePolygon, bool ReverseMultiLinestring, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         Polygon, MultiLinestring,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         ReversePolygon, ReverseMultiLinestring, ReverseOut,
Chris@102:         polygon_tag, multi_linestring_tag, linestring_tag,
Chris@102:         true, false, false
Chris@102:     > : detail::intersection::intersection_of_areal_with_multi_linestring
Chris@102:             <
Chris@102:                 ReversePolygon,
Chris@102:                 GeometryOut,
Chris@102:                 OverlayType
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename MultiLinestring, typename Ring,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         MultiLinestring, Ring,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         ReverseMultiLinestring, ReverseRing, ReverseOut,
Chris@102:         multi_linestring_tag, ring_tag, linestring_tag,
Chris@102:         false, true, false
Chris@102:     > : detail::intersection::intersection_of_multi_linestring_with_areal
Chris@102:             <
Chris@102:                 ReverseRing,
Chris@102:                 GeometryOut,
Chris@102:                 OverlayType
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename MultiLinestring, typename Polygon,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         MultiLinestring, Polygon,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         ReverseMultiLinestring, ReverseRing, ReverseOut,
Chris@102:         multi_linestring_tag, polygon_tag, linestring_tag,
Chris@102:         false, true, false
Chris@102:     > : detail::intersection::intersection_of_multi_linestring_with_areal
Chris@102:             <
Chris@102:                 ReverseRing,
Chris@102:                 GeometryOut,
Chris@102:                 OverlayType
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename MultiLinestring, typename MultiPolygon,
Chris@102:     typename GeometryOut,
Chris@102:     overlay_type OverlayType,
Chris@102:     bool ReverseMultiLinestring, bool ReverseMultiPolygon, bool ReverseOut
Chris@102: >
Chris@102: struct intersection_insert
Chris@102:     <
Chris@102:         MultiLinestring, MultiPolygon,
Chris@102:         GeometryOut,
Chris@102:         OverlayType,
Chris@102:         ReverseMultiLinestring, ReverseMultiPolygon, ReverseOut,
Chris@102:         multi_linestring_tag, multi_polygon_tag, linestring_tag,
Chris@102:         false, true, false
Chris@102:     > : detail::intersection::intersection_of_multi_linestring_with_areal
Chris@102:             <
Chris@102:                 ReverseMultiPolygon,
Chris@102:                 GeometryOut,
Chris@102:                 OverlayType
Chris@102:             >
Chris@102: {};
Chris@102: 
Chris@102: 
Chris@102: } // namespace dispatch
Chris@102: #endif
Chris@102: 
Chris@102: }} // namespace boost::geometry
Chris@102: 
Chris@102: 
Chris@102: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
Chris@102: