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.
   6 // Modifications copyright (c) 2013-2017 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/no_rescale_policy.hpp>
  25
  26 #include <boost/type_traits/is_base_of.hpp>
  27
  28
  29 namespace boost { namespace geometry {
  30
  31 #ifndef DOXYGEN_NO_DETAIL
  32 namespace detail { namespace relate { namespace turns {
  33
  34 template <bool IncludeDegenerate = false>
  35 struct assign_policy
  36     : overlay::assign_null_policy
  37 {
  38     static bool const include_degenerate = IncludeDegenerate;
  39 };
  40
  41 // GET_TURNS
  42
  43 template
  44 <
  45     typename Geometry1,
  46     typename Geometry2,
  47     typename GetTurnPolicy = detail::get_turns::get_turn_info_type
  48         <
  49             Geometry1, Geometry2, assign_policy<>
  50         >,
  51     typename RobustPolicy = detail::no_rescale_policy
  52 >
  53 struct get_turns
  54 {
  55     typedef typename geometry::point_type<Geometry1>::type point1_type;
  56
  57     typedef overlay::turn_info
  58             <
  59                 point1_type,
  60                 typename segment_ratio_type<point1_type, RobustPolicy>::type,
  61                 typename detail::get_turns::turn_operation_type
  62                     <
  63                         Geometry1, Geometry2,
  64                         typename segment_ratio_type
  65                             <
  66                                 point1_type, RobustPolicy
  67                             >::type
  68                     >::type
  69             > turn_info;
  70
  71     template <typename Turns>
  72     static inline void apply(Turns & turns,
  73                              Geometry1 const& geometry1,
  74                              Geometry2 const& geometry2)
  75     {
  76         detail::get_turns::no_interrupt_policy interrupt_policy;
  77
  78         typename strategy::intersection::services::default_strategy
  79             <
  80                 typename cs_tag<Geometry1>::type
  81             >::type intersection_strategy;
  82
  83         apply(turns, geometry1, geometry2, interrupt_policy, intersection_strategy);
  84     }
  85
  86     template <typename Turns, typename InterruptPolicy, typename IntersectionStrategy>
  87     static inline void apply(Turns & turns,
  88                              Geometry1 const& geometry1,
  89                              Geometry2 const& geometry2,
  90                              InterruptPolicy & interrupt_policy,
  91                              IntersectionStrategy const& intersection_strategy)
  92     {
  93         RobustPolicy robust_policy = geometry::get_rescale_policy
  94             <
  95                 RobustPolicy
  96             >(geometry1, geometry2);
  97
  98         apply(turns, geometry1, geometry2, interrupt_policy, intersection_strategy, robust_policy);
  99     }
 100
 101     template <typename Turns, typename InterruptPolicy, typename IntersectionStrategy>
 102     static inline void apply(Turns & turns,
 103                              Geometry1 const& geometry1,
 104                              Geometry2 const& geometry2,
 105                              InterruptPolicy & interrupt_policy,
 106                              IntersectionStrategy const& intersection_strategy,
 107                              RobustPolicy const& robust_policy)
 108     {
 109         static const bool reverse1 = detail::overlay::do_reverse
 110             <
 111                 geometry::point_order<Geometry1>::value
 112             >::value;
 113
 114         static const bool reverse2 = detail::overlay::do_reverse
 115             <
 116                 geometry::point_order<Geometry2>::value
 117             >::value;
 118
 119         dispatch::get_turns
 120             <
 121                 typename geometry::tag<Geometry1>::type,
 122                 typename geometry::tag<Geometry2>::type,
 123                 Geometry1,
 124                 Geometry2,
 125                 reverse1,
 126                 reverse2,
 127                 GetTurnPolicy
 128             >::apply(0, geometry1, 1, geometry2,
 129                      intersection_strategy, robust_policy,
 130                      turns, interrupt_policy);
 131     }
 132 };
 133
 134 // TURNS SORTING AND SEARCHING
 135
 136 template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
 137 struct op_to_int
 138 {
 139     template <typename Operation>
 140     inline int operator()(Operation const& op) const
 141     {
 142         switch(op.operation)
 143         {
 144         case detail::overlay::operation_none : return N;
 145         case detail::overlay::operation_union : return U;
 146         case detail::overlay::operation_intersection : return I;
 147         case detail::overlay::operation_blocked : return B;
 148         case detail::overlay::operation_continue : return C;
 149         case detail::overlay::operation_opposite : return O;
 150         }
 151         return -1;
 152     }
 153 };
 154
 155 template <std::size_t OpId, typename OpToInt>
 156 struct less_op_xxx_linear
 157 {
 158     template <typename Turn>
 159     inline bool operator()(Turn const& left, Turn const& right) const
 160     {
 161         static OpToInt op_to_int;
 162         return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
 163     }
 164 };
 165
 166 template <std::size_t OpId>
 167 struct less_op_linear_linear
 168     : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> >
 169 {};
 170
 171 template <std::size_t OpId>
 172 struct less_op_linear_areal_single
 173 {
 174     template <typename Turn>
 175     inline bool operator()(Turn const& left, Turn const& right) const
 176     {
 177         static const std::size_t other_op_id = (OpId + 1) % 2;
 178         static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
 179         static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;
 180
 181         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
 182         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
 183
 184         typedef typename Turn::turn_operation_type operation_type;
 185         operation_type const& left_operation = left.operations[OpId];
 186         operation_type const& right_operation = right.operations[OpId];
 187
 188         if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
 189         {
 190             return op_to_int_xuic(left_operation)
 191                  < op_to_int_xuic(right_operation);
 192         }
 193         else
 194         {
 195             return op_to_int_xiuc(left_operation)
 196                  < op_to_int_xiuc(right_operation);
 197         }
 198     }
 199 };
 200
 201 template <std::size_t OpId>
 202 struct less_op_areal_linear
 203     : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
 204 {};
 205
 206 template <std::size_t OpId>
 207 struct less_op_areal_areal
 208 {
 209     template <typename Turn>
 210     inline bool operator()(Turn const& left, Turn const& right) const
 211     {
 212         static const std::size_t other_op_id = (OpId + 1) % 2;
 213         static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
 214         static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;
 215
 216         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
 217         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
 218
 219         typedef typename Turn::turn_operation_type operation_type;
 220         operation_type const& left_operation = left.operations[OpId];
 221         operation_type const& right_operation = right.operations[OpId];
 222
 223         if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
 224         {
 225             if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
 226             {
 227                 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
 228             }
 229             else
 230             {
 231                 if ( left_other_seg_id.ring_index == -1 )
 232                 {
 233                     if ( left_operation.operation == overlay::operation_union )
 234                         return false;
 235                     else if ( left_operation.operation == overlay::operation_intersection )
 236                         return true;
 237                 }
 238                 else if ( right_other_seg_id.ring_index == -1 )
 239                 {
 240                     if ( right_operation.operation == overlay::operation_union )
 241                         return true;
 242                     else if ( right_operation.operation == overlay::operation_intersection )
 243                         return false;
 244                 }
 245
 246                 return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
 247             }
 248         }
 249         else
 250         {
 251             return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
 252         }
 253     }
 254 };
 255
 256 template <std::size_t OpId>
 257 struct less_other_multi_index
 258 {
 259     static const std::size_t other_op_id = (OpId + 1) % 2;
 260
 261     template <typename Turn>
 262     inline bool operator()(Turn const& left, Turn const& right) const
 263     {
 264         return left.operations[other_op_id].seg_id.multi_index
 265              < right.operations[other_op_id].seg_id.multi_index;
 266     }
 267 };
 268
 269 // sort turns by G1 - source_index == 0 by:
 270 // seg_id -> distance -> operation
 271 template <std::size_t OpId = 0,
 272           typename LessOp = less_op_xxx_linear< OpId, op_to_int<> > >
 273 struct less
 274 {
 275     BOOST_STATIC_ASSERT(OpId < 2);
 276
 277     template <typename Turn>
 278     static inline bool use_fraction(Turn const& left, Turn const& right)
 279     {
 280         static LessOp less_op;
 281
 282         return
 283             geometry::math::equals(left.operations[OpId].fraction,
 284                                    right.operations[OpId].fraction)
 285             ?
 286             less_op(left, right)
 287             :
 288             (left.operations[OpId].fraction < right.operations[OpId].fraction)
 289             ;
 290     }
 291
 292     template <typename Turn>
 293     inline bool operator()(Turn const& left, Turn const& right) const
 294     {
 295         segment_identifier const& sl = left.operations[OpId].seg_id;
 296         segment_identifier const& sr = right.operations[OpId].seg_id;
 297
 298         return sl < sr || ( sl == sr && use_fraction(left, right) );
 299     }
 300 };
 301
 302 }}} // namespace detail::relate::turns
 303 #endif // DOXYGEN_NO_DETAIL
 304
 305 }} // namespace boost::geometry
 306
 307 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP