1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2013, 2014, 2015.
6 // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
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)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
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>
23 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
24 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
26 #include <boost/type_traits/is_base_of.hpp>
29 namespace boost { namespace geometry {
31 #ifndef DOXYGEN_NO_DETAIL
32 namespace detail { namespace relate { namespace turns {
34 template <bool IncludeDegenerate = false>
36 : overlay::assign_null_policy
38 static bool const include_degenerate = IncludeDegenerate;
47 typename GetTurnPolicy = detail::get_turns::get_turn_info_type
49 Geometry1, Geometry2, assign_policy<>
51 typename RobustPolicy = detail::no_rescale_policy
55 typedef typename geometry::point_type<Geometry1>::type point1_type;
57 typedef overlay::turn_info
60 typename segment_ratio_type<point1_type, RobustPolicy>::type,
61 typename detail::get_turns::turn_operation_type
64 typename segment_ratio_type
66 point1_type, RobustPolicy
71 template <typename Turns>
72 static inline void apply(Turns & turns,
73 Geometry1 const& geometry1,
74 Geometry2 const& geometry2)
76 detail::get_turns::no_interrupt_policy interrupt_policy;
78 apply(turns, geometry1, geometry2, interrupt_policy);
81 template <typename Turns, typename InterruptPolicy>
82 static inline void apply(Turns & turns,
83 Geometry1 const& geometry1,
84 Geometry2 const& geometry2,
85 InterruptPolicy & interrupt_policy)
87 RobustPolicy robust_policy = geometry::get_rescale_policy
90 >(geometry1, geometry2);
92 apply(turns, geometry1, geometry2, interrupt_policy, robust_policy);
95 template <typename Turns, typename InterruptPolicy>
96 static inline void apply(Turns & turns,
97 Geometry1 const& geometry1,
98 Geometry2 const& geometry2,
99 InterruptPolicy & interrupt_policy,
100 RobustPolicy const& robust_policy)
102 static const bool reverse1 = detail::overlay::do_reverse
104 geometry::point_order<Geometry1>::value
107 static const bool reverse2 = detail::overlay::do_reverse
109 geometry::point_order<Geometry2>::value
114 typename geometry::tag<Geometry1>::type,
115 typename geometry::tag<Geometry2>::type,
121 >::apply(0, geometry1, 1, geometry2,
122 robust_policy, turns, interrupt_policy);
126 // TURNS SORTING AND SEARCHING
128 template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
131 template <typename Operation>
132 inline int operator()(Operation const& op) const
136 case detail::overlay::operation_none : return N;
137 case detail::overlay::operation_union : return U;
138 case detail::overlay::operation_intersection : return I;
139 case detail::overlay::operation_blocked : return B;
140 case detail::overlay::operation_continue : return C;
141 case detail::overlay::operation_opposite : return O;
147 template <std::size_t OpId, typename OpToInt>
148 struct less_op_xxx_linear
150 template <typename Turn>
151 inline bool operator()(Turn const& left, Turn const& right) const
153 static OpToInt op_to_int;
154 return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
158 template <std::size_t OpId>
159 struct less_op_linear_linear
160 : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> >
163 template <std::size_t OpId>
164 struct less_op_linear_areal_single
166 template <typename Turn>
167 inline bool operator()(Turn const& left, Turn const& right) const
169 static const std::size_t other_op_id = (OpId + 1) % 2;
170 static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
171 static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;
173 segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
174 segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
176 typedef typename Turn::turn_operation_type operation_type;
177 operation_type const& left_operation = left.operations[OpId];
178 operation_type const& right_operation = right.operations[OpId];
180 if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
182 return op_to_int_xuic(left_operation)
183 < op_to_int_xuic(right_operation);
187 return op_to_int_xiuc(left_operation)
188 < op_to_int_xiuc(right_operation);
193 template <std::size_t OpId>
194 struct less_op_areal_linear
195 : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
198 template <std::size_t OpId>
199 struct less_op_areal_areal
201 template <typename Turn>
202 inline bool operator()(Turn const& left, Turn const& right) const
204 static const std::size_t other_op_id = (OpId + 1) % 2;
205 static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
206 static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;
208 segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
209 segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
211 typedef typename Turn::turn_operation_type operation_type;
212 operation_type const& left_operation = left.operations[OpId];
213 operation_type const& right_operation = right.operations[OpId];
215 if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
217 if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
219 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
223 if ( left_other_seg_id.ring_index == -1 )
225 if ( left_operation.operation == overlay::operation_union )
227 else if ( left_operation.operation == overlay::operation_intersection )
230 else if ( right_other_seg_id.ring_index == -1 )
232 if ( right_operation.operation == overlay::operation_union )
234 else if ( right_operation.operation == overlay::operation_intersection )
238 return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
243 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
248 template <std::size_t OpId>
249 struct less_other_multi_index
251 static const std::size_t other_op_id = (OpId + 1) % 2;
253 template <typename Turn>
254 inline bool operator()(Turn const& left, Turn const& right) const
256 return left.operations[other_op_id].seg_id.multi_index
257 < right.operations[other_op_id].seg_id.multi_index;
261 // sort turns by G1 - source_index == 0 by:
262 // seg_id -> distance -> operation
263 template <std::size_t OpId = 0,
264 typename LessOp = less_op_xxx_linear< OpId, op_to_int<> > >
267 BOOST_STATIC_ASSERT(OpId < 2);
269 template <typename Turn>
270 static inline bool use_fraction(Turn const& left, Turn const& right)
272 static LessOp less_op;
275 geometry::math::equals(left.operations[OpId].fraction,
276 right.operations[OpId].fraction)
280 (left.operations[OpId].fraction < right.operations[OpId].fraction)
284 template <typename Turn>
285 inline bool operator()(Turn const& left, Turn const& right) const
287 segment_identifier const& sl = left.operations[OpId].seg_id;
288 segment_identifier const& sr = right.operations[OpId].seg_id;
290 return sl < sr || ( sl == sr && use_fraction(left, right) );
294 }}} // namespace detail::relate::turns
295 #endif // DOXYGEN_NO_DETAIL
297 }} // namespace boost::geometry
299 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP