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