ceph/src/boost/boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2017-2020.
   6 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
  16
  17 #include <cstddef>
  18 #include <algorithm>
  19 #include <map>
  20 #include <set>
  21 #include <vector>
  22
  23 #include <boost/core/addressof.hpp>
  24 #include <boost/range/value_type.hpp>
  25
  26 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
  27 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
  28 #include <boost/geometry/strategies/side.hpp>
  29
  30 namespace boost { namespace geometry
  31 {
  32
  33 #ifndef DOXYGEN_NO_DETAIL
  34 namespace detail { namespace overlay
  35 {
  36
  37 // Wraps "turn_operation" from turn_info.hpp,
  38 // giving it extra information, necessary for sorting
  39 template <typename TurnOperation>
  40 struct indexed_turn_operation
  41 {
  42     typedef TurnOperation type;
  43
  44     std::size_t turn_index;
  45     std::size_t operation_index;
  46     bool skip;
  47     // use pointers to avoid copies, const& is not possible because of usage in vector
  48     segment_identifier const* other_seg_id; // segment id of other segment of intersection of two segments
  49     TurnOperation const* subject;
  50
  51     inline indexed_turn_operation(std::size_t ti, std::size_t oi,
  52                 TurnOperation const& sub,
  53                 segment_identifier const& oid)
  54         : turn_index(ti)
  55         , operation_index(oi)
  56         , skip(false)
  57         , other_seg_id(&oid)
  58         , subject(boost::addressof(sub))
  59     {}
  60
  61 };
  62
  63 template
  64 <
  65     typename Turns,
  66     typename Indexed,
  67     typename Geometry1, typename Geometry2,
  68     typename RobustPolicy,
  69     typename SideStrategy,
  70     bool Reverse1, bool Reverse2
  71 >
  72 struct less_by_segment_ratio
  73 {
  74     inline less_by_segment_ratio(Turns const& turns
  75             , Geometry1 const& geometry1
  76             , Geometry2 const& geometry2
  77             , RobustPolicy const& robust_policy
  78             , SideStrategy const& strategy)
  79         : m_turns(turns)
  80         , m_geometry1(geometry1)
  81         , m_geometry2(geometry2)
  82         , m_robust_policy(robust_policy)
  83         , m_strategy(strategy)
  84     {
  85     }
  86
  87 private :
  88
  89     Turns const& m_turns;
  90     Geometry1 const& m_geometry1;
  91     Geometry2 const& m_geometry2;
  92     RobustPolicy const& m_robust_policy;
  93     SideStrategy const& m_strategy;
  94
  95     typedef typename geometry::point_type<Geometry1>::type point_type;
  96
  97     inline bool default_order(Indexed const& left, Indexed const& right) const
  98     {
  99         // We've nothing to sort on. Take the indexes
 100         return left.turn_index < right.turn_index;
 101     }
 102
 103     inline bool consider_relative_order(Indexed const& left,
 104                     Indexed const& right) const
 105     {
 106         point_type pi, pj, ri, rj, si, sj;
 107
 108         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
 109             left.subject->seg_id,
 110             pi, pj);
 111         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
 112             *left.other_seg_id,
 113             ri, rj);
 114         geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
 115             *right.other_seg_id,
 116             si, sj);
 117
 118         int const side_rj_p = m_strategy.apply(pi, pj, rj);
 119         int const side_sj_p = m_strategy.apply(pi, pj, sj);
 120
 121         // Put the one turning left (1; right == -1) as last
 122         if (side_rj_p != side_sj_p)
 123         {
 124             return side_rj_p < side_sj_p;
 125         }
 126
 127         int const side_sj_r = m_strategy.apply(ri, rj, sj);
 128         int const side_rj_s = m_strategy.apply(si, sj, rj);
 129
 130         // If they both turn left: the most left as last
 131         // If they both turn right: this is not relevant, but take also here most left
 132         if (side_rj_s != side_sj_r)
 133         {
 134             return side_rj_s < side_sj_r;
 135         }
 136
 137         return default_order(left, right);
 138     }
 139
 140
 141 public :
 142
 143     // Note that left/right do NOT correspond to m_geometry1/m_geometry2
 144     // but to the "indexed_turn_operation"
 145     inline bool operator()(Indexed const& left, Indexed const& right) const
 146     {
 147         if (! (left.subject->seg_id == right.subject->seg_id))
 148         {
 149             return left.subject->seg_id < right.subject->seg_id;
 150         }
 151
 152         // Both left and right are located on the SAME segment.
 153
 154         if (! (left.subject->fraction == right.subject->fraction))
 155         {
 156             return left.subject->fraction < right.subject->fraction;
 157         }
 158
 159
 160         typedef typename boost::range_value<Turns>::type turn_type;
 161         turn_type const& left_turn = m_turns[left.turn_index];
 162         turn_type const& right_turn = m_turns[right.turn_index];
 163
 164         // First check "real" intersection (crosses)
 165         // -> distance zero due to precision, solve it by sorting
 166         if (left_turn.method == method_crosses
 167             && right_turn.method == method_crosses)
 168         {
 169             return consider_relative_order(left, right);
 170         }
 171
 172         bool const left_both_xx = left_turn.both(operation_blocked);
 173         bool const right_both_xx = right_turn.both(operation_blocked);
 174         if (left_both_xx && ! right_both_xx)
 175         {
 176             return true;
 177         }
 178         if (! left_both_xx && right_both_xx)
 179         {
 180             return false;
 181         }
 182
 183         bool const left_both_uu = left_turn.both(operation_union);
 184         bool const right_both_uu = right_turn.both(operation_union);
 185         if (left_both_uu && ! right_both_uu)
 186         {
 187             return true;
 188         }
 189         if (! left_both_uu && right_both_uu)
 190         {
 191             return false;
 192         }
 193
 194         return default_order(left, right);
 195     }
 196 };
 197
 198
 199 }} // namespace detail::overlay
 200 #endif //DOXYGEN_NO_DETAIL
 201
 202
 203 }} // namespace boost::geometry
 204
 205 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP