]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/relate/turns.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / geometry / include / boost / geometry / algorithms / detail / relate / turns.hpp
CommitLineData
7c673cae
FG		 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.
6// Modifications copyright (c) 2013-2015 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
29namespace boost { namespace geometry {
30
31#ifndef DOXYGEN_NO_DETAIL
32namespace detail { namespace relate { namespace turns {
33
34template <bool IncludeDegenerate = false>
35struct assign_policy
36 : overlay::assign_null_policy
37{
38 static bool const include_degenerate = IncludeDegenerate;
39};
40
41// GET_TURNS
42
43template
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>
53struct 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 apply(turns, geometry1, geometry2, interrupt_policy);
79 }
80
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)
86 {
87 RobustPolicy robust_policy = geometry::get_rescale_policy
88 <
89 RobustPolicy
90 >(geometry1, geometry2);
91
92 apply(turns, geometry1, geometry2, interrupt_policy, robust_policy);
93 }
94
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)
101 {
102 static const bool reverse1 = detail::overlay::do_reverse
103 <
104 geometry::point_order<Geometry1>::value
105 >::value;
106
107 static const bool reverse2 = detail::overlay::do_reverse
108 <
109 geometry::point_order<Geometry2>::value
110 >::value;
111
112 dispatch::get_turns
113 <
114 typename geometry::tag<Geometry1>::type,
115 typename geometry::tag<Geometry2>::type,
116 Geometry1,
117 Geometry2,
118 reverse1,
119 reverse2,
120 GetTurnPolicy
121 >::apply(0, geometry1, 1, geometry2,
122 robust_policy, turns, interrupt_policy);
123 }
124};
125
126// TURNS SORTING AND SEARCHING
127
128template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
129struct op_to_int
130{
131 template <typename Operation>
132 inline int operator()(Operation const& op) const
133 {
134 switch(op.operation)
135 {
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;
142 }
143 return -1;
144 }
145};
146
147template <std::size_t OpId, typename OpToInt>
148struct less_op_xxx_linear
149{
150 template <typename Turn>
151 inline bool operator()(Turn const& left, Turn const& right) const
152 {
153 static OpToInt op_to_int;
154 return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
155 }
156};
157
158template <std::size_t OpId>
159struct less_op_linear_linear
160 : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> >
161{};
162
163template <std::size_t OpId>
164struct less_op_linear_areal_single
165{
166 template <typename Turn>
167 inline bool operator()(Turn const& left, Turn const& right) const
168 {
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;
172
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;
175
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];
179
180 if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
181 {
182 return op_to_int_xuic(left_operation)
183 < op_to_int_xuic(right_operation);
184 }
185 else
186 {
187 return op_to_int_xiuc(left_operation)
188 < op_to_int_xiuc(right_operation);
189 }
190 }
191};
192
193template <std::size_t OpId>
194struct less_op_areal_linear
195 : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
196{};
197
198template <std::size_t OpId>
199struct less_op_areal_areal
200{
201 template <typename Turn>
202 inline bool operator()(Turn const& left, Turn const& right) const
203 {
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;
207
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;
210
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];
214
215 if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
216 {
217 if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
218 {
219 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
220 }
221 else
222 {
223 if ( left_other_seg_id.ring_index == -1 )
224 {
225 if ( left_operation.operation == overlay::operation_union )
226 return false;
227 else if ( left_operation.operation == overlay::operation_intersection )
228 return true;
229 }
230 else if ( right_other_seg_id.ring_index == -1 )
231 {
232 if ( right_operation.operation == overlay::operation_union )
233 return true;
234 else if ( right_operation.operation == overlay::operation_intersection )
235 return false;
236 }
237
238 return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
239 }
240 }
241 else
242 {
243 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
244 }
245 }
246};
247
248template <std::size_t OpId>
249struct less_other_multi_index
250{
251 static const std::size_t other_op_id = (OpId + 1) % 2;
252
253 template <typename Turn>
254 inline bool operator()(Turn const& left, Turn const& right) const
255 {
256 return left.operations[other_op_id].seg_id.multi_index
257 < right.operations[other_op_id].seg_id.multi_index;
258 }
259};
260
261// sort turns by G1 - source_index == 0 by:
262// seg_id -> distance -> operation
263template <std::size_t OpId = 0,
264 typename LessOp = less_op_xxx_linear< OpId, op_to_int<> > >
265struct less
266{
267 BOOST_STATIC_ASSERT(OpId < 2);
268
269 template <typename Turn>
270 static inline bool use_fraction(Turn const& left, Turn const& right)
271 {
272 static LessOp less_op;
273
274 return
275 geometry::math::equals(left.operations[OpId].fraction,
276 right.operations[OpId].fraction)
277 ?
278 less_op(left, right)
279 :
280 (left.operations[OpId].fraction < right.operations[OpId].fraction)
281 ;
282 }
283
284 template <typename Turn>
285 inline bool operator()(Turn const& left, Turn const& right) const
286 {
287 segment_identifier const& sl = left.operations[OpId].seg_id;
288 segment_identifier const& sr = right.operations[OpId].seg_id;
289
290 return sl < sr || ( sl == sr && use_fraction(left, right) );
291 }
292};
293
294}}} // namespace detail::relate::turns
295#endif // DOXYGEN_NO_DETAIL
296
297}} // namespace boost::geometry
298
299#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
Ceph