| // Boost.Geometry (aka GGL, Generic Geometry Library) |
| |
| // Copyright (c) 2007-2011 Barend Gehrels, 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_OVERLAY_INTERSECTION_INSERT_HPP |
| #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP |
| |
| |
| #include <cstddef> |
| |
| #include <boost/mpl/if.hpp> |
| #include <boost/mpl/assert.hpp> |
| #include <boost/range/metafunctions.hpp> |
| |
| |
| #include <boost/geometry/core/is_areal.hpp> |
| #include <boost/geometry/core/point_order.hpp> |
| #include <boost/geometry/core/reverse_dispatch.hpp> |
| #include <boost/geometry/geometries/concepts/check.hpp> |
| #include <boost/geometry/algorithms/convert.hpp> |
| #include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp> |
| #include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp> |
| #include <boost/geometry/algorithms/detail/overlay/overlay.hpp> |
| #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> |
| #include <boost/geometry/views/segment_view.hpp> |
| |
| |
| namespace boost { namespace geometry |
| { |
| |
| #ifndef DOXYGEN_NO_DETAIL |
| namespace detail { namespace intersection |
| { |
| |
| template |
| < |
| typename Segment1, typename Segment2, |
| typename OutputIterator, typename PointOut, |
| typename Strategy |
| > |
| struct intersection_segment_segment_point |
| { |
| static inline OutputIterator apply(Segment1 const& segment1, |
| Segment2 const& segment2, OutputIterator out, |
| Strategy const& strategy) |
| { |
| typedef typename point_type<PointOut>::type point_type; |
| |
| // Get the intersection point (or two points) |
| segment_intersection_points<point_type> is |
| = strategy::intersection::relate_cartesian_segments |
| < |
| policies::relate::segments_intersection_points |
| < |
| Segment1, |
| Segment2, |
| segment_intersection_points<point_type> |
| > |
| >::apply(segment1, segment2); |
| |
| for (std::size_t i = 0; i < is.count; i++) |
| { |
| PointOut p; |
| geometry::convert(is.intersections[i], p); |
| *out++ = p; |
| } |
| return out; |
| } |
| }; |
| |
| template |
| < |
| typename Linestring1, typename Linestring2, |
| typename OutputIterator, typename PointOut, |
| typename Strategy |
| > |
| struct intersection_linestring_linestring_point |
| { |
| static inline OutputIterator apply(Linestring1 const& linestring1, |
| Linestring2 const& linestring2, OutputIterator out, |
| Strategy const& strategy) |
| { |
| typedef typename point_type<PointOut>::type point_type; |
| |
| typedef detail::overlay::turn_info<point_type> turn_info; |
| std::deque<turn_info> turns; |
| |
| geometry::get_intersection_points(linestring1, linestring2, turns); |
| |
| for (typename boost::range_iterator<std::deque<turn_info> const>::type |
| it = boost::begin(turns); it != boost::end(turns); ++it) |
| { |
| PointOut p; |
| geometry::convert(it->point, p); |
| *out++ = p; |
| } |
| return out; |
| } |
| }; |
| |
| }} // namespace detail::intersection |
| #endif // DOXYGEN_NO_DETAIL |
| |
| |
| |
| #ifndef DOXYGEN_NO_DISPATCH |
| namespace dispatch |
| { |
| |
| template |
| < |
| // tag dispatching: |
| typename TagIn1, typename TagIn2, typename TagOut, |
| // orientation |
| // metafunction finetuning helpers: |
| bool Areal1, bool Areal2, bool ArealOut, |
| // real types |
| typename Geometry1, typename Geometry2, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, |
| typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert |
| { |
| BOOST_MPL_ASSERT_MSG |
| ( |
| false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPES_OR_ORIENTATIONS |
| , (types<Geometry1, Geometry2, GeometryOut>) |
| ); |
| }; |
| |
| |
| template |
| < |
| typename TagIn1, typename TagIn2, typename TagOut, |
| typename Geometry1, typename Geometry2, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, |
| typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert |
| < |
| TagIn1, TagIn2, TagOut, |
| true, true, true, |
| Geometry1, Geometry2, |
| Reverse1, Reverse2, ReverseOut, |
| OutputIterator, GeometryOut, |
| OverlayType, |
| Strategy |
| > : detail::overlay::overlay |
| <Geometry1, Geometry2, Reverse1, Reverse2, ReverseOut, OutputIterator, GeometryOut, OverlayType, Strategy> |
| {}; |
| |
| |
| // Any areal type with box: |
| template |
| < |
| typename TagIn, typename TagOut, |
| typename Geometry, typename Box, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, |
| typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert |
| < |
| TagIn, box_tag, TagOut, |
| true, true, true, |
| Geometry, Box, |
| Reverse1, Reverse2, ReverseOut, |
| OutputIterator, GeometryOut, |
| OverlayType, |
| Strategy |
| > : detail::overlay::overlay |
| <Geometry, Box, Reverse1, Reverse2, ReverseOut, OutputIterator, GeometryOut, OverlayType, Strategy> |
| {}; |
| |
| |
| template |
| < |
| typename Segment1, typename Segment2, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert |
| < |
| segment_tag, segment_tag, point_tag, |
| false, false, false, |
| Segment1, Segment2, |
| Reverse1, Reverse2, ReverseOut, |
| OutputIterator, GeometryOut, |
| OverlayType, Strategy |
| > : detail::intersection::intersection_segment_segment_point |
| < |
| Segment1, Segment2, |
| OutputIterator, GeometryOut, |
| Strategy |
| > |
| {}; |
| |
| |
| template |
| < |
| typename Linestring1, typename Linestring2, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert |
| < |
| linestring_tag, linestring_tag, point_tag, |
| false, false, false, |
| Linestring1, Linestring2, |
| Reverse1, Reverse2, ReverseOut, |
| OutputIterator, GeometryOut, |
| OverlayType, Strategy |
| > : detail::intersection::intersection_linestring_linestring_point |
| < |
| Linestring1, Linestring2, |
| OutputIterator, GeometryOut, |
| Strategy |
| > |
| {}; |
| |
| |
| template |
| < |
| typename Linestring, typename Box, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert |
| < |
| linestring_tag, box_tag, linestring_tag, |
| false, true, false, |
| Linestring, Box, |
| Reverse1, Reverse2, ReverseOut, |
| OutputIterator, GeometryOut, |
| OverlayType, |
| Strategy |
| > |
| { |
| static inline OutputIterator apply(Linestring const& linestring, |
| Box const& box, OutputIterator out, Strategy const& strategy) |
| { |
| typedef typename point_type<GeometryOut>::type point_type; |
| strategy::intersection::liang_barsky<Box, point_type> lb_strategy; |
| return detail::intersection::clip_range_with_box |
| <GeometryOut>(box, linestring, out, lb_strategy); |
| } |
| }; |
| |
| template |
| < |
| typename Segment, typename Box, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert |
| < |
| segment_tag, box_tag, linestring_tag, |
| false, true, false, |
| Segment, Box, |
| Reverse1, Reverse2, ReverseOut, |
| OutputIterator, GeometryOut, |
| OverlayType, |
| Strategy |
| > |
| { |
| static inline OutputIterator apply(Segment const& segment, |
| Box const& box, OutputIterator out, Strategy const& strategy) |
| { |
| geometry::segment_view<Segment> range(segment); |
| |
| typedef typename point_type<GeometryOut>::type point_type; |
| strategy::intersection::liang_barsky<Box, point_type> lb_strategy; |
| return detail::intersection::clip_range_with_box |
| <GeometryOut>(box, range, out, lb_strategy); |
| } |
| }; |
| |
| |
| template |
| < |
| typename GeometryTag1, typename GeometryTag2, typename GeometryTag3, |
| bool Areal1, bool Areal2, bool ArealOut, |
| typename Geometry1, typename Geometry2, |
| bool Reverse1, bool Reverse2, bool ReverseOut, |
| typename OutputIterator, typename GeometryOut, |
| overlay_type OverlayType, |
| typename Strategy |
| > |
| struct intersection_insert_reversed |
| { |
| static inline OutputIterator apply(Geometry1 const& g1, |
| Geometry2 const& g2, OutputIterator out, |
| Strategy const& strategy) |
| { |
| return intersection_insert |
| < |
| GeometryTag2, GeometryTag1, GeometryTag3, |
| Areal2, Areal1, ArealOut, |
| Geometry2, Geometry1, |
| Reverse2, Reverse1, ReverseOut, |
| OutputIterator, GeometryOut, |
| OverlayType, |
| Strategy |
| >::apply(g2, g1, out, strategy); |
| } |
| }; |
| |
| |
| |
| } // namespace dispatch |
| #endif // DOXYGEN_NO_DISPATCH |
| |
| |
| #ifndef DOXYGEN_NO_DETAIL |
| namespace detail { namespace intersection |
| { |
| |
| |
| template |
| < |
| typename GeometryOut, |
| bool ReverseSecond, |
| overlay_type OverlayType, |
| typename Geometry1, typename Geometry2, |
| typename OutputIterator, |
| typename Strategy |
| > |
| inline OutputIterator insert(Geometry1 const& geometry1, |
| Geometry2 const& geometry2, |
| OutputIterator out, |
| Strategy const& strategy) |
| { |
| return boost::mpl::if_c |
| < |
| geometry::reverse_dispatch<Geometry1, Geometry2>::type::value, |
| geometry::dispatch::intersection_insert_reversed |
| < |
| typename geometry::tag<Geometry1>::type, |
| typename geometry::tag<Geometry2>::type, |
| typename geometry::tag<GeometryOut>::type, |
| geometry::is_areal<Geometry1>::value, |
| geometry::is_areal<Geometry2>::value, |
| geometry::is_areal<GeometryOut>::value, |
| Geometry1, Geometry2, |
| overlay::do_reverse<geometry::point_order<Geometry1>::value>::value, |
| overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value, |
| overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value, |
| OutputIterator, GeometryOut, |
| OverlayType, |
| Strategy |
| >, |
| geometry::dispatch::intersection_insert |
| < |
| typename geometry::tag<Geometry1>::type, |
| typename geometry::tag<Geometry2>::type, |
| typename geometry::tag<GeometryOut>::type, |
| geometry::is_areal<Geometry1>::value, |
| geometry::is_areal<Geometry2>::value, |
| geometry::is_areal<GeometryOut>::value, |
| Geometry1, Geometry2, |
| geometry::detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value, |
| geometry::detail::overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value, |
| geometry::detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value, |
| OutputIterator, GeometryOut, |
| OverlayType, |
| Strategy |
| > |
| >::type::apply(geometry1, geometry2, out, strategy); |
| } |
| |
| |
| /*! |
| \brief \brief_calc2{intersection} \brief_strategy |
| \ingroup intersection |
| \details \details_calc2{intersection_insert, spatial set theoretic intersection} |
| \brief_strategy. \details_insert{intersection} |
| \tparam GeometryOut \tparam_geometry{\p_l_or_c} |
| \tparam Geometry1 \tparam_geometry |
| \tparam Geometry2 \tparam_geometry |
| \tparam OutputIterator \tparam_out{\p_l_or_c} |
| \tparam Strategy \tparam_strategy_overlay |
| \param geometry1 \param_geometry |
| \param geometry2 \param_geometry |
| \param out \param_out{intersection} |
| \param strategy \param_strategy{intersection} |
| \return \return_out |
| |
| \qbk{distinguish,with strategy} |
| \qbk{[include reference/algorithms/intersection.qbk]} |
| */ |
| template |
| < |
| typename GeometryOut, |
| typename Geometry1, |
| typename Geometry2, |
| typename OutputIterator, |
| typename Strategy |
| > |
| inline OutputIterator intersection_insert(Geometry1 const& geometry1, |
| Geometry2 const& geometry2, |
| OutputIterator out, |
| Strategy const& strategy) |
| { |
| concept::check<Geometry1 const>(); |
| concept::check<Geometry2 const>(); |
| |
| return detail::intersection::insert |
| < |
| GeometryOut, false, overlay_intersection |
| >(geometry1, geometry2, out, strategy); |
| } |
| |
| |
| /*! |
| \brief \brief_calc2{intersection} |
| \ingroup intersection |
| \details \details_calc2{intersection_insert, spatial set theoretic intersection}. |
| \details_insert{intersection} |
| \tparam GeometryOut \tparam_geometry{\p_l_or_c} |
| \tparam Geometry1 \tparam_geometry |
| \tparam Geometry2 \tparam_geometry |
| \tparam OutputIterator \tparam_out{\p_l_or_c} |
| \param geometry1 \param_geometry |
| \param geometry2 \param_geometry |
| \param out \param_out{intersection} |
| \return \return_out |
| |
| \qbk{[include reference/algorithms/intersection.qbk]} |
| */ |
| template |
| < |
| typename GeometryOut, |
| typename Geometry1, |
| typename Geometry2, |
| typename OutputIterator |
| > |
| inline OutputIterator intersection_insert(Geometry1 const& geometry1, |
| Geometry2 const& geometry2, |
| OutputIterator out) |
| { |
| concept::check<Geometry1 const>(); |
| concept::check<Geometry2 const>(); |
| |
| typedef strategy_intersection |
| < |
| typename cs_tag<GeometryOut>::type, |
| Geometry1, |
| Geometry2, |
| typename geometry::point_type<GeometryOut>::type |
| > strategy; |
| |
| return intersection_insert<GeometryOut>(geometry1, geometry2, out, |
| strategy()); |
| } |
| |
| }} // namespace detail::intersection |
| #endif // DOXYGEN_NO_DETAIL |
| |
| |
| |
| }} // namespace boost::geometry |
| |
| |
| #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP |