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-2024.
0009 // Modifications copyright (c) 2013-2024, Oracle and/or its affiliates.
0010 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0011 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0012 // Contributed and/or modified by Adam Wulkiewicz, 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
0040 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
0041
0042
0043 namespace boost { namespace geometry
0044 {
0045
0046
0047 #ifndef DOXYGEN_NO_DETAIL
0048 namespace detail { namespace disjoint
0049 {
0050
0051 template <typename Segment1, typename Segment2>
0052 struct disjoint_segment
0053 {
0054     template <typename Strategy>
0055     static inline bool apply(Segment1 const& segment1, Segment2 const& segment2,
0056                              Strategy const& strategy)
0057     {
0058         using point_type = point_type_t<Segment1>;
0059         using intersection_return_type = segment_intersection_points<point_type>;
0060         using intersection_policy = policies::relate::segments_intersection_points
0061             <
0062                 intersection_return_type
0063             >;
0064
0065         detail::segment_as_subrange<Segment1> sub_range1(segment1);
0066         detail::segment_as_subrange<Segment2> sub_range2(segment2);
0067         intersection_return_type is = strategy.relate().apply(sub_range1, sub_range2,
0068                                                               intersection_policy());
0069
0070         return is.count == 0;
0071     }
0072 };
0073
0074
0075 struct assign_disjoint_policy
0076 {
0077     // We want to include all points:
0078     static bool const include_no_turn = true;
0079     static bool const include_degenerate = true;
0080     static bool const include_opposite = true;
0081     static bool const include_start_turn = false;
0082 };
0083
0084
0085 template <typename Geometry1, typename Geometry2>
0086 struct disjoint_linear
0087 {
0088     template <typename Strategy>
0089     static inline bool apply(Geometry1 const& geometry1,
0090                              Geometry2 const& geometry2,
0091                              Strategy const& strategy)
0092     {
0093         using point_type = geometry::point_type_t<Geometry1>;
0094         using mutable_point_type = typename helper_geometry<point_type>::type;
0095         using ratio_type = geometry::segment_ratio<coordinate_type_t<point_type>>;
0096         using turn_info_type = overlay::turn_info
0097             <
0098                 mutable_point_type,
0099                 ratio_type,
0100                 typename detail::get_turns::turn_operation_type
0101                         <
0102                             Geometry1, Geometry2, mutable_point_type, ratio_type
0103                         >::type
0104             >;
0105
0106         std::deque<turn_info_type> turns;
0107
0108         // Specify two policies:
0109         // 1) Stop at any intersection
0110         // 2) In assignment, include also degenerate points (which are normally skipped)
0111         disjoint_interrupt_policy interrupt_policy;
0112         dispatch::get_turns
0113             <
0114                 geometry::tag_t<Geometry1>,
0115                 geometry::tag_t<Geometry2>,
0116                 Geometry1,
0117                 Geometry2,
0118                 overlay::do_reverse<geometry::point_order<Geometry1>::value>::value, // should be false
0119                 overlay::do_reverse<geometry::point_order<Geometry2>::value>::value, // should be false
0120                 detail::get_turns::get_turn_info_type
0121                     <
0122                         Geometry1, Geometry2, assign_disjoint_policy
0123                     >
0124             >::apply(0, geometry1, 1, geometry2,
0125                      strategy, turns, interrupt_policy);
0126
0127         return !interrupt_policy.has_intersections;
0128     }
0129 };
0130
0131
0132 }} // namespace detail::disjoint
0133 #endif // DOXYGEN_NO_DETAIL
0134
0135
0136
0137
0138 #ifndef DOXYGEN_NO_DISPATCH
0139 namespace dispatch
0140 {
0141
0142
0143 template <typename Linear1, typename Linear2>
0144 struct disjoint<Linear1, Linear2, 2, linear_tag, linear_tag, false>
0145     : detail::disjoint::disjoint_linear<Linear1, Linear2>
0146 {};
0147
0148
0149 template <typename Segment1, typename Segment2>
0150 struct disjoint<Segment1, Segment2, 2, segment_tag, segment_tag, false>
0151     : detail::disjoint::disjoint_segment<Segment1, Segment2>
0152 {};
0153
0154
0155 } // namespace dispatch
0156 #endif // DOXYGEN_NO_DISPATCH
0157
0158
0159 }} // namespace boost::geometry
0160
0161
0162 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_LINEAR_HPP