1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2012 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 // Use, modification and distribution is subject to the Boost Software License,
9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP
17 #include <boost/geometry/core/assert.hpp>
19 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
20 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp>
22 #include <boost/geometry/util/condition.hpp>
24 namespace boost { namespace geometry {
26 #ifndef DOXYGEN_NO_DETAIL
27 namespace detail { namespace overlay {
29 template<typename AssignPolicy>
30 struct get_turn_info_linear_linear
32 static const bool handle_spikes = true;
39 typename RobustPolicy,
40 typename OutputIterator
42 static inline OutputIterator apply(
43 Point1 const& pi, Point1 const& pj, Point1 const& pk,
44 Point2 const& qi, Point2 const& qj, Point2 const& qk,
45 bool is_p_first, bool is_p_last,
46 bool is_q_first, bool is_q_last,
47 TurnInfo const& tp_model,
48 RobustPolicy const& robust_policy,
51 typedef intersection_info<Point1, Point2, typename TurnInfo::point_type, RobustPolicy>
54 inters_info inters(pi, pj, pk, qi, qj, qk, robust_policy);
56 char const method = inters.d_info().how;
58 // Copy, to copy possibly extended fields
59 TurnInfo tp = tp_model;
61 // Select method and apply
64 case 'a' : // collinear, "at"
65 case 'f' : // collinear, "from"
66 case 's' : // starts from the middle
67 get_turn_info_for_endpoint<AssignPolicy, true, true>
68 ::apply(pi, pj, pk, qi, qj, qk,
69 is_p_first, is_p_last, is_q_first, is_q_last,
70 tp_model, inters, method_none, out);
73 case 'd' : // disjoint: never do anything
78 if ( get_turn_info_for_endpoint<AssignPolicy, false, true>
79 ::apply(pi, pj, pk, qi, qj, qk,
80 is_p_first, is_p_last, is_q_first, is_q_last,
81 tp_model, inters, method_touch_interior, out) )
87 typedef touch_interior
92 // If Q (1) arrives (1)
93 if ( inters.d_info().arrival[1] == 1)
95 policy::template apply<0>(pi, pj, pk, qi, qj, qk,
96 tp, inters.i_info(), inters.d_info(),
104 typename inters_info::cs_tag,
105 typename inters_info::robust_point2_type,
106 typename inters_info::robust_point1_type
107 > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(),
108 inters.rpi(), inters.rpj(), inters.rpk());
110 policy::template apply<1>(qi, qj, qk, pi, pj, pk,
111 tp, inters.i_info(), inters.d_info(),
115 if ( tp.operations[0].operation == operation_blocked )
117 tp.operations[1].is_collinear = true;
119 if ( tp.operations[1].operation == operation_blocked )
121 tp.operations[0].is_collinear = true;
124 replace_method_and_operations_tm(tp.method,
125 tp.operations[0].operation,
126 tp.operations[1].operation);
128 AssignPolicy::apply(tp, pi, qi, inters);
135 crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
136 tp, inters.i_info(), inters.d_info());
138 replace_operations_i(tp.operations[0].operation, tp.operations[1].operation);
140 AssignPolicy::apply(tp, pi, qi, inters);
146 // Both touch (both arrive there)
147 if ( get_turn_info_for_endpoint<AssignPolicy, false, true>
148 ::apply(pi, pj, pk, qi, qj, qk,
149 is_p_first, is_p_last, is_q_first, is_q_last,
150 tp_model, inters, method_touch, out) )
156 touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
157 tp, inters.i_info(), inters.d_info(), inters.sides());
159 // workarounds for touch<> not taking spikes into account starts here
160 // those was discovered empirically
161 // touch<> is not symmetrical!
162 // P spikes and Q spikes may produce various operations!
163 // TODO: this is not optimal solution - think about rewriting touch<>
165 if ( tp.operations[0].operation == operation_blocked
166 && tp.operations[1].operation == operation_blocked )
168 // two touching spikes on the same line
169 if ( inters.is_spike_p() && inters.is_spike_q() )
171 tp.operations[0].operation = operation_union;
172 tp.operations[1].operation = operation_union;
176 tp.operations[0].is_collinear = true;
177 tp.operations[1].is_collinear = true;
180 else if ( tp.operations[0].operation == operation_blocked )
182 // a spike on P on the same line with Q1
183 if ( inters.is_spike_p() )
185 if ( inters.sides().qk_wrt_p1() == 0 )
187 tp.operations[0].is_collinear = true;
191 tp.operations[0].operation = operation_union;
196 tp.operations[1].is_collinear = true;
199 else if ( tp.operations[1].operation == operation_blocked )
201 // a spike on Q on the same line with P1
202 if ( inters.is_spike_q() )
204 if ( inters.sides().pk_wrt_q1() == 0 )
206 tp.operations[1].is_collinear = true;
210 tp.operations[1].operation = operation_union;
215 tp.operations[0].is_collinear = true;
218 else if ( tp.operations[0].operation == operation_continue
219 && tp.operations[1].operation == operation_continue )
221 // P spike on the same line with Q2 (opposite)
222 if ( inters.sides().pk_wrt_q1() == -inters.sides().qk_wrt_q1()
223 && inters.is_spike_p() )
225 tp.operations[0].operation = operation_union;
226 tp.operations[1].operation = operation_union;
229 else if ( tp.operations[0].operation == operation_none
230 && tp.operations[1].operation == operation_none )
232 // spike not handled by touch<>
233 bool const is_p = inters.is_spike_p();
234 bool const is_q = inters.is_spike_q();
238 tp.operations[0].operation = operation_union;
239 tp.operations[1].operation = operation_union;
241 if ( inters.sides().pk_wrt_q2() == 0 )
243 tp.operations[0].operation = operation_continue; // will be converted to i
246 tp.operations[0].is_collinear = true;
250 if ( inters.sides().qk_wrt_p2() == 0 )
252 tp.operations[1].operation = operation_continue; // will be converted to i
255 tp.operations[1].is_collinear = true;
261 // workarounds for touch<> not taking spikes into account ends here
263 replace_method_and_operations_tm(tp.method,
264 tp.operations[0].operation,
265 tp.operations[1].operation);
267 // TODO: move this into the append_xxx and call for each turn?
268 AssignPolicy::apply(tp, pi, qi, inters);
270 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
271 || ! append_opposite_spikes<append_touches>(tp, inters,
272 is_p_last, is_q_last,
282 if ( get_turn_info_for_endpoint<AssignPolicy, true, true>
283 ::apply(pi, pj, pk, qi, qj, qk,
284 is_p_first, is_p_last, is_q_first, is_q_last,
285 tp_model, inters, method_equal, out) )
291 tp.operations[0].is_collinear = true;
292 tp.operations[1].is_collinear = true;
294 if ( ! inters.d_info().opposite )
297 // or collinear-and-ending at intersection point
298 equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
299 tp, inters.i_info(), inters.d_info(), inters.sides());
301 operation_type spike_op
302 = ( tp.operations[0].operation != operation_continue
303 || tp.operations[1].operation != operation_continue ) ?
308 turn_transformer_ec transformer(method_touch);
311 // TODO: move this into the append_xxx and call for each turn?
312 AssignPolicy::apply(tp, pi, qi, inters);
314 // conditionally handle spikes
315 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
316 || ! append_collinear_spikes(tp, inters,
317 is_p_last, is_q_last,
318 method_touch, spike_op,
321 *out++ = tp; // no spikes
326 // TODO: ignore for spikes or generate something else than opposite?
332 >::apply(pi, qi, tp, out, inters);
340 if ( get_turn_info_for_endpoint<AssignPolicy, true, true>
341 ::apply(pi, pj, pk, qi, qj, qk,
342 is_p_first, is_p_last, is_q_first, is_q_last,
343 tp_model, inters, method_collinear, out) )
349 // NOTE: this is for spikes since those are set in the turn_transformer_ec
350 tp.operations[0].is_collinear = true;
351 tp.operations[1].is_collinear = true;
353 if ( ! inters.d_info().opposite )
355 method_type method_replace = method_touch_interior;
356 operation_type spike_op = operation_continue;
358 if ( inters.d_info().arrival[0] == 0 )
360 // Collinear, but similar thus handled as equal
361 equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
362 tp, inters.i_info(), inters.d_info(), inters.sides());
364 method_replace = method_touch;
365 if ( tp.operations[0].operation != operation_continue
366 || tp.operations[1].operation != operation_continue )
368 spike_op = operation_union;
373 collinear<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
374 tp, inters.i_info(), inters.d_info(), inters.sides());
376 //method_replace = method_touch_interior;
377 //spike_op = operation_continue;
381 turn_transformer_ec transformer(method_replace);
384 // TODO: move this into the append_xxx and call for each turn?
385 AssignPolicy::apply(tp, pi, qi, inters);
387 // conditionally handle spikes
388 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
389 || ! append_collinear_spikes(tp, inters,
390 is_p_last, is_q_last,
391 method_replace, spike_op,
400 // If this always 'm' ?
401 turn_transformer_ec transformer(method_touch_interior);
403 // conditionally handle spikes
404 if ( BOOST_GEOMETRY_CONDITION(handle_spikes) )
406 append_opposite_spikes<append_collinear_opposite>(tp, inters,
407 is_p_last, is_q_last,
411 // TODO: ignore for spikes?
412 // E.g. pass is_p_valid = !is_p_last && !is_pj_spike,
413 // the same with is_q_valid
419 >::apply(pi, pj, pk, qi, qj, qk,
420 tp, out, inters, inters.sides(),
421 transformer, !is_p_last, !is_q_last);
429 if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) )
431 only_convert::apply(tp, inters.i_info());
433 // if any, only one of those should be true
435 && equals::equals_point_point(pi, tp.point) )
437 tp.operations[0].position = position_front;
440 && equals::equals_point_point(pj, tp.point) )
442 tp.operations[0].position = position_back;
445 && equals::equals_point_point(qi, tp.point) )
447 tp.operations[1].position = position_front;
450 && equals::equals_point_point(qj, tp.point) )
452 tp.operations[1].position = position_back;
455 AssignPolicy::apply(tp, pi, qi, inters);
462 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS)
463 std::cout << "TURN: Unknown method: " << method << std::endl;
465 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
466 throw turn_info_exception(method);
475 template <typename TurnInfo,
476 typename IntersectionInfo,
478 static inline bool append_collinear_spikes(TurnInfo & tp,
479 IntersectionInfo const& inters_info,
480 bool is_p_last, bool is_q_last,
481 method_type method, operation_type spike_op,
484 // method == touch || touch_interior
485 // both position == middle
487 bool is_p_spike = tp.operations[0].operation == spike_op
489 && inters_info.is_spike_p();
490 bool is_q_spike = tp.operations[1].operation == spike_op
492 && inters_info.is_spike_q();
494 if ( is_p_spike && is_q_spike )
496 if ( tp.method == method_equal
497 && tp.operations[0].operation == operation_continue
498 && tp.operations[1].operation == operation_continue )
500 // treat both non-opposite collinear spikes as no-spikes
505 tp.operations[0].operation = operation_blocked;
506 tp.operations[1].operation = operation_blocked;
508 tp.operations[0].operation = operation_intersection;
509 tp.operations[1].operation = operation_intersection;
514 else if ( is_p_spike )
517 tp.operations[0].operation = operation_blocked;
518 tp.operations[1].operation = operation_union;
520 tp.operations[0].operation = operation_intersection;
521 //tp.operations[1].operation = operation_union;
526 else if ( is_q_spike )
529 tp.operations[0].operation = operation_union;
530 tp.operations[1].operation = operation_blocked;
532 //tp.operations[0].operation = operation_union;
533 tp.operations[1].operation = operation_intersection;
542 enum append_version { append_touches, append_collinear_opposite };
544 template <append_version Version,
546 typename IntersectionInfo,
548 static inline bool append_opposite_spikes(TurnInfo & tp,
549 IntersectionInfo const& inters,
550 bool is_p_last, bool is_q_last,
553 static const bool is_version_touches = (Version == append_touches);
555 bool is_p_spike = ( is_version_touches ?
556 ( tp.operations[0].operation == operation_continue
557 || tp.operations[0].operation == operation_intersection ) :
560 && inters.is_spike_p();
561 bool is_q_spike = ( is_version_touches ?
562 ( tp.operations[1].operation == operation_continue
563 || tp.operations[1].operation == operation_intersection ) :
566 && inters.is_spike_q();
571 && ( BOOST_GEOMETRY_CONDITION(is_version_touches)
572 || inters.d_info().arrival[0] == 1 ) )
574 if ( BOOST_GEOMETRY_CONDITION(is_version_touches) )
576 tp.operations[0].is_collinear = true;
577 tp.operations[1].is_collinear = false;
578 tp.method = method_touch;
580 else // Version == append_collinear_opposite
582 tp.operations[0].is_collinear = true;
583 tp.operations[1].is_collinear = false;
585 BOOST_GEOMETRY_ASSERT(inters.i_info().count > 1);
587 base_turn_handler::assign_point(tp, method_touch_interior,
590 AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters);
593 tp.operations[0].operation = operation_blocked;
594 tp.operations[1].operation = operation_intersection;
596 tp.operations[0].operation = operation_intersection;
597 //tp.operations[1].operation = operation_intersection;
604 && ( BOOST_GEOMETRY_CONDITION(is_version_touches)
605 || inters.d_info().arrival[1] == 1 ) )
607 if ( BOOST_GEOMETRY_CONDITION(is_version_touches) )
609 tp.operations[0].is_collinear = false;
610 tp.operations[1].is_collinear = true;
611 tp.method = method_touch;
613 else // Version == append_collinear_opposite
615 tp.operations[0].is_collinear = false;
616 tp.operations[1].is_collinear = true;
618 BOOST_GEOMETRY_ASSERT(inters.i_info().count > 0);
620 base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 0);
622 AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters);
625 tp.operations[0].operation = operation_intersection;
626 tp.operations[1].operation = operation_blocked;
628 //tp.operations[0].operation = operation_intersection;
629 tp.operations[1].operation = operation_intersection;
638 static inline void replace_method_and_operations_tm(method_type & method,
639 operation_type & op0,
640 operation_type & op1)
642 if ( op0 == operation_blocked && op1 == operation_blocked )
644 // NOTE: probably only if methods are WRT IPs, not segments!
645 method = (method == method_touch ? method_equal : method_collinear);
646 op0 = operation_continue;
647 op1 = operation_continue;
651 if ( op0 == operation_continue || op0 == operation_blocked )
653 op0 = operation_intersection;
655 else if ( op0 == operation_intersection )
657 op0 = operation_union;
660 if ( op1 == operation_continue || op1 == operation_blocked )
662 op1 = operation_intersection;
664 else if ( op1 == operation_intersection )
666 op1 = operation_union;
670 if ( method == method_error )
672 method = method_touch_interior;
673 op0 = operation_union;
674 op1 = operation_union;
679 class turn_transformer_ec
682 explicit turn_transformer_ec(method_type method_t_or_m)
683 : m_method(method_t_or_m)
686 template <typename Turn>
687 void operator()(Turn & turn) const
689 operation_type & op0 = turn.operations[0].operation;
690 operation_type & op1 = turn.operations[1].operation;
692 BOOST_GEOMETRY_ASSERT(op0 != operation_blocked || op1 != operation_blocked );
694 if ( op0 == operation_blocked )
696 op0 = operation_intersection;
698 else if ( op0 == operation_intersection )
700 op0 = operation_union;
703 if ( op1 == operation_blocked )
705 op1 = operation_intersection;
707 else if ( op1 == operation_intersection )
709 op1 = operation_union;
712 if ( op0 == operation_intersection || op0 == operation_union
713 || op1 == operation_intersection || op1 == operation_union )
715 turn.method = m_method;
718 // TODO: is this correct?
719 // it's equivalent to comparing to operation_blocked at the beginning of the function
720 turn.operations[0].is_collinear = op0 != operation_intersection;
721 turn.operations[1].is_collinear = op1 != operation_intersection;
725 method_type m_method;
728 static inline void replace_operations_i(operation_type & op0, operation_type & op1)
730 if ( op0 == operation_intersection )
732 op0 = operation_union;
735 if ( op1 == operation_intersection )
737 op1 = operation_union;
742 }} // namespace detail::overlay
743 #endif // DOXYGEN_NO_DETAIL
745 }} // namespace boost::geometry
747 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LL_HPP