]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
11fdf7f2 | 4 | // Copyright (c) 2013-2017 Adam Wulkiewicz, Lodz, Poland. |
7c673cae | 5 | |
20effc67 TL |
6 | // This file was modified by Oracle on 2014-2020. |
7 | // Modifications copyright (c) 2014-2020, Oracle and/or its affiliates. | |
7c673cae FG |
8 | |
9 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
10 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
11 | ||
12 | // Use, modification and distribution is subject to the Boost Software License, | |
13 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
14 | // http://www.boost.org/LICENSE_1_0.txt) | |
15 | ||
16 | #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_INTERSECTION_HPP | |
17 | #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_INTERSECTION_HPP | |
18 | ||
19 | #include <algorithm> | |
20 | ||
21 | #include <boost/geometry/core/exception.hpp> | |
22 | ||
23 | #include <boost/geometry/geometries/concepts/point_concept.hpp> | |
24 | #include <boost/geometry/geometries/concepts/segment_concept.hpp> | |
20effc67 | 25 | #include <boost/geometry/geometries/segment.hpp> |
7c673cae FG |
26 | |
27 | #include <boost/geometry/arithmetic/determinant.hpp> | |
28 | #include <boost/geometry/algorithms/detail/assign_values.hpp> | |
29 | #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> | |
30 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> | |
31 | #include <boost/geometry/algorithms/detail/recalculate.hpp> | |
32 | ||
33 | #include <boost/geometry/util/math.hpp> | |
34 | #include <boost/geometry/util/promote_integral.hpp> | |
35 | #include <boost/geometry/util/select_calculation_type.hpp> | |
36 | ||
20effc67 TL |
37 | #include <boost/geometry/strategy/cartesian/area.hpp> |
38 | #include <boost/geometry/strategy/cartesian/envelope.hpp> | |
39 | #include <boost/geometry/strategy/cartesian/expand_box.hpp> | |
40 | #include <boost/geometry/strategy/cartesian/expand_segment.hpp> | |
41 | ||
92f5a8d4 TL |
42 | #include <boost/geometry/strategies/cartesian/disjoint_box_box.hpp> |
43 | #include <boost/geometry/strategies/cartesian/disjoint_segment_box.hpp> | |
b32b8144 | 44 | #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp> |
92f5a8d4 | 45 | #include <boost/geometry/strategies/cartesian/point_in_point.hpp> |
b32b8144 | 46 | #include <boost/geometry/strategies/cartesian/point_in_poly_winding.hpp> |
7c673cae | 47 | #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp> |
b32b8144 | 48 | #include <boost/geometry/strategies/covered_by.hpp> |
7c673cae FG |
49 | #include <boost/geometry/strategies/intersection.hpp> |
50 | #include <boost/geometry/strategies/intersection_result.hpp> | |
b32b8144 FG |
51 | #include <boost/geometry/strategies/side.hpp> |
52 | #include <boost/geometry/strategies/side_info.hpp> | |
53 | #include <boost/geometry/strategies/within.hpp> | |
7c673cae | 54 | |
92f5a8d4 | 55 | #include <boost/geometry/policies/robustness/rescale_policy_tags.hpp> |
7c673cae | 56 | #include <boost/geometry/policies/robustness/robust_point_type.hpp> |
7c673cae | 57 | |
20effc67 | 58 | |
7c673cae FG |
59 | #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS) |
60 | # include <boost/geometry/io/wkt/write.hpp> | |
61 | #endif | |
62 | ||
63 | ||
64 | namespace boost { namespace geometry | |
65 | { | |
66 | ||
67 | ||
68 | namespace strategy { namespace intersection | |
69 | { | |
70 | ||
71 | ||
72 | /*! | |
73 | \see http://mathworld.wolfram.com/Line-LineIntersection.html | |
74 | */ | |
b32b8144 FG |
75 | template |
76 | < | |
77 | typename CalculationType = void | |
78 | > | |
79 | struct cartesian_segments | |
7c673cae | 80 | { |
92f5a8d4 TL |
81 | typedef cartesian_tag cs_tag; |
82 | ||
b32b8144 FG |
83 | typedef side::side_by_triangle<CalculationType> side_strategy_type; |
84 | ||
85 | static inline side_strategy_type get_side_strategy() | |
86 | { | |
87 | return side_strategy_type(); | |
88 | } | |
89 | ||
90 | template <typename Geometry1, typename Geometry2> | |
91 | struct point_in_geometry_strategy | |
92 | { | |
93 | typedef strategy::within::cartesian_winding | |
94 | < | |
95 | typename point_type<Geometry1>::type, | |
96 | typename point_type<Geometry2>::type, | |
97 | CalculationType | |
98 | > type; | |
99 | }; | |
100 | ||
101 | template <typename Geometry1, typename Geometry2> | |
102 | static inline typename point_in_geometry_strategy<Geometry1, Geometry2>::type | |
103 | get_point_in_geometry_strategy() | |
104 | { | |
105 | typedef typename point_in_geometry_strategy | |
106 | < | |
107 | Geometry1, Geometry2 | |
108 | >::type strategy_type; | |
109 | return strategy_type(); | |
110 | } | |
111 | ||
112 | template <typename Geometry> | |
113 | struct area_strategy | |
114 | { | |
11fdf7f2 | 115 | typedef area::cartesian |
b32b8144 | 116 | < |
b32b8144 FG |
117 | CalculationType |
118 | > type; | |
119 | }; | |
120 | ||
121 | template <typename Geometry> | |
122 | static inline typename area_strategy<Geometry>::type get_area_strategy() | |
123 | { | |
124 | typedef typename area_strategy<Geometry>::type strategy_type; | |
125 | return strategy_type(); | |
126 | } | |
127 | ||
128 | template <typename Geometry> | |
129 | struct distance_strategy | |
130 | { | |
131 | typedef distance::pythagoras | |
132 | < | |
133 | CalculationType | |
134 | > type; | |
135 | }; | |
136 | ||
137 | template <typename Geometry> | |
138 | static inline typename distance_strategy<Geometry>::type get_distance_strategy() | |
139 | { | |
140 | typedef typename distance_strategy<Geometry>::type strategy_type; | |
141 | return strategy_type(); | |
142 | } | |
143 | ||
92f5a8d4 | 144 | typedef envelope::cartesian<CalculationType> envelope_strategy_type; |
b32b8144 FG |
145 | |
146 | static inline envelope_strategy_type get_envelope_strategy() | |
147 | { | |
148 | return envelope_strategy_type(); | |
149 | } | |
7c673cae | 150 | |
92f5a8d4 TL |
151 | typedef expand::cartesian_segment expand_strategy_type; |
152 | ||
153 | static inline expand_strategy_type get_expand_strategy() | |
154 | { | |
155 | return expand_strategy_type(); | |
156 | } | |
157 | ||
158 | typedef within::cartesian_point_point point_in_point_strategy_type; | |
159 | ||
160 | static inline point_in_point_strategy_type get_point_in_point_strategy() | |
161 | { | |
162 | return point_in_point_strategy_type(); | |
163 | } | |
164 | ||
165 | typedef within::cartesian_point_point equals_point_point_strategy_type; | |
166 | ||
167 | static inline equals_point_point_strategy_type get_equals_point_point_strategy() | |
168 | { | |
169 | return equals_point_point_strategy_type(); | |
170 | } | |
171 | ||
172 | typedef disjoint::cartesian_box_box disjoint_box_box_strategy_type; | |
173 | ||
174 | static inline disjoint_box_box_strategy_type get_disjoint_box_box_strategy() | |
175 | { | |
176 | return disjoint_box_box_strategy_type(); | |
177 | } | |
178 | ||
179 | typedef disjoint::segment_box disjoint_segment_box_strategy_type; | |
180 | ||
181 | static inline disjoint_segment_box_strategy_type get_disjoint_segment_box_strategy() | |
182 | { | |
183 | return disjoint_segment_box_strategy_type(); | |
184 | } | |
185 | ||
186 | typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type; | |
187 | typedef covered_by::cartesian_point_box covered_by_point_box_strategy_type; | |
188 | typedef within::cartesian_point_box within_point_box_strategy_type; | |
189 | typedef envelope::cartesian_box envelope_box_strategy_type; | |
190 | typedef expand::cartesian_box expand_box_strategy_type; | |
191 | ||
7c673cae FG |
192 | template <typename CoordinateType, typename SegmentRatio> |
193 | struct segment_intersection_info | |
194 | { | |
11fdf7f2 | 195 | private : |
7c673cae FG |
196 | typedef typename select_most_precise |
197 | < | |
198 | CoordinateType, double | |
199 | >::type promoted_type; | |
200 | ||
201 | promoted_type comparable_length_a() const | |
202 | { | |
203 | return dx_a * dx_a + dy_a * dy_a; | |
204 | } | |
205 | ||
206 | promoted_type comparable_length_b() const | |
207 | { | |
208 | return dx_b * dx_b + dy_b * dy_b; | |
209 | } | |
210 | ||
211 | template <typename Point, typename Segment1, typename Segment2> | |
212 | void assign_a(Point& point, Segment1 const& a, Segment2 const& ) const | |
213 | { | |
214 | assign(point, a, dx_a, dy_a, robust_ra); | |
215 | } | |
216 | template <typename Point, typename Segment1, typename Segment2> | |
217 | void assign_b(Point& point, Segment1 const& , Segment2 const& b) const | |
218 | { | |
219 | assign(point, b, dx_b, dy_b, robust_rb); | |
220 | } | |
221 | ||
222 | template <typename Point, typename Segment> | |
223 | void assign(Point& point, Segment const& segment, CoordinateType const& dx, CoordinateType const& dy, SegmentRatio const& ratio) const | |
224 | { | |
225 | // Calculate the intersection point based on segment_ratio | |
226 | // Up to now, division was postponed. Here we divide using numerator/ | |
227 | // denominator. In case of integer this results in an integer | |
228 | // division. | |
229 | BOOST_GEOMETRY_ASSERT(ratio.denominator() != 0); | |
230 | ||
92f5a8d4 TL |
231 | typedef typename promote_integral<CoordinateType>::type calc_type; |
232 | ||
233 | calc_type const numerator | |
234 | = boost::numeric_cast<calc_type>(ratio.numerator()); | |
235 | calc_type const denominator | |
236 | = boost::numeric_cast<calc_type>(ratio.denominator()); | |
237 | calc_type const dx_calc = boost::numeric_cast<calc_type>(dx); | |
238 | calc_type const dy_calc = boost::numeric_cast<calc_type>(dy); | |
239 | ||
240 | set<0>(point, get<0, 0>(segment) | |
241 | + boost::numeric_cast<CoordinateType>(numerator * dx_calc | |
242 | / denominator)); | |
243 | set<1>(point, get<0, 1>(segment) | |
244 | + boost::numeric_cast<CoordinateType>(numerator * dy_calc | |
245 | / denominator)); | |
7c673cae FG |
246 | } |
247 | ||
11fdf7f2 TL |
248 | public : |
249 | template <typename Point, typename Segment1, typename Segment2> | |
250 | void calculate(Point& point, Segment1 const& a, Segment2 const& b) const | |
251 | { | |
252 | bool use_a = true; | |
253 | ||
254 | // Prefer one segment if one is on or near an endpoint | |
255 | bool const a_near_end = robust_ra.near_end(); | |
256 | bool const b_near_end = robust_rb.near_end(); | |
257 | if (a_near_end && ! b_near_end) | |
258 | { | |
259 | use_a = true; | |
260 | } | |
261 | else if (b_near_end && ! a_near_end) | |
262 | { | |
263 | use_a = false; | |
264 | } | |
265 | else | |
266 | { | |
267 | // Prefer shorter segment | |
268 | promoted_type const len_a = comparable_length_a(); | |
269 | promoted_type const len_b = comparable_length_b(); | |
270 | if (len_b < len_a) | |
271 | { | |
272 | use_a = false; | |
273 | } | |
274 | // else use_a is true but was already assigned like that | |
275 | } | |
276 | ||
277 | if (use_a) | |
278 | { | |
279 | assign_a(point, a, b); | |
280 | } | |
281 | else | |
282 | { | |
283 | assign_b(point, a, b); | |
284 | } | |
285 | } | |
286 | ||
7c673cae FG |
287 | CoordinateType dx_a, dy_a; |
288 | CoordinateType dx_b, dy_b; | |
289 | SegmentRatio robust_ra; | |
290 | SegmentRatio robust_rb; | |
291 | }; | |
292 | ||
293 | template <typename D, typename W, typename ResultType> | |
294 | static inline void cramers_rule(D const& dx_a, D const& dy_a, | |
295 | D const& dx_b, D const& dy_b, W const& wx, W const& wy, | |
296 | // out: | |
20effc67 | 297 | ResultType& nominator, ResultType& denominator) |
7c673cae FG |
298 | { |
299 | // Cramers rule | |
20effc67 TL |
300 | nominator = geometry::detail::determinant<ResultType>(dx_b, dy_b, wx, wy); |
301 | denominator = geometry::detail::determinant<ResultType>(dx_a, dy_a, dx_b, dy_b); | |
302 | // Ratio r = nominator/denominator | |
303 | // Collinear if denominator == 0, intersecting if 0 <= r <= 1 | |
7c673cae FG |
304 | // IntersectionPoint = (x1 + r * dx_a, y1 + r * dy_a) |
305 | } | |
306 | ||
92f5a8d4 | 307 | // Version for non-rescaled policies |
b32b8144 FG |
308 | template |
309 | < | |
92f5a8d4 TL |
310 | typename UniqueSubRange1, |
311 | typename UniqueSubRange2, | |
312 | typename Policy | |
b32b8144 FG |
313 | > |
314 | static inline typename Policy::return_type | |
92f5a8d4 TL |
315 | apply(UniqueSubRange1 const& range_p, |
316 | UniqueSubRange2 const& range_q, | |
317 | Policy const& policy) | |
7c673cae | 318 | { |
20effc67 | 319 | // Pass the same ranges both as normal ranges and as modelled ranges |
92f5a8d4 | 320 | return apply(range_p, range_q, policy, range_p, range_q); |
7c673cae FG |
321 | } |
322 | ||
20effc67 TL |
323 | // Version for non rescaled versions. |
324 | // The "modelled" parameter might be rescaled (will be removed later) | |
b32b8144 FG |
325 | template |
326 | < | |
92f5a8d4 TL |
327 | typename UniqueSubRange1, |
328 | typename UniqueSubRange2, | |
b32b8144 | 329 | typename Policy, |
20effc67 TL |
330 | typename ModelledUniqueSubRange1, |
331 | typename ModelledUniqueSubRange2 | |
b32b8144 FG |
332 | > |
333 | static inline typename Policy::return_type | |
92f5a8d4 TL |
334 | apply(UniqueSubRange1 const& range_p, |
335 | UniqueSubRange2 const& range_q, | |
20effc67 TL |
336 | Policy const& policy, |
337 | ModelledUniqueSubRange1 const& modelled_range_p, | |
338 | ModelledUniqueSubRange2 const& modelled_range_q) | |
7c673cae | 339 | { |
92f5a8d4 TL |
340 | typedef typename UniqueSubRange1::point_type point1_type; |
341 | typedef typename UniqueSubRange2::point_type point2_type; | |
342 | ||
343 | BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<point1_type>) ); | |
344 | BOOST_CONCEPT_ASSERT( (concepts::ConstPoint<point2_type>) ); | |
345 | ||
92f5a8d4 TL |
346 | point1_type const& p1 = range_p.at(0); |
347 | point1_type const& p2 = range_p.at(1); | |
348 | point2_type const& q1 = range_q.at(0); | |
349 | point2_type const& q2 = range_q.at(1); | |
350 | ||
20effc67 TL |
351 | // Declare segments, currently necessary for the policies |
352 | // (segment_crosses, segment_colinear, degenerate, one_degenerate, etc) | |
353 | model::referring_segment<point1_type const> const p(p1, p2); | |
354 | model::referring_segment<point2_type const> const q(q1, q2); | |
7c673cae | 355 | |
20effc67 TL |
356 | typedef typename select_most_precise |
357 | < | |
358 | typename geometry::coordinate_type<typename ModelledUniqueSubRange1::point_type>::type, | |
359 | typename geometry::coordinate_type<typename ModelledUniqueSubRange1::point_type>::type | |
360 | >::type modelled_coordinate_type; | |
361 | ||
362 | typedef segment_ratio<modelled_coordinate_type> ratio_type; | |
363 | segment_intersection_info | |
364 | < | |
365 | typename select_calculation_type<point1_type, point2_type, CalculationType>::type, | |
366 | ratio_type | |
367 | > sinfo; | |
368 | ||
369 | sinfo.dx_a = get<0>(p2) - get<0>(p1); // distance in x-dir | |
370 | sinfo.dx_b = get<0>(q2) - get<0>(q1); | |
371 | sinfo.dy_a = get<1>(p2) - get<1>(p1); // distance in y-dir | |
372 | sinfo.dy_b = get<1>(q2) - get<1>(q1); | |
7c673cae | 373 | |
20effc67 TL |
374 | return unified<ratio_type>(sinfo, p, q, policy, modelled_range_p, modelled_range_q); |
375 | } | |
376 | ||
377 | //! Returns true if two segments do not overlap. | |
378 | //! If not, then no further calculations need to be done. | |
379 | template | |
380 | < | |
381 | std::size_t Dimension, | |
382 | typename CoordinateType, | |
383 | typename PointP, | |
384 | typename PointQ | |
385 | > | |
386 | static inline bool disjoint_by_range(PointP const& p1, PointP const& p2, | |
387 | PointQ const& q1, PointQ const& q2) | |
388 | { | |
389 | CoordinateType minp = get<Dimension>(p1); | |
390 | CoordinateType maxp = get<Dimension>(p2); | |
391 | CoordinateType minq = get<Dimension>(q1); | |
392 | CoordinateType maxq = get<Dimension>(q2); | |
393 | if (minp > maxp) | |
394 | { | |
395 | std::swap(minp, maxp); | |
396 | } | |
397 | if (minq > maxq) | |
7c673cae | 398 | { |
20effc67 TL |
399 | std::swap(minq, maxq); |
400 | } | |
401 | ||
402 | // In this case, max(p) < min(q) | |
403 | // P Q | |
404 | // <-------> <-------> | |
405 | // (and the space in between is not extremely small) | |
406 | return math::smaller(maxp, minq) || math::smaller(maxq, minp); | |
407 | } | |
408 | ||
409 | // Implementation for either rescaled or non rescaled versions. | |
410 | template | |
411 | < | |
412 | typename RatioType, | |
413 | typename SegmentInfo, | |
414 | typename Segment1, | |
415 | typename Segment2, | |
416 | typename Policy, | |
417 | typename UniqueSubRange1, | |
418 | typename UniqueSubRange2 | |
419 | > | |
420 | static inline typename Policy::return_type | |
421 | unified(SegmentInfo& sinfo, | |
422 | Segment1 const& p, Segment2 const& q, Policy const&, | |
423 | UniqueSubRange1 const& range_p, | |
424 | UniqueSubRange2 const& range_q) | |
425 | { | |
426 | typedef typename UniqueSubRange1::point_type point1_type; | |
427 | typedef typename UniqueSubRange2::point_type point2_type; | |
428 | typedef typename select_most_precise | |
429 | < | |
430 | typename geometry::coordinate_type<point1_type>::type, | |
431 | typename geometry::coordinate_type<point2_type>::type | |
432 | >::type coordinate_type; | |
433 | ||
434 | point1_type const& p1 = range_p.at(0); | |
435 | point1_type const& p2 = range_p.at(1); | |
436 | point2_type const& q1 = range_q.at(0); | |
437 | point2_type const& q2 = range_q.at(1); | |
92f5a8d4 | 438 | |
20effc67 TL |
439 | using geometry::detail::equals::equals_point_point; |
440 | bool const p_is_point = equals_point_point(p1, p2, point_in_point_strategy_type()); | |
441 | bool const q_is_point = equals_point_point(q1, q2, point_in_point_strategy_type()); | |
442 | ||
443 | if (p_is_point && q_is_point) | |
444 | { | |
445 | return equals_point_point(p1, q2, point_in_point_strategy_type()) | |
446 | ? Policy::degenerate(p, true) | |
7c673cae FG |
447 | : Policy::disjoint() |
448 | ; | |
449 | } | |
450 | ||
20effc67 TL |
451 | if (disjoint_by_range<0, coordinate_type>(p1, p2, q1, q2) |
452 | || disjoint_by_range<1, coordinate_type>(p1, p2, q1, q2)) | |
453 | { | |
454 | return Policy::disjoint(); | |
455 | } | |
456 | ||
7c673cae | 457 | side_info sides; |
20effc67 TL |
458 | sides.set<0>(side_strategy_type::apply(q1, q2, p1), |
459 | side_strategy_type::apply(q1, q2, p2)); | |
7c673cae FG |
460 | |
461 | if (sides.same<0>()) | |
462 | { | |
463 | // Both points are at same side of other segment, we can leave | |
464 | return Policy::disjoint(); | |
465 | } | |
466 | ||
20effc67 TL |
467 | sides.set<1>(side_strategy_type::apply(p1, p2, q1), |
468 | side_strategy_type::apply(p1, p2, q2)); | |
7c673cae FG |
469 | |
470 | if (sides.same<1>()) | |
471 | { | |
472 | // Both points are at same side of other segment, we can leave | |
473 | return Policy::disjoint(); | |
474 | } | |
475 | ||
476 | bool collinear = sides.collinear(); | |
477 | ||
20effc67 TL |
478 | // Calculate the differences again |
479 | // (for rescaled version, this is different from dx_p etc) | |
480 | coordinate_type const dx_p = get<0>(p2) - get<0>(p1); | |
481 | coordinate_type const dx_q = get<0>(q2) - get<0>(q1); | |
482 | coordinate_type const dy_p = get<1>(p2) - get<1>(p1); | |
483 | coordinate_type const dy_q = get<1>(q2) - get<1>(q1); | |
7c673cae FG |
484 | |
485 | // r: ratio 0-1 where intersection divides A/B | |
486 | // (only calculated for non-collinear segments) | |
487 | if (! collinear) | |
488 | { | |
20effc67 TL |
489 | coordinate_type denominator_a, nominator_a; |
490 | coordinate_type denominator_b, nominator_b; | |
491 | ||
492 | cramers_rule(dx_p, dy_p, dx_q, dy_q, | |
493 | get<0>(p1) - get<0>(q1), | |
494 | get<1>(p1) - get<1>(q1), | |
495 | nominator_a, denominator_a); | |
496 | ||
497 | cramers_rule(dx_q, dy_q, dx_p, dy_p, | |
498 | get<0>(q1) - get<0>(p1), | |
499 | get<1>(q1) - get<1>(p1), | |
500 | nominator_b, denominator_b); | |
501 | ||
502 | math::detail::equals_factor_policy<coordinate_type> | |
503 | policy(dx_p, dy_p, dx_q, dy_q); | |
504 | ||
505 | coordinate_type const zero = 0; | |
506 | if (math::detail::equals_by_policy(denominator_a, zero, policy) | |
507 | || math::detail::equals_by_policy(denominator_b, zero, policy)) | |
7c673cae FG |
508 | { |
509 | // If this is the case, no rescaling is done for FP precision. | |
510 | // We set it to collinear, but it indicates a robustness issue. | |
20effc67 TL |
511 | sides.set<0>(0, 0); |
512 | sides.set<1>(0, 0); | |
7c673cae FG |
513 | collinear = true; |
514 | } | |
515 | else | |
516 | { | |
20effc67 TL |
517 | sinfo.robust_ra.assign(nominator_a, denominator_a); |
518 | sinfo.robust_rb.assign(nominator_b, denominator_b); | |
7c673cae FG |
519 | } |
520 | } | |
521 | ||
522 | if (collinear) | |
523 | { | |
524 | std::pair<bool, bool> const collinear_use_first | |
20effc67 TL |
525 | = is_x_more_significant(geometry::math::abs(dx_p), |
526 | geometry::math::abs(dy_p), | |
527 | geometry::math::abs(dx_q), | |
528 | geometry::math::abs(dy_q), | |
529 | p_is_point, q_is_point); | |
7c673cae FG |
530 | |
531 | if (collinear_use_first.second) | |
532 | { | |
533 | // Degenerate cases: segments of single point, lying on other segment, are not disjoint | |
534 | // This situation is collinear too | |
535 | ||
536 | if (collinear_use_first.first) | |
537 | { | |
20effc67 TL |
538 | return relate_collinear<0, Policy, RatioType>(p, q, |
539 | p1, p2, q1, q2, | |
540 | p_is_point, q_is_point); | |
7c673cae FG |
541 | } |
542 | else | |
543 | { | |
544 | // Y direction contains larger segments (maybe dx is zero) | |
20effc67 TL |
545 | return relate_collinear<1, Policy, RatioType>(p, q, |
546 | p1, p2, q1, q2, | |
547 | p_is_point, q_is_point); | |
7c673cae FG |
548 | } |
549 | } | |
550 | } | |
551 | ||
92f5a8d4 | 552 | return Policy::segments_crosses(sides, sinfo, p, q); |
7c673cae FG |
553 | } |
554 | ||
555 | private: | |
556 | // first is true if x is more significant | |
557 | // second is true if the more significant difference is not 0 | |
20effc67 | 558 | template <typename CoordinateType> |
7c673cae | 559 | static inline std::pair<bool, bool> |
20effc67 TL |
560 | is_x_more_significant(CoordinateType const& abs_dx_a, |
561 | CoordinateType const& abs_dy_a, | |
562 | CoordinateType const& abs_dx_b, | |
563 | CoordinateType const& abs_dy_b, | |
7c673cae FG |
564 | bool const a_is_point, |
565 | bool const b_is_point) | |
566 | { | |
567 | //BOOST_GEOMETRY_ASSERT_MSG(!(a_is_point && b_is_point), "both segments shouldn't be degenerated"); | |
568 | ||
569 | // for degenerated segments the second is always true because this function | |
570 | // shouldn't be called if both segments were degenerated | |
571 | ||
572 | if (a_is_point) | |
573 | { | |
20effc67 | 574 | return std::make_pair(abs_dx_b >= abs_dy_b, true); |
7c673cae FG |
575 | } |
576 | else if (b_is_point) | |
577 | { | |
20effc67 | 578 | return std::make_pair(abs_dx_a >= abs_dy_a, true); |
7c673cae FG |
579 | } |
580 | else | |
581 | { | |
20effc67 TL |
582 | CoordinateType const min_dx = (std::min)(abs_dx_a, abs_dx_b); |
583 | CoordinateType const min_dy = (std::min)(abs_dy_a, abs_dy_b); | |
7c673cae | 584 | return min_dx == min_dy ? |
20effc67 | 585 | std::make_pair(true, min_dx > CoordinateType(0)) : |
7c673cae FG |
586 | std::make_pair(min_dx > min_dy, true); |
587 | } | |
588 | } | |
589 | ||
590 | template | |
591 | < | |
592 | std::size_t Dimension, | |
b32b8144 | 593 | typename Policy, |
7c673cae FG |
594 | typename RatioType, |
595 | typename Segment1, | |
596 | typename Segment2, | |
597 | typename RobustPoint1, | |
598 | typename RobustPoint2 | |
599 | > | |
b32b8144 FG |
600 | static inline typename Policy::return_type |
601 | relate_collinear(Segment1 const& a, | |
602 | Segment2 const& b, | |
603 | RobustPoint1 const& robust_a1, RobustPoint1 const& robust_a2, | |
604 | RobustPoint2 const& robust_b1, RobustPoint2 const& robust_b2, | |
605 | bool a_is_point, bool b_is_point) | |
7c673cae FG |
606 | { |
607 | if (a_is_point) | |
608 | { | |
b32b8144 | 609 | return relate_one_degenerate<Policy, RatioType>(a, |
7c673cae FG |
610 | get<Dimension>(robust_a1), |
611 | get<Dimension>(robust_b1), get<Dimension>(robust_b2), | |
612 | true); | |
613 | } | |
614 | if (b_is_point) | |
615 | { | |
b32b8144 | 616 | return relate_one_degenerate<Policy, RatioType>(b, |
7c673cae FG |
617 | get<Dimension>(robust_b1), |
618 | get<Dimension>(robust_a1), get<Dimension>(robust_a2), | |
619 | false); | |
620 | } | |
b32b8144 | 621 | return relate_collinear<Policy, RatioType>(a, b, |
7c673cae FG |
622 | get<Dimension>(robust_a1), |
623 | get<Dimension>(robust_a2), | |
624 | get<Dimension>(robust_b1), | |
625 | get<Dimension>(robust_b2)); | |
626 | } | |
627 | ||
628 | /// Relate segments known collinear | |
629 | template | |
630 | < | |
b32b8144 | 631 | typename Policy, |
7c673cae FG |
632 | typename RatioType, |
633 | typename Segment1, | |
634 | typename Segment2, | |
20effc67 TL |
635 | typename Type1, |
636 | typename Type2 | |
7c673cae | 637 | > |
b32b8144 FG |
638 | static inline typename Policy::return_type |
639 | relate_collinear(Segment1 const& a, Segment2 const& b, | |
20effc67 TL |
640 | Type1 oa_1, Type1 oa_2, |
641 | Type2 ob_1, Type2 ob_2) | |
7c673cae FG |
642 | { |
643 | // Calculate the ratios where a starts in b, b starts in a | |
644 | // a1--------->a2 (2..7) | |
645 | // b1----->b2 (5..8) | |
646 | // length_a: 7-2=5 | |
647 | // length_b: 8-5=3 | |
648 | // b1 is located w.r.t. a at ratio: (5-2)/5=3/5 (on a) | |
649 | // b2 is located w.r.t. a at ratio: (8-2)/5=6/5 (right of a) | |
650 | // a1 is located w.r.t. b at ratio: (2-5)/3=-3/3 (left of b) | |
651 | // a2 is located w.r.t. b at ratio: (7-5)/3=2/3 (on b) | |
652 | // A arrives (a2 on b), B departs (b1 on a) | |
653 | ||
654 | // If both are reversed: | |
655 | // a2<---------a1 (7..2) | |
656 | // b2<-----b1 (8..5) | |
657 | // length_a: 2-7=-5 | |
658 | // length_b: 5-8=-3 | |
659 | // b1 is located w.r.t. a at ratio: (8-7)/-5=-1/5 (before a starts) | |
660 | // b2 is located w.r.t. a at ratio: (5-7)/-5=2/5 (on a) | |
661 | // a1 is located w.r.t. b at ratio: (7-8)/-3=1/3 (on b) | |
662 | // a2 is located w.r.t. b at ratio: (2-8)/-3=6/3 (after b ends) | |
663 | ||
664 | // If both one is reversed: | |
665 | // a1--------->a2 (2..7) | |
666 | // b2<-----b1 (8..5) | |
667 | // length_a: 7-2=+5 | |
668 | // length_b: 5-8=-3 | |
669 | // b1 is located w.r.t. a at ratio: (8-2)/5=6/5 (after a ends) | |
670 | // b2 is located w.r.t. a at ratio: (5-2)/5=3/5 (on a) | |
671 | // a1 is located w.r.t. b at ratio: (2-8)/-3=6/3 (after b ends) | |
672 | // a2 is located w.r.t. b at ratio: (7-8)/-3=1/3 (on b) | |
20effc67 TL |
673 | Type1 const length_a = oa_2 - oa_1; // no abs, see above |
674 | Type2 const length_b = ob_2 - ob_1; | |
7c673cae FG |
675 | |
676 | RatioType ra_from(oa_1 - ob_1, length_b); | |
677 | RatioType ra_to(oa_2 - ob_1, length_b); | |
678 | RatioType rb_from(ob_1 - oa_1, length_a); | |
679 | RatioType rb_to(ob_2 - oa_1, length_a); | |
680 | ||
681 | // use absolute measure to detect endpoints intersection | |
682 | // NOTE: it'd be possible to calculate bx_wrt_a using ax_wrt_b values | |
683 | int const a1_wrt_b = position_value(oa_1, ob_1, ob_2); | |
684 | int const a2_wrt_b = position_value(oa_2, ob_1, ob_2); | |
685 | int const b1_wrt_a = position_value(ob_1, oa_1, oa_2); | |
686 | int const b2_wrt_a = position_value(ob_2, oa_1, oa_2); | |
687 | ||
688 | // fix the ratios if necessary | |
689 | // CONSIDER: fixing ratios also in other cases, if they're inconsistent | |
690 | // e.g. if ratio == 1 or 0 (so IP at the endpoint) | |
691 | // but position value indicates that the IP is in the middle of the segment | |
692 | // because one of the segments is very long | |
693 | // In such case the ratios could be moved into the middle direction | |
694 | // by some small value (e.g. EPS+1ULP) | |
695 | if (a1_wrt_b == 1) | |
696 | { | |
697 | ra_from.assign(0, 1); | |
698 | rb_from.assign(0, 1); | |
699 | } | |
700 | else if (a1_wrt_b == 3) | |
701 | { | |
702 | ra_from.assign(1, 1); | |
703 | rb_to.assign(0, 1); | |
704 | } | |
705 | ||
706 | if (a2_wrt_b == 1) | |
707 | { | |
708 | ra_to.assign(0, 1); | |
709 | rb_from.assign(1, 1); | |
710 | } | |
711 | else if (a2_wrt_b == 3) | |
712 | { | |
713 | ra_to.assign(1, 1); | |
714 | rb_to.assign(1, 1); | |
715 | } | |
716 | ||
717 | if ((a1_wrt_b < 1 && a2_wrt_b < 1) || (a1_wrt_b > 3 && a2_wrt_b > 3)) | |
718 | //if ((ra_from.left() && ra_to.left()) || (ra_from.right() && ra_to.right())) | |
719 | { | |
720 | return Policy::disjoint(); | |
721 | } | |
722 | ||
723 | bool const opposite = math::sign(length_a) != math::sign(length_b); | |
724 | ||
725 | return Policy::segments_collinear(a, b, opposite, | |
726 | a1_wrt_b, a2_wrt_b, b1_wrt_a, b2_wrt_a, | |
727 | ra_from, ra_to, rb_from, rb_to); | |
728 | } | |
729 | ||
730 | /// Relate segments where one is degenerate | |
731 | template | |
732 | < | |
b32b8144 | 733 | typename Policy, |
7c673cae FG |
734 | typename RatioType, |
735 | typename DegenerateSegment, | |
20effc67 TL |
736 | typename Type1, |
737 | typename Type2 | |
7c673cae | 738 | > |
b32b8144 FG |
739 | static inline typename Policy::return_type |
740 | relate_one_degenerate(DegenerateSegment const& degenerate_segment, | |
20effc67 | 741 | Type1 d, Type2 s1, Type2 s2, |
b32b8144 | 742 | bool a_degenerate) |
7c673cae FG |
743 | { |
744 | // Calculate the ratios where ds starts in s | |
745 | // a1--------->a2 (2..6) | |
746 | // b1/b2 (4..4) | |
747 | // Ratio: (4-2)/(6-2) | |
748 | RatioType const ratio(d - s1, s2 - s1); | |
749 | ||
750 | if (!ratio.on_segment()) | |
751 | { | |
752 | return Policy::disjoint(); | |
753 | } | |
754 | ||
755 | return Policy::one_degenerate(degenerate_segment, ratio, a_degenerate); | |
756 | } | |
757 | ||
758 | template <typename ProjCoord1, typename ProjCoord2> | |
759 | static inline int position_value(ProjCoord1 const& ca1, | |
760 | ProjCoord2 const& cb1, | |
761 | ProjCoord2 const& cb2) | |
762 | { | |
763 | // S1x 0 1 2 3 4 | |
764 | // S2 |----------> | |
765 | return math::equals(ca1, cb1) ? 1 | |
766 | : math::equals(ca1, cb2) ? 3 | |
767 | : cb1 < cb2 ? | |
768 | ( ca1 < cb1 ? 0 | |
769 | : ca1 > cb2 ? 4 | |
770 | : 2 ) | |
771 | : ( ca1 > cb1 ? 0 | |
772 | : ca1 < cb2 ? 4 | |
773 | : 2 ); | |
774 | } | |
775 | }; | |
776 | ||
777 | ||
778 | #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS | |
779 | namespace services | |
780 | { | |
781 | ||
b32b8144 FG |
782 | template <typename CalculationType> |
783 | struct default_strategy<cartesian_tag, CalculationType> | |
7c673cae | 784 | { |
b32b8144 | 785 | typedef cartesian_segments<CalculationType> type; |
7c673cae FG |
786 | }; |
787 | ||
788 | } // namespace services | |
789 | #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS | |
790 | ||
791 | ||
792 | }} // namespace strategy::intersection | |
793 | ||
b32b8144 FG |
794 | namespace strategy |
795 | { | |
796 | ||
797 | namespace within { namespace services | |
798 | { | |
799 | ||
800 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
801 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, linear_tag, linear_tag, cartesian_tag, cartesian_tag> | |
802 | { | |
803 | typedef strategy::intersection::cartesian_segments<> type; | |
804 | }; | |
805 | ||
806 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
807 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, linear_tag, polygonal_tag, cartesian_tag, cartesian_tag> | |
808 | { | |
809 | typedef strategy::intersection::cartesian_segments<> type; | |
810 | }; | |
811 | ||
812 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
813 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, polygonal_tag, linear_tag, cartesian_tag, cartesian_tag> | |
814 | { | |
815 | typedef strategy::intersection::cartesian_segments<> type; | |
816 | }; | |
817 | ||
818 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
819 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, polygonal_tag, polygonal_tag, cartesian_tag, cartesian_tag> | |
820 | { | |
821 | typedef strategy::intersection::cartesian_segments<> type; | |
822 | }; | |
823 | ||
824 | }} // within::services | |
825 | ||
826 | namespace covered_by { namespace services | |
827 | { | |
828 | ||
829 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
830 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, linear_tag, linear_tag, cartesian_tag, cartesian_tag> | |
831 | { | |
832 | typedef strategy::intersection::cartesian_segments<> type; | |
833 | }; | |
834 | ||
835 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
836 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, linear_tag, polygonal_tag, cartesian_tag, cartesian_tag> | |
837 | { | |
838 | typedef strategy::intersection::cartesian_segments<> type; | |
839 | }; | |
840 | ||
841 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
842 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, polygonal_tag, linear_tag, cartesian_tag, cartesian_tag> | |
843 | { | |
844 | typedef strategy::intersection::cartesian_segments<> type; | |
845 | }; | |
846 | ||
847 | template <typename Geometry1, typename Geometry2, typename AnyTag1, typename AnyTag2> | |
848 | struct default_strategy<Geometry1, Geometry2, AnyTag1, AnyTag2, polygonal_tag, polygonal_tag, cartesian_tag, cartesian_tag> | |
849 | { | |
850 | typedef strategy::intersection::cartesian_segments<> type; | |
851 | }; | |
852 | ||
853 | }} // within::services | |
854 | ||
855 | } // strategy | |
856 | ||
7c673cae FG |
857 | }} // namespace boost::geometry |
858 | ||
859 | ||
860 | #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_INTERSECTION_HPP |