• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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>
applyboost::geometry::detail::relate::turns::get_turns89     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>
applyboost::geometry::detail::relate::turns::get_turns104     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>
applyboost::geometry::detail::relate::turns::get_turns120     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>
operator ()boost::geometry::detail::relate::turns::op_to_int158     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>
operator ()boost::geometry::detail::relate::turns::less_op_xxx_linear177     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>
operator ()boost::geometry::detail::relate::turns::less_op_linear_areal_single193     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>
operator ()boost::geometry::detail::relate::turns::less_op_areal_areal228     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>
operator ()boost::geometry::detail::relate::turns::less_other_multi_index280     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>
use_fractionboost::geometry::detail::relate::turns::less295     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>
operator ()boost::geometry::detail::relate::turns::less321     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
336