detail/disjoint/linear_linear.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2013-2020.
0009 // Modifications copyright (c) 2013-2020, Oracle and/or its affiliates.
0010
0011 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0012 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0013
0014 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0015 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0016
0017 // Use, modification and distribution is subject to the Boost Software License,
0018 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0019 // http://www.boost.org/LICENSE_1_0.txt)
0020
0021 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_LINEAR_HPP
0022 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_LINEAR_HPP
0023
0024 #include <cstddef>
0025 #include <deque>
0026
0027 #include <boost/geometry/core/point_type.hpp>
0028 #include <boost/geometry/core/tag.hpp>
0029 #include <boost/geometry/core/tags.hpp>
0030
0031 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/segment_as_subrange.hpp>
0035
0036 #include <boost/geometry/geometries/helper_geometry.hpp>
0037
0038 #include <boost/geometry/policies/disjoint_interrupt_policy.hpp>
0039 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
0040
0041 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
0042
0043
0044 namespace boost { namespace geometry
0045 {
0046
0047
0048 #ifndef DOXYGEN_NO_DETAIL
0049 namespace detail { namespace disjoint
0050 {
0051
0052 template <typename Segment1, typename Segment2>
0053 struct disjoint_segment
0054 {
0055     template <typename Strategy>
0056     static inline bool apply(Segment1 const& segment1, Segment2 const& segment2,
0057                              Strategy const& strategy)
0058     {
0059         typedef typename point_type<Segment1>::type point_type;
0060
0061         typedef segment_intersection_points<point_type> intersection_return_type;
0062
0063         typedef policies::relate::segments_intersection_points
0064             <
0065                 intersection_return_type
0066             > intersection_policy;
0067
0068         detail::segment_as_subrange<Segment1> sub_range1(segment1);
0069         detail::segment_as_subrange<Segment2> sub_range2(segment2);
0070         intersection_return_type is = strategy.relate().apply(sub_range1, sub_range2,
0071                                                               intersection_policy());
0072
0073         return is.count == 0;
0074     }
0075 };
0076
0077
0078 struct assign_disjoint_policy
0079 {
0080     // We want to include all points:
0081     static bool const include_no_turn = true;
0082     static bool const include_degenerate = true;
0083     static bool const include_opposite = true;
0084     static bool const include_start_turn = false;
0085 };
0086
0087
0088 template <typename Geometry1, typename Geometry2>
0089 struct disjoint_linear
0090 {
0091     template <typename Strategy>
0092     static inline bool apply(Geometry1 const& geometry1,
0093                              Geometry2 const& geometry2,
0094                              Strategy const& strategy)
0095     {
0096         using point_type = typename geometry::point_type<Geometry1>::type;
0097         using mutable_point_type = typename helper_geometry<point_type>::type;
0098         using ratio_type = geometry::segment_ratio
0099             <
0100                 typename coordinate_type<point_type>::type
0101             > ;
0102         using turn_info_type = overlay::turn_info
0103             <
0104                 mutable_point_type,
0105                 ratio_type,
0106                 typename detail::get_turns::turn_operation_type
0107                         <
0108                             Geometry1, Geometry2, mutable_point_type, ratio_type
0109                         >::type
0110             >;
0111
0112         std::deque<turn_info_type> turns;
0113
0114         // Specify two policies:
0115         // 1) Stop at any intersection
0116         // 2) In assignment, include also degenerate points (which are normally skipped)
0117         disjoint_interrupt_policy interrupt_policy;
0118         dispatch::get_turns
0119             <
0120                 typename geometry::tag<Geometry1>::type,
0121                 typename geometry::tag<Geometry2>::type,
0122                 Geometry1,
0123                 Geometry2,
0124                 overlay::do_reverse<geometry::point_order<Geometry1>::value>::value, // should be false
0125                 overlay::do_reverse<geometry::point_order<Geometry2>::value>::value, // should be false
0126                 detail::get_turns::get_turn_info_type
0127                     <
0128                         Geometry1, Geometry2, assign_disjoint_policy
0129                     >
0130             >::apply(0, geometry1, 1, geometry2,
0131                      strategy, detail::no_rescale_policy(), turns, interrupt_policy);
0132
0133         return !interrupt_policy.has_intersections;
0134     }
0135 };
0136
0137
0138 }} // namespace detail::disjoint
0139 #endif // DOXYGEN_NO_DETAIL
0140
0141
0142
0143
0144 #ifndef DOXYGEN_NO_DISPATCH
0145 namespace dispatch
0146 {
0147
0148
0149 template <typename Linear1, typename Linear2>
0150 struct disjoint<Linear1, Linear2, 2, linear_tag, linear_tag, false>
0151     : detail::disjoint::disjoint_linear<Linear1, Linear2>
0152 {};
0153
0154
0155 template <typename Segment1, typename Segment2>
0156 struct disjoint<Segment1, Segment2, 2, segment_tag, segment_tag, false>
0157     : detail::disjoint::disjoint_segment<Segment1, Segment2>
0158 {};
0159
0160
0161 } // namespace dispatch
0162 #endif // DOXYGEN_NO_DISPATCH
0163
0164
0165 }} // namespace boost::geometry
0166
0167
0168 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_LINEAR_HPP