1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2014-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2014-2015 Bruno Lalande, Paris, France.
5 // Copyright (c) 2014-2015 Mateusz Loskot, London, UK.
6 // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland.
7
8 // This file was modified by Oracle on 2015, 2019.
9 // Modifications copyright (c) 2015, 2019, Oracle and/or its affiliates.
10
11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
13
14 // Use, modification and distribution is subject to the Boost Software License,
15 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
16 // http://www.boost.org/LICENSE_1_0.txt)
17
18 #ifndef BOOST_GEOMETRY_POLICIES_ROBUSTNESS_GET_RESCALE_POLICY_HPP
19 #define BOOST_GEOMETRY_POLICIES_ROBUSTNESS_GET_RESCALE_POLICY_HPP
20
21
22 #include <cstddef>
23
24 #include <boost/mpl/assert.hpp>
25 #include <boost/type_traits/is_floating_point.hpp>
26 #include <boost/type_traits/is_same.hpp>
27
28 #include <boost/geometry/core/assert.hpp>
29 #include <boost/geometry/core/config.hpp>
30 #include <boost/geometry/core/tag_cast.hpp>
31
32 #include <boost/geometry/algorithms/envelope.hpp>
33 #include <boost/geometry/algorithms/expand.hpp>
34 #include <boost/geometry/algorithms/is_empty.hpp>
35 #include <boost/geometry/algorithms/detail/recalculate.hpp>
36 #include <boost/geometry/algorithms/detail/get_max_size.hpp>
37 #include <boost/geometry/policies/robustness/robust_type.hpp>
38
39 #include <boost/geometry/geometries/point.hpp>
40 #include <boost/geometry/geometries/box.hpp>
41
42 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
43 #include <boost/geometry/policies/robustness/rescale_policy.hpp>
44
45 #include <boost/geometry/util/promote_floating_point.hpp>
46
47 namespace boost { namespace geometry
48 {
49
50 #ifndef DOXYGEN_NO_DETAIL
51 namespace detail { namespace get_rescale_policy
52 {
53
54 template
55 <
56 typename Box,
57 typename Point,
58 typename RobustPoint,
59 typename Factor
60 >
scale_box_to_integer_range(Box const & box,Point & min_point,RobustPoint & min_robust_point,Factor & factor)61 inline void scale_box_to_integer_range(Box const& box,
62 Point& min_point,
63 RobustPoint& min_robust_point,
64 Factor& factor)
65 {
66 // Scale box to integer-range
67 typedef typename promote_floating_point
68 <
69 typename geometry::coordinate_type<Point>::type
70 >::type num_type;
71 num_type const diff = boost::numeric_cast<num_type>(detail::get_max_size(box));
72 num_type const range = 10000000.0; // Define a large range to get precise integer coordinates
73 num_type const half = 0.5;
74 if (math::equals(diff, num_type())
75 || diff >= range
76 || ! boost::math::isfinite(diff))
77 {
78 factor = 1;
79 }
80 else
81 {
82 factor = boost::numeric_cast<num_type>(
83 boost::numeric_cast<boost::long_long_type>(half + range / diff));
84 BOOST_GEOMETRY_ASSERT(factor >= 1);
85 }
86
87 // Assign input/output minimal points
88 detail::assign_point_from_index<0>(box, min_point);
89 num_type const two = 2;
90 boost::long_long_type const min_coordinate
91 = boost::numeric_cast<boost::long_long_type>(-range / two);
92 assign_values(min_robust_point, min_coordinate, min_coordinate);
93 }
94
95 template
96 <
97 typename Point, typename RobustPoint, typename Geometry,
98 typename Factor, typename EnvelopeStrategy
99 >
init_rescale_policy(Geometry const & geometry,Point & min_point,RobustPoint & min_robust_point,Factor & factor,EnvelopeStrategy const & strategy)100 static inline void init_rescale_policy(Geometry const& geometry,
101 Point& min_point,
102 RobustPoint& min_robust_point,
103 Factor& factor,
104 EnvelopeStrategy const& strategy)
105 {
106 if (geometry::is_empty(geometry))
107 {
108 return;
109 }
110
111 // Get bounding box
112 model::box<Point> env = geometry::return_envelope
113 <
114 model::box<Point>
115 >(geometry, strategy);
116
117 scale_box_to_integer_range(env, min_point, min_robust_point, factor);
118 }
119
120 // NOTE: Actually it should take 2 separate strategies, one for each geometry
121 // in case one of them was e.g. a Box
122 template
123 <
124 typename Point, typename RobustPoint, typename Geometry1, typename Geometry2,
125 typename Factor, typename EnvelopeStrategy1, typename EnvelopeStrategy2
126 >
init_rescale_policy(Geometry1 const & geometry1,Geometry2 const & geometry2,Point & min_point,RobustPoint & min_robust_point,Factor & factor,EnvelopeStrategy1 const & strategy1,EnvelopeStrategy2 const & strategy2)127 static inline void init_rescale_policy(Geometry1 const& geometry1,
128 Geometry2 const& geometry2,
129 Point& min_point,
130 RobustPoint& min_robust_point,
131 Factor& factor,
132 EnvelopeStrategy1 const& strategy1,
133 EnvelopeStrategy2 const& strategy2)
134 {
135 // Get bounding boxes (when at least one of the geometries is not empty)
136 bool const is_empty1 = geometry::is_empty(geometry1);
137 bool const is_empty2 = geometry::is_empty(geometry2);
138 if (is_empty1 && is_empty2)
139 {
140 return;
141 }
142
143 model::box<Point> env;
144 if (is_empty1)
145 {
146 geometry::envelope(geometry2, env, strategy2);
147 }
148 else if (is_empty2)
149 {
150 geometry::envelope(geometry1, env, strategy1);
151 }
152 else
153 {
154 // The following approach (envelope + expand) may not give the
155 // optimal MBR when then two geometries are in the spherical
156 // equatorial or geographic coordinate systems.
157 // TODO: implement envelope for two (or possibly more geometries)
158 geometry::envelope(geometry1, env, strategy1);
159 model::box<Point> env2 = geometry::return_envelope
160 <
161 model::box<Point>
162 >(geometry2, strategy2);
163 geometry::expand(env, env2, strategy1.get_box_expand_strategy());
164 }
165
166 scale_box_to_integer_range(env, min_point, min_robust_point, factor);
167 }
168
169
170 template
171 <
172 typename Point,
173 bool IsFloatingPoint
174 >
175 struct rescale_policy_type
176 {
177 typedef no_rescale_policy type;
178 };
179
180 // We rescale only all FP types
181 template
182 <
183 typename Point
184 >
185 struct rescale_policy_type<Point, true>
186 {
187 typedef typename geometry::coordinate_type<Point>::type coordinate_type;
188 typedef model::point
189 <
190 typename detail::robust_type<coordinate_type>::type,
191 geometry::dimension<Point>::value,
192 typename geometry::coordinate_system<Point>::type
193 > robust_point_type;
194 typedef typename promote_floating_point<coordinate_type>::type factor_type;
195 typedef detail::robust_policy<Point, robust_point_type, factor_type> type;
196 };
197
198 template <typename Policy>
199 struct get_rescale_policy
200 {
201 template <typename Geometry, typename EnvelopeStrategy>
applyboost::geometry::detail::get_rescale_policy::get_rescale_policy202 static inline Policy apply(Geometry const& geometry,
203 EnvelopeStrategy const& strategy)
204 {
205 typedef typename point_type<Geometry>::type point_type;
206 typedef typename geometry::coordinate_type<Geometry>::type coordinate_type;
207 typedef typename promote_floating_point<coordinate_type>::type factor_type;
208 typedef model::point
209 <
210 typename detail::robust_type<coordinate_type>::type,
211 geometry::dimension<point_type>::value,
212 typename geometry::coordinate_system<point_type>::type
213 > robust_point_type;
214
215 point_type min_point;
216 robust_point_type min_robust_point;
217 factor_type factor;
218 init_rescale_policy(geometry, min_point, min_robust_point,
219 factor, strategy);
220
221 return Policy(min_point, min_robust_point, factor);
222 }
223
224 template <typename Geometry1, typename Geometry2, typename EnvelopeStrategy1, typename EnvelopeStrategy2>
applyboost::geometry::detail::get_rescale_policy::get_rescale_policy225 static inline Policy apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
226 EnvelopeStrategy1 const& strategy1,
227 EnvelopeStrategy2 const& strategy2)
228 {
229 typedef typename point_type<Geometry1>::type point_type;
230 typedef typename geometry::coordinate_type<Geometry1>::type coordinate_type;
231 typedef typename promote_floating_point<coordinate_type>::type factor_type;
232 typedef model::point
233 <
234 typename detail::robust_type<coordinate_type>::type,
235 geometry::dimension<point_type>::value,
236 typename geometry::coordinate_system<point_type>::type
237 > robust_point_type;
238
239 point_type min_point;
240 robust_point_type min_robust_point;
241 factor_type factor;
242 init_rescale_policy(geometry1, geometry2, min_point, min_robust_point,
243 factor, strategy1, strategy2);
244
245 return Policy(min_point, min_robust_point, factor);
246 }
247 };
248
249 // Specialization for no-rescaling
250 template <>
251 struct get_rescale_policy<no_rescale_policy>
252 {
253 template <typename Geometry, typename EnvelopeStrategy>
applyboost::geometry::detail::get_rescale_policy::get_rescale_policy254 static inline no_rescale_policy apply(Geometry const& , EnvelopeStrategy const&)
255 {
256 return no_rescale_policy();
257 }
258
259 template <typename Geometry1, typename Geometry2, typename EnvelopeStrategy1, typename EnvelopeStrategy2>
applyboost::geometry::detail::get_rescale_policy::get_rescale_policy260 static inline no_rescale_policy apply(Geometry1 const& , Geometry2 const& ,
261 EnvelopeStrategy1 const& , EnvelopeStrategy2 const& )
262 {
263 return no_rescale_policy();
264 }
265 };
266
267
268 }} // namespace detail::get_rescale_policy
269 #endif // DOXYGEN_NO_DETAIL
270
271 template
272 <
273 typename Point,
274 typename CSTag = typename geometry::cs_tag<Point>::type
275 >
276 struct rescale_policy_type
277 : public detail::get_rescale_policy::rescale_policy_type
278 <
279 Point,
280 #if defined(BOOST_GEOMETRY_USE_RESCALING)
281 boost::is_floating_point
282 <
283 typename geometry::coordinate_type<Point>::type
284 >::type::value
285 &&
286 boost::is_same
287 <
288 CSTag,
289 geometry::cartesian_tag
290 >::value
291 #else
292 false
293 #endif
294 >
295 {
296 static const bool is_point
297 = boost::is_same
298 <
299 typename geometry::tag<Point>::type,
300 geometry::point_tag
301 >::type::value;
302
303 BOOST_MPL_ASSERT_MSG((is_point),
304 INVALID_INPUT_GEOMETRY,
305 (typename geometry::tag<Point>::type));
306 };
307
308
309 template
310 <
311 typename Geometry1,
312 typename Geometry2,
313 typename CSTag = typename geometry::cs_tag<Geometry1>::type,
314 typename Tag1 = typename tag_cast
315 <
316 typename tag<Geometry1>::type,
317 box_tag,
318 pointlike_tag,
319 linear_tag,
320 areal_tag
321 >::type,
322 typename Tag2 = typename tag_cast
323 <
324 typename tag<Geometry2>::type,
325 box_tag,
326 pointlike_tag,
327 linear_tag,
328 areal_tag
329 >::type
330 >
331 struct rescale_overlay_policy_type
332 // Default: no rescaling
333 : public detail::get_rescale_policy::rescale_policy_type
334 <
335 typename geometry::point_type<Geometry1>::type,
336 false
337 >
338 {};
339
340 // Areal/areal: get rescale policy based on coordinate type
341 template
342 <
343 typename Geometry1,
344 typename Geometry2,
345 typename CSTag
346 >
347 struct rescale_overlay_policy_type<Geometry1, Geometry2, CSTag, areal_tag, areal_tag>
348 : public rescale_policy_type
349 <
350 typename geometry::point_type<Geometry1>::type,
351 CSTag
352 >
353 {};
354
355
356 #ifndef DOXYGEN_NO_DETAIL
357 namespace detail { namespace get_rescale_policy
358 {
359
360
361 // get envelope strategy compatible with relate strategy based on geometry tag
362 // and strategy cs_tag
363 template
364 <
365 typename Geometry,
366 typename Strategy,
367 typename Tag = typename geometry::tag<Geometry>::type,
368 typename CSTag = typename Strategy::cs_tag
369 >
370 struct get_envelope_strategy
371 {
372 typedef typename Strategy::envelope_strategy_type type;
373
applyboost::geometry::detail::get_rescale_policy::get_envelope_strategy374 static inline type apply(Strategy const& strategy)
375 {
376 return strategy.get_envelope_strategy();
377 }
378 };
379
380 template <typename Geometry, typename Strategy, typename CSTag>
381 struct get_envelope_strategy<Geometry, Strategy, box_tag, CSTag>
382 {
383 typedef typename Strategy::envelope_box_strategy_type type;
384
applyboost::geometry::detail::get_rescale_policy::get_envelope_strategy385 static inline type apply(Strategy const& )
386 {
387 return type();
388 }
389 };
390
391 // NOTE: within::xxx_point_point shouldn't have a getter for envelope strategy
392 // so dispatch by CStag. In the future strategies should probably be redesigned.
393 template <typename Geometry, typename Strategy>
394 struct get_envelope_strategy<Geometry, Strategy, point_tag, cartesian_tag>
395 {
396 typedef strategy::envelope::cartesian_point type;
397
applyboost::geometry::detail::get_rescale_policy::get_envelope_strategy398 static inline type apply(Strategy const& )
399 {
400 return type();
401 }
402 };
403 template <typename Geometry, typename Strategy>
404 struct get_envelope_strategy<Geometry, Strategy, point_tag, spherical_tag>
405 {
406 typedef strategy::envelope::spherical_point type;
407
applyboost::geometry::detail::get_rescale_policy::get_envelope_strategy408 static inline type apply(Strategy const& )
409 {
410 return type();
411 }
412 };
413
414 template <typename Geometry, typename Strategy>
415 struct get_envelope_strategy<Geometry, Strategy, multi_point_tag, cartesian_tag>
416 {
417 typedef strategy::envelope::cartesian_point type;
418
applyboost::geometry::detail::get_rescale_policy::get_envelope_strategy419 static inline type apply(Strategy const& )
420 {
421 return type();
422 }
423 };
424 template <typename Geometry, typename Strategy>
425 struct get_envelope_strategy<Geometry, Strategy, multi_point_tag, spherical_tag>
426 {
427 typedef strategy::envelope::spherical_point type;
428
applyboost::geometry::detail::get_rescale_policy::get_envelope_strategy429 static inline type apply(Strategy const& )
430 {
431 return type();
432 }
433 };
434
435
436 // utility for backward-compatibility either treating the argument as geometry
437 // or envelope strategy for get_rescale_policy
438 template
439 <
440 typename Geometry2OrStrategy,
441 typename Tag = typename geometry::tag<Geometry2OrStrategy>::type
442 >
443 struct get_rescale_policy_geometry_or_strategy
444 {
445 template <typename Policy, typename Geometry>
applyboost::geometry::detail::get_rescale_policy::get_rescale_policy_geometry_or_strategy446 static inline Policy apply(Geometry const& geometry, Geometry2OrStrategy const& geometry2)
447 {
448 typename geometry::strategy::envelope::services::default_strategy
449 <
450 typename geometry::tag<Geometry>::type,
451 typename geometry::cs_tag<Geometry>::type
452 >::type strategy1;
453 typename geometry::strategy::envelope::services::default_strategy
454 <
455 typename geometry::tag<Geometry2OrStrategy>::type,
456 typename geometry::cs_tag<Geometry2OrStrategy>::type
457 >::type strategy2;
458
459 return detail::get_rescale_policy::get_rescale_policy
460 <
461 Policy
462 >::apply(geometry, geometry2, strategy1, strategy2);
463 }
464 };
465
466 template <typename Strategy>
467 struct get_rescale_policy_geometry_or_strategy<Strategy, void>
468 {
469 template <typename Policy, typename Geometry>
applyboost::geometry::detail::get_rescale_policy::get_rescale_policy_geometry_or_strategy470 static inline Policy apply(Geometry const& geometry, Strategy const& strategy)
471 {
472 return detail::get_rescale_policy::get_rescale_policy
473 <
474 Policy
475 >::apply(geometry,
476 get_envelope_strategy
477 <
478 Geometry, Strategy
479 >::apply(strategy));
480 }
481 };
482
483
484 }} // namespace detail::get_rescale_policy
485 #endif // DOXYGEN_NO_DETAIL
486
487
488 template <typename Policy, typename Geometry>
get_rescale_policy(Geometry const & geometry)489 inline Policy get_rescale_policy(Geometry const& geometry)
490 {
491 typename geometry::strategy::envelope::services::default_strategy
492 <
493 typename geometry::tag<Geometry>::type,
494 typename geometry::cs_tag<Geometry>::type
495 >::type strategy;
496
497 return detail::get_rescale_policy::get_rescale_policy<Policy>::apply(geometry, strategy);
498 }
499
500 template <typename Policy, typename Geometry, typename Geometry2OrStrategy>
get_rescale_policy(Geometry const & geometry,Geometry2OrStrategy const & geometry2_or_strategy)501 inline Policy get_rescale_policy(Geometry const& geometry, Geometry2OrStrategy const& geometry2_or_strategy)
502 {
503 // if the second argument is a geometry use default strategy
504 // otherwise assume it's envelope strategy for the first argument
505 return detail::get_rescale_policy::get_rescale_policy_geometry_or_strategy
506 <
507 Geometry2OrStrategy
508 > ::template apply<Policy, Geometry>(geometry, geometry2_or_strategy);
509 }
510
511 template <typename Policy, typename Geometry1, typename Geometry2, typename IntersectionStrategy>
get_rescale_policy(Geometry1 const & geometry1,Geometry2 const & geometry2,IntersectionStrategy const & strategy)512 inline Policy get_rescale_policy(Geometry1 const& geometry1, Geometry2 const& geometry2,
513 IntersectionStrategy const& strategy)
514 {
515 return detail::get_rescale_policy::get_rescale_policy
516 <
517 Policy
518 >::apply(geometry1, geometry2,
519 detail::get_rescale_policy::get_envelope_strategy
520 <
521 Geometry1, IntersectionStrategy
522 >::apply(strategy),
523 detail::get_rescale_policy::get_envelope_strategy
524 <
525 Geometry2, IntersectionStrategy
526 >::apply(strategy));
527 }
528
529
530 }} // namespace boost::geometry
531
532
533 #endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_GET_RESCALE_POLICY_HPP
534