1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2013, 2014, 2015, 2017, 2018.
7 // Modifications copyright (c) 2013-2018 Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, 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_OVERLAY_GET_TURN_INFO_LA_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP
18 #include <boost/throw_exception.hpp>
20 #include <boost/geometry/core/assert.hpp>
22 #include <boost/geometry/util/condition.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp>
27 // TEMP, for spikes detector
28 //#include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
30 namespace boost { namespace geometry {
32 #ifndef DOXYGEN_NO_DETAIL
33 namespace detail { namespace overlay {
35 template<typename AssignPolicy>
36 struct get_turn_info_linear_areal
38 // Currently only Linear spikes are handled
39 // Areal spikes are ignored
40 static const bool handle_spikes = true;
44 typename UniqueSubRange1,
45 typename UniqueSubRange2,
47 typename UmbrellaStrategy,
48 typename RobustPolicy,
49 typename OutputIterator
51 static inline OutputIterator apply(
52 UniqueSubRange1 const& range_p,
53 UniqueSubRange2 const& range_q,
54 TurnInfo const& tp_model,
55 UmbrellaStrategy const& umbrella_strategy,
56 RobustPolicy const& robust_policy,
59 typedef intersection_info
61 UniqueSubRange1, UniqueSubRange2,
62 typename TurnInfo::point_type,
67 inters_info inters(range_p, range_q, umbrella_strategy, robust_policy);
69 char const method = inters.d_info().how;
71 // Copy, to copy possibly extended fields
72 TurnInfo tp = tp_model;
74 // Select method and apply
77 case 'a' : // collinear, "at"
78 case 'f' : // collinear, "from"
79 case 's' : // starts from the middle
80 get_turn_info_for_endpoint<true, true>(range_p, range_q,
81 tp_model, inters, method_none, out,
82 umbrella_strategy.get_point_in_point_strategy());
85 case 'd' : // disjoint: never do anything
90 if ( get_turn_info_for_endpoint<false, true>(range_p, range_q,
91 tp_model, inters, method_touch_interior, out,
92 umbrella_strategy.get_point_in_point_strategy()) )
98 typedef touch_interior<TurnInfo> handler;
100 // If Q (1) arrives (1)
101 if ( inters.d_info().arrival[1] == 1 )
103 handler::template apply<0>(range_p, range_q, tp,
104 inters.i_info(), inters.d_info(),
105 inters.sides(), umbrella_strategy);
110 handler::template apply<1>(range_q, range_p,
111 tp, inters.i_info(), inters.d_info(),
112 inters.get_swapped_sides(), umbrella_strategy);
115 if ( tp.operations[1].operation == operation_blocked )
117 tp.operations[0].is_collinear = true;
120 replace_method_and_operations_tm(tp.method,
121 tp.operations[0].operation,
122 tp.operations[1].operation);
124 // this function assumes that 'u' must be set for a spike
125 calculate_spike_operation(tp.operations[0].operation,
127 umbrella_strategy.get_point_in_point_strategy());
135 crosses<TurnInfo>::apply(tp, inters.i_info(), inters.d_info());
137 replace_operations_i(tp.operations[0].operation, tp.operations[1].operation);
144 // Both touch (both arrive there)
145 if ( get_turn_info_for_endpoint<false, true>(range_p, range_q,
146 tp_model, inters, method_touch, out,
147 umbrella_strategy.get_point_in_point_strategy()) )
153 touch<TurnInfo>::apply(range_p, range_q, tp,
154 inters.i_info(), inters.d_info(), inters.sides(),
157 if ( tp.operations[1].operation == operation_blocked )
159 tp.operations[0].is_collinear = true;
162 // workarounds for touch<> not taking spikes into account starts here
163 // those was discovered empirically
164 // touch<> is not symmetrical!
165 // P spikes and Q spikes may produce various operations!
166 // Only P spikes are valid for L/A
167 // TODO: this is not optimal solution - think about rewriting touch<>
169 if ( tp.operations[0].operation == operation_blocked )
171 // a spike on P on the same line with Q1
172 if ( inters.is_spike_p() )
174 if ( inters.sides().qk_wrt_p1() == 0 )
176 tp.operations[0].is_collinear = true;
180 tp.operations[0].operation = operation_union;
184 else if ( tp.operations[0].operation == operation_continue
185 && tp.operations[1].operation == operation_continue )
187 // P spike on the same line with Q2 (opposite)
188 if ( inters.sides().pk_wrt_q1() == -inters.sides().qk_wrt_q1()
189 && inters.is_spike_p() )
191 tp.operations[0].operation = operation_union;
192 tp.operations[1].operation = operation_union;
195 else if ( tp.operations[0].operation == operation_none
196 && tp.operations[1].operation == operation_none )
198 // spike not handled by touch<>
199 if ( inters.is_spike_p() )
201 tp.operations[0].operation = operation_intersection;
202 tp.operations[1].operation = operation_union;
204 if ( inters.sides().pk_wrt_q2() == 0 )
206 tp.operations[0].operation = operation_continue; // will be converted to i
207 tp.operations[0].is_collinear = true;
212 // workarounds for touch<> not taking spikes into account ends here
214 replace_method_and_operations_tm(tp.method,
215 tp.operations[0].operation,
216 tp.operations[1].operation);
219 = calculate_spike_operation(tp.operations[0].operation,
221 umbrella_strategy.get_point_in_point_strategy());
223 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
225 || ! append_opposite_spikes<append_touches>( // for 'i' or 'c' i???
235 if ( get_turn_info_for_endpoint<true, true>(range_p, range_q,
236 tp_model, inters, method_equal, out,
237 umbrella_strategy.get_point_in_point_strategy()) )
243 tp.operations[0].is_collinear = true;
245 if ( ! inters.d_info().opposite )
248 // or collinear-and-ending at intersection point
249 equal<TurnInfo>::apply(range_p, range_q, tp,
250 inters.i_info(), inters.d_info(), inters.sides(),
253 turn_transformer_ec<false> transformer(method_touch);
256 // conditionally handle spikes
257 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
258 || ! append_collinear_spikes(tp, inters,
259 method_touch, append_equal, out) )
261 *out++ = tp; // no spikes
270 >::apply(range_p, range_q,
279 if ( get_turn_info_for_endpoint<true, true>(
281 tp_model, inters, method_collinear, out,
282 umbrella_strategy.get_point_in_point_strategy()) )
288 tp.operations[0].is_collinear = true;
290 if ( ! inters.d_info().opposite )
292 method_type method_replace = method_touch_interior;
293 append_version_c version = append_collinear;
295 if ( inters.d_info().arrival[0] == 0 )
297 // Collinear, but similar thus handled as equal
298 equal<TurnInfo>::apply(range_p, range_q, tp,
299 inters.i_info(), inters.d_info(), inters.sides(),
302 method_replace = method_touch;
303 version = append_equal;
307 collinear<TurnInfo>::apply(range_p, range_q, tp,
308 inters.i_info(), inters.d_info(), inters.sides());
310 //method_replace = method_touch_interior;
311 //version = append_collinear;
314 turn_transformer_ec<false> transformer(method_replace);
317 // conditionally handle spikes
318 if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
319 || ! append_collinear_spikes(tp, inters,
320 method_replace, version, out) )
328 // Is this always 'm' ?
329 turn_transformer_ec<false> transformer(method_touch_interior);
331 // conditionally handle spikes
332 if ( BOOST_GEOMETRY_CONDITION(handle_spikes) )
334 append_opposite_spikes<append_collinear_opposite>(
338 // TODO: ignore for spikes?
339 // E.g. pass is_p_valid = !is_p_last && !is_pj_spike,
340 // the same with is_q_valid
346 >::apply(range_p, range_q,
348 inters.sides(), transformer);
356 if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) )
358 only_convert::apply(tp, inters.i_info());
360 if ( range_p.is_first_segment()
361 && equals::equals_point_point(range_p.at(0), tp.point,
362 umbrella_strategy.get_point_in_point_strategy()) )
364 tp.operations[0].position = position_front;
366 else if ( range_p.is_last_segment()
367 && equals::equals_point_point(range_p.at(1), tp.point,
368 umbrella_strategy.get_point_in_point_strategy()) )
370 tp.operations[0].position = position_back;
372 // tp.operations[1].position = position_middle;
380 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS)
381 std::cout << "TURN: Unknown method: " << method << std::endl;
383 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
384 BOOST_THROW_EXCEPTION(turn_info_exception(method));
393 template <typename Operation,
394 typename IntersectionInfo,
395 typename EqPPStrategy>
396 static inline bool calculate_spike_operation(Operation & op,
397 IntersectionInfo const& inters,
398 EqPPStrategy const& strategy)
400 bool is_p_spike = ( op == operation_union || op == operation_intersection )
401 && inters.is_spike_p();
405 int const pk_q1 = inters.sides().pk_wrt_q1();
407 bool going_in = pk_q1 < 0; // Pk on the right
408 bool going_out = pk_q1 > 0; // Pk on the left
410 int const qk_q1 = inters.sides().qk_wrt_q1();
413 if ( qk_q1 < 0 ) // Q turning R
415 // spike on the edge point
416 // if it's already known that the spike is going out this musn't be checked
418 && detail::equals::equals_point_point(inters.rpj(), inters.rqj(), strategy) )
420 int const pk_q2 = inters.sides().pk_wrt_q2();
421 going_in = pk_q1 < 0 && pk_q2 < 0; // Pk on the right of both
422 going_out = pk_q1 > 0 || pk_q2 > 0; // Pk on the left of one of them
425 else if ( qk_q1 > 0 ) // Q turning L
427 // spike on the edge point
428 // if it's already known that the spike is going in this musn't be checked
430 && detail::equals::equals_point_point(inters.rpj(), inters.rqj(), strategy) )
432 int const pk_q2 = inters.sides().pk_wrt_q2();
433 going_in = pk_q1 < 0 || pk_q2 < 0; // Pk on the right of one of them
434 going_out = pk_q1 > 0 && pk_q2 > 0; // Pk on the left of both
440 op = operation_intersection;
443 else if ( going_out )
445 op = operation_union;
453 enum append_version_c { append_equal, append_collinear };
455 template <typename TurnInfo,
456 typename IntersectionInfo,
458 static inline bool append_collinear_spikes(TurnInfo & tp,
459 IntersectionInfo const& inters,
460 method_type method, append_version_c version,
463 // method == touch || touch_interior
464 // both position == middle
466 bool is_p_spike = ( version == append_equal ?
467 ( tp.operations[0].operation == operation_union
468 || tp.operations[0].operation == operation_intersection ) :
469 tp.operations[0].operation == operation_continue )
470 && inters.is_spike_p();
472 // TODO: throw an exception for spike in Areal?
473 /*bool is_q_spike = tp.operations[1].operation == operation_continue
474 && inters.is_spike_q();
476 // both are collinear spikes on the same IP, we can just follow both
477 if ( is_p_spike && is_q_spike )
481 // spike on Linear - it's turning back on the boundary of Areal
486 tp.operations[0].operation = operation_blocked;
487 tp.operations[1].operation = operation_union;
489 tp.operations[0].operation = operation_continue; // boundary
490 //tp.operations[1].operation = operation_union;
495 // spike on Areal - Linear is going outside
496 /*else if ( is_q_spike )
499 tp.operations[0].operation = operation_union;
500 tp.operations[1].operation = operation_continue;
510 enum append_version_o { append_touches, append_collinear_opposite };
512 template <append_version_o Version,
514 typename IntersectionInfo,
516 static inline bool append_opposite_spikes(TurnInfo & tp,
517 IntersectionInfo const& inters,
520 static const bool is_version_touches = (Version == append_touches);
522 bool is_p_spike = ( is_version_touches ?
523 ( tp.operations[0].operation == operation_continue
524 || tp.operations[0].operation == operation_intersection ) : // i ???
526 && inters.is_spike_p();
528 // TODO: throw an exception for spike in Areal?
529 /*bool is_q_spike = ( ( Version == append_touches
530 && tp.operations[1].operation == operation_continue )
531 || ( Version == append_collinear_opposite
532 && tp.operations[1].operation == operation_none ) )
533 && inters.is_spike_q();
535 if ( is_p_spike && is_q_spike )
543 if ( BOOST_GEOMETRY_CONDITION(is_version_touches)
544 || inters.d_info().arrival[0] == 1 )
546 if ( BOOST_GEOMETRY_CONDITION(is_version_touches) )
548 tp.operations[0].is_collinear = true;
549 //tp.operations[1].is_collinear = false;
550 tp.method = method_touch;
554 tp.operations[0].is_collinear = true;
555 //tp.operations[1].is_collinear = false;
557 BOOST_GEOMETRY_ASSERT(inters.i_info().count > 1);
558 base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1);
561 tp.operations[0].operation = operation_blocked;
562 tp.operations[1].operation = operation_continue; // boundary
564 tp.operations[0].operation = operation_continue; // boundary
565 //tp.operations[1].operation = operation_continue; // boundary
571 /*else if ( is_q_spike )
573 tp.operations[0].is_collinear = true;
574 tp.method = is_version_touches ? method_touch : method_touch_interior;
575 tp.operations[0].operation = operation_continue;
576 tp.operations[1].operation = operation_continue; // boundary
586 static inline void replace_method_and_operations_tm(method_type & method,
587 operation_type & op0,
588 operation_type & op1)
590 if ( op0 == operation_blocked && op1 == operation_blocked )
592 // NOTE: probably only if methods are WRT IPs, not segments!
593 method = (method == method_touch ? method_equal : method_collinear);
596 // Assuming G1 is always Linear
597 if ( op0 == operation_blocked )
599 op0 = operation_continue;
602 if ( op1 == operation_blocked )
604 op1 = operation_continue;
606 else if ( op1 == operation_intersection )
608 op1 = operation_union;
612 if ( method == method_error )
614 method = method_touch_interior;
615 op0 = operation_union;
616 op1 = operation_union;
620 template <bool IsFront>
621 class turn_transformer_ec
624 explicit turn_transformer_ec(method_type method_t_or_m)
625 : m_method(method_t_or_m)
628 template <typename Turn>
629 void operator()(Turn & turn) const
631 operation_type & op0 = turn.operations[0].operation;
632 operation_type & op1 = turn.operations[1].operation;
634 // NOTE: probably only if methods are WRT IPs, not segments!
635 if ( BOOST_GEOMETRY_CONDITION(IsFront)
636 || op0 == operation_intersection || op0 == operation_union
637 || op1 == operation_intersection || op1 == operation_union )
639 turn.method = m_method;
642 turn.operations[0].is_collinear = op0 != operation_blocked;
644 // Assuming G1 is always Linear
645 if ( op0 == operation_blocked )
647 op0 = operation_continue;
650 if ( op1 == operation_blocked )
652 op1 = operation_continue;
654 else if ( op1 == operation_intersection )
656 op1 = operation_union;
661 method_type m_method;
664 static inline void replace_operations_i(operation_type & /*op0*/, operation_type & op1)
666 // assuming Linear is always the first one
667 op1 = operation_union;
670 // NOTE: Spikes may NOT be handled for Linear endpoints because it's not
671 // possible to define a spike on an endpoint. Areal geometries must
672 // NOT have spikes at all. One thing that could be done is to throw
673 // an exception when spike is detected in Areal geometry.
675 template <bool EnableFirst,
677 typename UniqueSubRange1,
678 typename UniqueSubRange2,
680 typename IntersectionInfo,
681 typename OutputIterator,
682 typename EqPPStrategy>
683 static inline bool get_turn_info_for_endpoint(
684 UniqueSubRange1 const& range_p,
685 UniqueSubRange2 const& range_q,
686 TurnInfo const& tp_model,
687 IntersectionInfo const& inters,
688 method_type /*method*/,
690 EqPPStrategy const& strategy)
692 namespace ov = overlay;
693 typedef ov::get_turn_info_for_endpoint<EnableFirst, EnableLast> get_info_e;
695 const std::size_t ip_count = inters.i_info().count;
696 // no intersection points
702 if (! range_p.is_first_segment() && ! range_p.is_last_segment())
704 // P sub-range has no end-points
708 typename IntersectionInfo::side_strategy_type const& sides
709 = inters.get_side_strategy();
711 linear_intersections intersections(range_p.at(0),
714 range_p.is_last_segment(),
715 range_q.is_last_segment(),
717 linear_intersections::ip_info const& ip0 = intersections.template get<0>();
718 linear_intersections::ip_info const& ip1 = intersections.template get<1>();
720 const bool opposite = inters.d_info().opposite;
722 // ANALYSE AND ASSIGN FIRST
724 // IP on the first point of Linear Geometry
725 bool was_first_point_handled = false;
726 if ( BOOST_GEOMETRY_CONDITION(EnableFirst)
727 && range_p.is_first_segment() && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication
729 TurnInfo tp = tp_model;
730 tp.operations[0].position = position_front;
731 tp.operations[1].position = position_middle;
733 if ( opposite ) // opposite -> collinear
735 tp.operations[0].operation = operation_continue;
736 tp.operations[1].operation = operation_union;
737 tp.method = ip0.is_qj ? method_touch : method_touch_interior;
741 // pi is the intersection point at qj or in the middle of q1
742 // so consider segments
743 // 1. pi at qj: qi-qj-pj and qi-qj-qk
744 // x: qi-qj, y: qj-qk, qz: qk
745 // 2. pi in the middle of q1: qi-pi-pj and qi-pi-qj
746 // x: qi-pi, y: pi-qj, qz: qj
747 // qi-pi, side the same as WRT q1
748 // pi-qj, side the same as WRT q1
750 method_type replaced_method = method_none;
751 int side_pj_y = 0, side_pj_x = 0, side_qz_x = 0;
752 // 1. ip0 or pi at qj
755 replaced_method = method_touch;
756 side_pj_y = sides.apply(range_q.at(1), range_q.at(2), range_p.at(1)); // pj wrt q2
757 side_pj_x = sides.apply(range_q.at(0), range_q.at(1), range_p.at(1)); // pj wrt q1
758 side_qz_x = sides.apply(range_q.at(0), range_q.at(1), range_q.at(2)); // qk wrt q1
760 // 2. ip0 or pi in the middle of q1
763 replaced_method = method_touch_interior;
764 side_pj_y = sides.apply(range_q.at(0), range_q.at(1), range_p.at(1)); // pj wrt q1
765 side_pj_x = side_pj_y; // pj wrt q1
766 side_qz_x = 0; // qj wrt q1
769 std::pair<operation_type, operation_type> operations
770 = get_info_e::operations_of_equal(side_pj_y, side_pj_x, side_qz_x);
772 tp.operations[0].operation = operations.first;
773 tp.operations[1].operation = operations.second;
775 turn_transformer_ec<true> transformer(replaced_method);
779 // equals<> or collinear<> will assign the second point,
780 // we'd like to assign the first one
781 base_turn_handler::assign_point(tp, tp.method, inters.i_info(), 0);
783 // NOTE: is_collinear is not set for the first endpoint of L
784 // for which there is no preceding segment
785 // here is_p_first_ip == true
786 tp.operations[0].is_collinear = false;
790 was_first_point_handled = true;
793 // ANALYSE AND ASSIGN LAST
795 // IP on the last point of Linear Geometry
796 if ( BOOST_GEOMETRY_CONDITION(EnableLast)
797 && range_p.is_last_segment()
798 && ( ip_count > 1 ? (ip1.is_pj && !ip1.is_qi) : (ip0.is_pj && !ip0.is_qi) ) ) // prevents duplication
800 TurnInfo tp = tp_model;
802 if ( inters.i_info().count > 1 )
804 //BOOST_GEOMETRY_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 );
805 tp.operations[0].is_collinear = true;
806 tp.operations[1].operation = opposite ? operation_continue : operation_union;
808 else //if ( result.template get<0>().count == 1 )
810 // pj is the intersection point at qj or in the middle of q1
811 // so consider segments
812 // 1. pj at qj: qi-qj-pi and qi-qj-qk
813 // x: qi-qj, y: qj-qk, qz: qk
814 // 2. pj in the middle of q1: qi-pj-pi and qi-pj-qj
815 // x: qi-pj, y: pj-qj, qz: qj
816 // qi-pj, the side is the same as WRT q1
817 // pj-qj, the side is the same as WRT q1
818 // side of qj WRT q1 is 0
819 int side_pi_y = 0, side_pi_x = 0, side_qz_x = 0;
820 // 1. ip0 or pj at qj
823 side_pi_y = sides.apply(range_q.at(1), range_q.at(2), range_p.at(0)); // pi wrt q2
824 side_pi_x = sides.apply(range_q.at(0), range_q.at(1), range_p.at(0)); // pi wrt q1
825 side_qz_x = sides.apply(range_q.at(0), range_q.at(1), range_q.at(2)); // qk wrt q1
827 // 2. ip0 or pj in the middle of q1
830 side_pi_y = sides.apply(range_q.at(0), range_q.at(1), range_p.at(0)); // pi wrt q1
831 side_pi_x = side_pi_y; // pi wrt q1
832 side_qz_x = 0; // qj wrt q1
835 std::pair<operation_type, operation_type> operations
836 = get_info_e::operations_of_equal(side_pi_y, side_pi_x, side_qz_x);
838 tp.operations[0].operation = operations.first;
839 tp.operations[1].operation = operations.second;
841 turn_transformer_ec<false> transformer(method_none);
844 tp.operations[0].is_collinear = tp.both(operation_continue);
847 tp.method = ( ip_count > 1 ? ip1.is_qj : ip0.is_qj ) ? method_touch : method_touch_interior;
848 tp.operations[0].operation = operation_blocked;
849 tp.operations[0].position = position_back;
850 tp.operations[1].position = position_middle;
852 // equals<> or collinear<> will assign the second point,
853 // we'd like to assign the first one
854 unsigned int ip_index = ip_count > 1 ? 1 : 0;
855 base_turn_handler::assign_point(tp, tp.method, inters.i_info(), ip_index);
859 // don't ignore the first IP if the segment is opposite
860 return !( opposite && ip_count > 1 ) || was_first_point_handled;
863 // don't ignore anything for now
867 template <typename Point1, typename Point2, typename IntersectionStrategy>
868 static inline bool equals_point_point(Point1 const& point1, Point2 const& point2,
869 IntersectionStrategy const& strategy)
871 return detail::equals::equals_point_point(point1, point2,
872 strategy.get_point_in_point_strategy());
876 }} // namespace detail::overlay
877 #endif // DOXYGEN_NO_DETAIL
879 }} // namespace boost::geometry
881 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP