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>
applyboost::geometry::detail::relate::turns::get_turns72     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>
applyboost::geometry::detail::relate::turns::get_turns87     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>
applyboost::geometry::detail::relate::turns::get_turns102     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>
operator ()boost::geometry::detail::relate::turns::op_to_int140     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>
operator ()boost::geometry::detail::relate::turns::less_op_xxx_linear159     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>
operator ()boost::geometry::detail::relate::turns::less_op_linear_areal_single175     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>
operator ()boost::geometry::detail::relate::turns::less_op_areal_areal210     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>
operator ()boost::geometry::detail::relate::turns::less_other_multi_index262     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>
use_fractionboost::geometry::detail::relate::turns::less278     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>
operator ()boost::geometry::detail::relate::turns::less293     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
308