detail/overlay/less_by_segment_ratio.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2017-2024.
0006 // Modifications copyright (c) 2017-2024 Oracle and/or its affiliates.
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
0016
0017 #include <cstddef>
0018 #include <algorithm>
0019 #include <map>
0020 #include <set>
0021 #include <vector>
0022
0023 #include <boost/core/addressof.hpp>
0024 #include <boost/range/value_type.hpp>
0025
0026 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
0027 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
0028 #include <boost/geometry/strategies/side.hpp>
0029
0030 namespace boost { namespace geometry
0031 {
0032
0033 #ifndef DOXYGEN_NO_DETAIL
0034 namespace detail { namespace overlay
0035 {
0036
0037 // Wraps "turn_operation" from turn_info.hpp,
0038 // giving it extra information, necessary for sorting
0039 template <typename TurnOperation>
0040 struct indexed_turn_operation
0041 {
0042     using type = TurnOperation;
0043
0044     std::size_t turn_index;
0045     std::size_t operation_index;
0046     // use pointers to avoid copies, const& is not possible because of usage in vector
0047     segment_identifier const* other_seg_id; // segment id of other segment of intersection of two segments
0048     TurnOperation const* subject;
0049
0050     inline indexed_turn_operation(std::size_t ti, std::size_t oi,
0051                 TurnOperation const& sub,
0052                 segment_identifier const& oid)
0053         : turn_index(ti)
0054         , operation_index(oi)
0055         , other_seg_id(&oid)
0056         , subject(boost::addressof(sub))
0057     {}
0058
0059 };
0060
0061 template
0062 <
0063     typename Turns,
0064     typename Indexed,
0065     typename Geometry1, typename Geometry2,
0066     typename Strategy,
0067     bool Reverse1, bool Reverse2
0068 >
0069 struct less_by_segment_ratio
0070 {
0071     inline less_by_segment_ratio(Turns const& turns
0072             , Geometry1 const& geometry1
0073             , Geometry2 const& geometry2
0074             , Strategy const& strategy)
0075         : m_turns(turns)
0076         , m_geometry1(geometry1)
0077         , m_geometry2(geometry2)
0078         , m_strategy(strategy)
0079     {
0080     }
0081
0082 private :
0083
0084     Turns const& m_turns;
0085     Geometry1 const& m_geometry1;
0086     Geometry2 const& m_geometry2;
0087     Strategy const& m_strategy;
0088
0089     using point_type = geometry::point_type_t<Geometry1>;
0090
0091     inline bool default_order(Indexed const& left, Indexed const& right) const
0092     {
0093         // We've nothing to sort on. Take the indexes
0094         return left.turn_index < right.turn_index;
0095     }
0096
0097     inline bool consider_relative_order(Indexed const& left,
0098                     Indexed const& right) const
0099     {
0100         point_type pi, pj, ri, rj, si, sj;
0101
0102         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
0103             left.subject->seg_id,
0104             pi, pj);
0105         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
0106             *left.other_seg_id,
0107             ri, rj);
0108         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
0109             *right.other_seg_id,
0110             si, sj);
0111
0112         auto side_strategy = m_strategy.side();
0113         int const side_rj_p = side_strategy.apply(pi, pj, rj);
0114         int const side_sj_p = side_strategy.apply(pi, pj, sj);
0115
0116         // Put the one turning left (1; right == -1) as last
0117         if (side_rj_p != side_sj_p)
0118         {
0119             return side_rj_p < side_sj_p;
0120         }
0121
0122         int const side_sj_r = side_strategy.apply(ri, rj, sj);
0123         int const side_rj_s = side_strategy.apply(si, sj, rj);
0124
0125         // If they both turn left: the most left as last
0126         // If they both turn right: this is not relevant, but take also here most left
0127         if (side_rj_s != side_sj_r)
0128         {
0129             return side_rj_s < side_sj_r;
0130         }
0131
0132         return default_order(left, right);
0133     }
0134
0135
0136 public :
0137
0138     // Note that left/right do NOT correspond to m_geometry1/m_geometry2
0139     // but to the "indexed_turn_operation"
0140     inline bool operator()(Indexed const& left, Indexed const& right) const
0141     {
0142         if (! (left.subject->seg_id == right.subject->seg_id))
0143         {
0144             return left.subject->seg_id < right.subject->seg_id;
0145         }
0146
0147         // Both left and right are located on the SAME segment.
0148
0149         if (! (left.subject->fraction == right.subject->fraction))
0150         {
0151             return left.subject->fraction < right.subject->fraction;
0152         }
0153
0154         auto const& left_turn = m_turns[left.turn_index];
0155         auto const& right_turn = m_turns[right.turn_index];
0156
0157         // First check "real" intersection (crosses)
0158         // -> distance zero due to precision, solve it by sorting
0159         if (left_turn.method == method_crosses
0160             && right_turn.method == method_crosses)
0161         {
0162             return consider_relative_order(left, right);
0163         }
0164
0165         bool const left_both_xx = left_turn.both(operation_blocked);
0166         bool const right_both_xx = right_turn.both(operation_blocked);
0167         if (left_both_xx && ! right_both_xx)
0168         {
0169             return true;
0170         }
0171         if (! left_both_xx && right_both_xx)
0172         {
0173             return false;
0174         }
0175
0176         bool const left_both_uu = left_turn.both(operation_union);
0177         bool const right_both_uu = right_turn.both(operation_union);
0178         if (left_both_uu && ! right_both_uu)
0179         {
0180             return true;
0181         }
0182         if (! left_both_uu && right_both_uu)
0183         {
0184             return false;
0185         }
0186
0187         return default_order(left, right);
0188     }
0189 };
0190
0191
0192 }} // namespace detail::overlay
0193 #endif //DOXYGEN_NO_DETAIL
0194
0195
0196 }} // namespace boost::geometry
0197
0198 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP