1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France. 5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. 6 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. 7 8 // This file was modified by Oracle on 2013-2017. 9 // Modifications copyright (c) 2013-2017, 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_DISJOINT_LINEAR_LINEAR_HPP 22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_LINEAR_HPP 23 24 #include <cstddef> 25 #include <deque> 26 27 #include <boost/range.hpp> 28 #include <boost/geometry/util/range.hpp> 29 30 #include <boost/geometry/core/point_type.hpp> 31 #include <boost/geometry/core/tag.hpp> 32 #include <boost/geometry/core/tags.hpp> 33 34 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 35 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> 36 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> 37 #include <boost/geometry/algorithms/detail/overlay/segment_as_subrange.hpp> 38 39 #include <boost/geometry/policies/disjoint_interrupt_policy.hpp> 40 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> 41 42 #include <boost/geometry/algorithms/dispatch/disjoint.hpp> 43 44 45 namespace boost { namespace geometry 46 { 47 48 49 #ifndef DOXYGEN_NO_DETAIL 50 namespace detail { namespace disjoint 51 { 52 53 template <typename Segment1, typename Segment2> 54 struct disjoint_segment 55 { 56 template <typename Strategy> applyboost::geometry::detail::disjoint::disjoint_segment57 static inline bool apply(Segment1 const& segment1, Segment2 const& segment2, 58 Strategy const& strategy) 59 { 60 typedef typename point_type<Segment1>::type point_type; 61 62 typedef segment_intersection_points<point_type> intersection_return_type; 63 64 typedef policies::relate::segments_intersection_points 65 < 66 intersection_return_type 67 > intersection_policy; 68 69 detail::segment_as_subrange<Segment1> sub_range1(segment1); 70 detail::segment_as_subrange<Segment2> sub_range2(segment2); 71 intersection_return_type is = strategy.apply(sub_range1, sub_range2, 72 intersection_policy()); 73 74 return is.count == 0; 75 } 76 }; 77 78 79 struct assign_disjoint_policy 80 { 81 // We want to include all points: 82 static bool const include_no_turn = true; 83 static bool const include_degenerate = true; 84 static bool const include_opposite = true; 85 }; 86 87 88 template <typename Geometry1, typename Geometry2> 89 struct disjoint_linear 90 { 91 template <typename Strategy> applyboost::geometry::detail::disjoint::disjoint_linear92 static inline bool apply(Geometry1 const& geometry1, 93 Geometry2 const& geometry2, 94 Strategy const& strategy) 95 { 96 typedef typename geometry::point_type<Geometry1>::type point_type; 97 typedef geometry::segment_ratio 98 < 99 typename coordinate_type<point_type>::type 100 > ratio_type; 101 typedef overlay::turn_info 102 < 103 point_type, 104 ratio_type, 105 typename detail::get_turns::turn_operation_type 106 < 107 Geometry1, Geometry2, ratio_type 108 >::type 109 > turn_info_type; 110 111 std::deque<turn_info_type> turns; 112 113 // Specify two policies: 114 // 1) Stop at any intersection 115 // 2) In assignment, include also degenerate points (which are normally skipped) 116 disjoint_interrupt_policy interrupt_policy; 117 dispatch::get_turns 118 < 119 typename geometry::tag<Geometry1>::type, 120 typename geometry::tag<Geometry2>::type, 121 Geometry1, 122 Geometry2, 123 overlay::do_reverse<geometry::point_order<Geometry1>::value>::value, // should be false 124 overlay::do_reverse<geometry::point_order<Geometry2>::value>::value, // should be false 125 detail::get_turns::get_turn_info_type 126 < 127 Geometry1, Geometry2, assign_disjoint_policy 128 > 129 >::apply(0, geometry1, 1, geometry2, 130 strategy, detail::no_rescale_policy(), turns, interrupt_policy); 131 132 return !interrupt_policy.has_intersections; 133 } 134 }; 135 136 137 }} // namespace detail::disjoint 138 #endif // DOXYGEN_NO_DETAIL 139 140 141 142 143 #ifndef DOXYGEN_NO_DISPATCH 144 namespace dispatch 145 { 146 147 148 template <typename Linear1, typename Linear2> 149 struct disjoint<Linear1, Linear2, 2, linear_tag, linear_tag, false> 150 : detail::disjoint::disjoint_linear<Linear1, Linear2> 151 {}; 152 153 154 template <typename Segment1, typename Segment2> 155 struct disjoint<Segment1, Segment2, 2, segment_tag, segment_tag, false> 156 : detail::disjoint::disjoint_segment<Segment1, Segment2> 157 {}; 158 159 160 } // namespace dispatch 161 #endif // DOXYGEN_NO_DISPATCH 162 163 164 }} // namespace boost::geometry 165 166 167 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_LINEAR_HPP 168