boost/geometry/algorithms/detail/relate/turns.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 2013, 2014, 2015, 2017, 2019.
   6 // Modifications copyright (c) 2013-2019 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
  17
  18 #include <boost/geometry/strategies/distance.hpp>
  19 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
  20 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  21 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  22
  23 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
  24 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
  25
  26 #include <boost/geometry/strategies/cartesian/point_in_point.hpp>
  27 #include <boost/geometry/strategies/spherical/point_in_point.hpp>
  28
  29 #include <boost/type_traits/is_base_of.hpp>
  30
  31
  32 namespace boost { namespace geometry {
  33
  34 #ifndef DOXYGEN_NO_DETAIL
  35 namespace detail { namespace relate { namespace turns {
  36
  37 template <bool IncludeDegenerate = false>
  38 struct assign_policy
  39     : overlay::assign_null_policy
  40 {
  41     static bool const include_degenerate = IncludeDegenerate;
  42 };
  43
  44 // GET_TURNS
  45
  46 template
  47 <
  48     typename Geometry1,
  49     typename Geometry2,
  50     typename GetTurnPolicy = detail::get_turns::get_turn_info_type
  51         <
  52             Geometry1, Geometry2, assign_policy<>
  53         >
  54 >
  55 struct get_turns
  56 {
  57     typedef typename geometry::point_type<Geometry1>::type point1_type;
  58
  59     template <typename Strategy>
  60     struct robust_policy_type
  61         : geometry::rescale_overlay_policy_type
  62             <
  63                 Geometry1,
  64                 Geometry2,
  65                 typename Strategy::cs_tag
  66             >
  67     {};
  68
  69     template
  70     <
  71         typename Strategy,
  72         typename RobustPolicy = typename robust_policy_type<Strategy>::type
  73     >
  74     struct turn_info_type
  75     {
  76         typedef typename segment_ratio_type<point1_type, RobustPolicy>::type ratio_type;
  77         typedef overlay::turn_info
  78             <
  79                 point1_type,
  80                 ratio_type,
  81                 typename detail::get_turns::turn_operation_type
  82                     <
  83                         Geometry1, Geometry2, ratio_type
  84                     >::type
  85             > type;
  86     };
  87
  88     template <typename Turns>
  89     static inline void apply(Turns & turns,
  90                              Geometry1 const& geometry1,
  91                              Geometry2 const& geometry2)
  92     {
  93         detail::get_turns::no_interrupt_policy interrupt_policy;
  94
  95         typename strategy::intersection::services::default_strategy
  96             <
  97                 typename cs_tag<Geometry1>::type
  98             >::type intersection_strategy;
  99
 100         apply(turns, geometry1, geometry2, interrupt_policy, intersection_strategy);
 101     }
 102
 103     template <typename Turns, typename InterruptPolicy, typename IntersectionStrategy>
 104     static inline void apply(Turns & turns,
 105                              Geometry1 const& geometry1,
 106                              Geometry2 const& geometry2,
 107                              InterruptPolicy & interrupt_policy,
 108                              IntersectionStrategy const& intersection_strategy)
 109     {
 110         typedef typename robust_policy_type<IntersectionStrategy>::type robust_policy_t;
 111
 112         robust_policy_t robust_policy
 113                 = geometry::get_rescale_policy<robust_policy_t>(
 114                     geometry1, geometry2, intersection_strategy);
 115
 116         apply(turns, geometry1, geometry2, interrupt_policy, intersection_strategy, robust_policy);
 117     }
 118
 119     template <typename Turns, typename InterruptPolicy, typename IntersectionStrategy, typename RobustPolicy>
 120     static inline void apply(Turns & turns,
 121                              Geometry1 const& geometry1,
 122                              Geometry2 const& geometry2,
 123                              InterruptPolicy & interrupt_policy,
 124                              IntersectionStrategy const& intersection_strategy,
 125                              RobustPolicy const& robust_policy)
 126     {
 127         static const bool reverse1 = detail::overlay::do_reverse
 128             <
 129                 geometry::point_order<Geometry1>::value
 130             >::value;
 131
 132         static const bool reverse2 = detail::overlay::do_reverse
 133             <
 134                 geometry::point_order<Geometry2>::value
 135             >::value;
 136
 137         dispatch::get_turns
 138             <
 139                 typename geometry::tag<Geometry1>::type,
 140                 typename geometry::tag<Geometry2>::type,
 141                 Geometry1,
 142                 Geometry2,
 143                 reverse1,
 144                 reverse2,
 145                 GetTurnPolicy
 146             >::apply(0, geometry1, 1, geometry2,
 147                      intersection_strategy, robust_policy,
 148                      turns, interrupt_policy);
 149     }
 150 };
 151
 152 // TURNS SORTING AND SEARCHING
 153
 154 template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
 155 struct op_to_int
 156 {
 157     template <typename Operation>
 158     inline int operator()(Operation const& op) const
 159     {
 160         switch(op.operation)
 161         {
 162         case detail::overlay::operation_none : return N;
 163         case detail::overlay::operation_union : return U;
 164         case detail::overlay::operation_intersection : return I;
 165         case detail::overlay::operation_blocked : return B;
 166         case detail::overlay::operation_continue : return C;
 167         case detail::overlay::operation_opposite : return O;
 168         }
 169         return -1;
 170     }
 171 };
 172
 173 template <std::size_t OpId, typename OpToInt>
 174 struct less_op_xxx_linear
 175 {
 176     template <typename Turn>
 177     inline bool operator()(Turn const& left, Turn const& right) const
 178     {
 179         static OpToInt op_to_int;
 180         return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
 181     }
 182 };
 183
 184 template <std::size_t OpId>
 185 struct less_op_linear_linear
 186     : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> >
 187 {};
 188
 189 template <std::size_t OpId>
 190 struct less_op_linear_areal_single
 191 {
 192     template <typename Turn>
 193     inline bool operator()(Turn const& left, Turn const& right) const
 194     {
 195         static const std::size_t other_op_id = (OpId + 1) % 2;
 196         static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
 197         static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;
 198
 199         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
 200         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
 201
 202         typedef typename Turn::turn_operation_type operation_type;
 203         operation_type const& left_operation = left.operations[OpId];
 204         operation_type const& right_operation = right.operations[OpId];
 205
 206         if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
 207         {
 208             return op_to_int_xuic(left_operation)
 209                  < op_to_int_xuic(right_operation);
 210         }
 211         else
 212         {
 213             return op_to_int_xiuc(left_operation)
 214                  < op_to_int_xiuc(right_operation);
 215         }
 216     }
 217 };
 218
 219 template <std::size_t OpId>
 220 struct less_op_areal_linear
 221     : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
 222 {};
 223
 224 template <std::size_t OpId>
 225 struct less_op_areal_areal
 226 {
 227     template <typename Turn>
 228     inline bool operator()(Turn const& left, Turn const& right) const
 229     {
 230         static const std::size_t other_op_id = (OpId + 1) % 2;
 231         static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
 232         static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;
 233
 234         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
 235         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
 236
 237         typedef typename Turn::turn_operation_type operation_type;
 238         operation_type const& left_operation = left.operations[OpId];
 239         operation_type const& right_operation = right.operations[OpId];
 240
 241         if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
 242         {
 243             if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
 244             {
 245                 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
 246             }
 247             else
 248             {
 249                 if ( left_other_seg_id.ring_index == -1 )
 250                 {
 251                     if ( left_operation.operation == overlay::operation_union )
 252                         return false;
 253                     else if ( left_operation.operation == overlay::operation_intersection )
 254                         return true;
 255                 }
 256                 else if ( right_other_seg_id.ring_index == -1 )
 257                 {
 258                     if ( right_operation.operation == overlay::operation_union )
 259                         return true;
 260                     else if ( right_operation.operation == overlay::operation_intersection )
 261                         return false;
 262                 }
 263
 264                 return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
 265             }
 266         }
 267         else
 268         {
 269             return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
 270         }
 271     }
 272 };
 273
 274 template <std::size_t OpId>
 275 struct less_other_multi_index
 276 {
 277     static const std::size_t other_op_id = (OpId + 1) % 2;
 278
 279     template <typename Turn>
 280     inline bool operator()(Turn const& left, Turn const& right) const
 281     {
 282         return left.operations[other_op_id].seg_id.multi_index
 283              < right.operations[other_op_id].seg_id.multi_index;
 284     }
 285 };
 286
 287 // sort turns by G1 - source_index == 0 by:
 288 // seg_id -> distance and coordinates -> operation
 289 template <std::size_t OpId, typename LessOp, typename CSTag>
 290 struct less
 291 {
 292     BOOST_STATIC_ASSERT(OpId < 2);
 293
 294     template <typename Turn>
 295     static inline bool use_fraction(Turn const& left, Turn const& right)
 296     {
 297         typedef typename geometry::strategy::within::services::default_strategy
 298             <
 299                 typename Turn::point_type, typename Turn::point_type,
 300                 point_tag, point_tag,
 301                 pointlike_tag, pointlike_tag,
 302                 typename tag_cast<CSTag, spherical_tag>::type,
 303                 typename tag_cast<CSTag, spherical_tag>::type
 304             >::type eq_pp_strategy_type;
 305
 306         static LessOp less_op;
 307
 308         // NOTE: Assuming fraction is more permissive and faster than
 309         //       comparison of points with strategy.
 310         return geometry::math::equals(left.operations[OpId].fraction,
 311                                       right.operations[OpId].fraction)
 312                 && eq_pp_strategy_type::apply(left.point, right.point)
 313              ?
 314              less_op(left, right)
 315              :
 316              (left.operations[OpId].fraction < right.operations[OpId].fraction)
 317              ;
 318     }
 319
 320     template <typename Turn>
 321     inline bool operator()(Turn const& left, Turn const& right) const
 322     {
 323         segment_identifier const& sl = left.operations[OpId].seg_id;
 324         segment_identifier const& sr = right.operations[OpId].seg_id;
 325
 326         return sl < sr || ( sl == sr && use_fraction(left, right) );
 327     }
 328 };
 329
 330 }}} // namespace detail::relate::turns
 331 #endif // DOXYGEN_NO_DETAIL
 332
 333 }} // namespace boost::geometry
 334
 335 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP