diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp | 306 |
1 files changed, 147 insertions, 159 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp index 46c1305cd7..f8272794bd 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp @@ -3,8 +3,8 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. -// This file was modified by Oracle on 2013, 2014, 2015, 2017. -// Modifications copyright (c) 2013-2017 Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015, 2017, 2018. +// Modifications copyright (c) 2013-2018 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle @@ -41,32 +41,30 @@ struct get_turn_info_linear_areal template < - typename Point1, - typename Point2, + typename UniqueSubRange1, + typename UniqueSubRange2, typename TurnInfo, typename IntersectionStrategy, typename RobustPolicy, typename OutputIterator > static inline OutputIterator apply( - Point1 const& pi, Point1 const& pj, Point1 const& pk, - Point2 const& qi, Point2 const& qj, Point2 const& qk, - bool is_p_first, bool is_p_last, - bool is_q_first, bool is_q_last, + UniqueSubRange1 const& range_p, + UniqueSubRange2 const& range_q, TurnInfo const& tp_model, - IntersectionStrategy const& intersection_strategy, + IntersectionStrategy const& strategy, RobustPolicy const& robust_policy, OutputIterator out) { typedef intersection_info < - Point1, Point2, + UniqueSubRange1, UniqueSubRange2, typename TurnInfo::point_type, IntersectionStrategy, RobustPolicy > inters_info; - inters_info inters(pi, pj, pk, qi, qj, qk, intersection_strategy, robust_policy); + inters_info inters(range_p, range_q, strategy, robust_policy); char const method = inters.d_info().how; @@ -79,10 +77,9 @@ struct get_turn_info_linear_areal case 'a' : // collinear, "at" case 'f' : // collinear, "from" case 's' : // starts from the middle - get_turn_info_for_endpoint<true, true>( - pi, pj, pk, qi, qj, qk, - is_p_first, is_p_last, is_q_first, is_q_last, - tp_model, inters, method_none, out); + get_turn_info_for_endpoint<true, true>(range_p, range_q, + tp_model, inters, method_none, out, + strategy.get_point_in_point_strategy()); break; case 'd' : // disjoint: never do anything @@ -90,10 +87,9 @@ struct get_turn_info_linear_areal case 'm' : { - if ( get_turn_info_for_endpoint<false, true>( - pi, pj, pk, qi, qj, qk, - is_p_first, is_p_last, is_q_first, is_q_last, - tp_model, inters, method_touch_interior, out) ) + if ( get_turn_info_for_endpoint<false, true>(range_p, range_q, + tp_model, inters, method_touch_interior, out, + strategy.get_point_in_point_strategy()) ) { // do nothing } @@ -107,25 +103,16 @@ struct get_turn_info_linear_areal // If Q (1) arrives (1) if ( inters.d_info().arrival[1] == 1 ) { - policy::template apply<0>(pi, pj, pk, qi, qj, qk, - tp, inters.i_info(), inters.d_info(), + policy::template apply<0>(range_p, range_q, tp, + inters.i_info(), inters.d_info(), inters.sides()); } else { // Swap p/q - side_calculator - < - typename inters_info::cs_tag, - typename inters_info::robust_point2_type, - typename inters_info::robust_point1_type, - typename inters_info::side_strategy_type - > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(), - inters.rpi(), inters.rpj(), inters.rpk(), - inters.get_side_strategy()); - policy::template apply<1>(qi, qj, qk, pi, pj, pk, + policy::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(), - swapped_side_calc); + inters.get_swapped_sides()); } if ( tp.operations[1].operation == operation_blocked ) @@ -139,39 +126,35 @@ struct get_turn_info_linear_areal // this function assumes that 'u' must be set for a spike calculate_spike_operation(tp.operations[0].operation, - inters, is_p_last); + inters, + strategy.get_point_in_point_strategy()); - AssignPolicy::apply(tp, pi, qi, inters); - *out++ = tp; } } break; case 'i' : { - crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, - tp, inters.i_info(), inters.d_info()); + crosses<TurnInfo>::apply(tp, inters.i_info(), inters.d_info()); replace_operations_i(tp.operations[0].operation, tp.operations[1].operation); - AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } break; case 't' : { // Both touch (both arrive there) - if ( get_turn_info_for_endpoint<false, true>( - pi, pj, pk, qi, qj, qk, - is_p_first, is_p_last, is_q_first, is_q_last, - tp_model, inters, method_touch, out) ) + if ( get_turn_info_for_endpoint<false, true>(range_p, range_q, + tp_model, inters, method_touch, out, + strategy.get_point_in_point_strategy()) ) { // do nothing } else { - touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, - tp, inters.i_info(), inters.d_info(), inters.sides()); + touch<TurnInfo>::apply(range_p, range_q, tp, + inters.i_info(), inters.d_info(), inters.sides()); if ( tp.operations[1].operation == operation_blocked ) { @@ -236,15 +219,13 @@ struct get_turn_info_linear_areal bool ignore_spike = calculate_spike_operation(tp.operations[0].operation, - inters, is_p_last); - -// TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters); + inters, + strategy.get_point_in_point_strategy()); if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) || ignore_spike || ! append_opposite_spikes<append_touches>( // for 'i' or 'c' i??? - tp, inters, is_p_last, is_q_last, out) ) + tp, inters, out) ) { *out++ = tp; } @@ -253,10 +234,9 @@ struct get_turn_info_linear_areal break; case 'e': { - if ( get_turn_info_for_endpoint<true, true>( - pi, pj, pk, qi, qj, qk, - is_p_first, is_p_last, is_q_first, is_q_last, - tp_model, inters, method_equal, out) ) + if ( get_turn_info_for_endpoint<true, true>(range_p, range_q, + tp_model, inters, method_equal, out, + strategy.get_point_in_point_strategy()) ) { // do nothing } @@ -268,18 +248,15 @@ struct get_turn_info_linear_areal { // Both equal // or collinear-and-ending at intersection point - equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, - tp, inters.i_info(), inters.d_info(), inters.sides()); + equal<TurnInfo>::apply(range_p, range_q, tp, + inters.i_info(), inters.d_info(), inters.sides()); turn_transformer_ec<false> transformer(method_touch); transformer(tp); - -// TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters); - + // conditionally handle spikes if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) - || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last, + || ! append_collinear_spikes(tp, inters, method_touch, append_equal, out) ) { *out++ = tp; // no spikes @@ -291,7 +268,7 @@ struct get_turn_info_linear_areal < TurnInfo, AssignPolicy - >::apply(pi, qi, + >::apply(range_p, range_q, tp, out, inters); } } @@ -301,9 +278,9 @@ struct get_turn_info_linear_areal { // Collinear if ( get_turn_info_for_endpoint<true, true>( - pi, pj, pk, qi, qj, qk, - is_p_first, is_p_last, is_q_first, is_q_last, - tp_model, inters, method_collinear, out) ) + range_p, range_q, + tp_model, inters, method_collinear, out, + strategy.get_point_in_point_strategy()) ) { // do nothing } @@ -319,16 +296,16 @@ struct get_turn_info_linear_areal if ( inters.d_info().arrival[0] == 0 ) { // Collinear, but similar thus handled as equal - equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, - tp, inters.i_info(), inters.d_info(), inters.sides()); + equal<TurnInfo>::apply(range_p, range_q, tp, + inters.i_info(), inters.d_info(), inters.sides()); method_replace = method_touch; version = append_equal; } else { - collinear<TurnInfo>::apply(pi, pj, pk, qi, qj, qk, - tp, inters.i_info(), inters.d_info(), inters.sides()); + collinear<TurnInfo>::apply(range_p, range_q, tp, + inters.i_info(), inters.d_info(), inters.sides()); //method_replace = method_touch_interior; //version = append_collinear; @@ -337,12 +314,9 @@ struct get_turn_info_linear_areal turn_transformer_ec<false> transformer(method_replace); transformer(tp); -// TODO: move this into the append_xxx and call for each turn? - AssignPolicy::apply(tp, pi, qi, inters); - // conditionally handle spikes if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes) - || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last, + || ! append_collinear_spikes(tp, inters, method_replace, version, out) ) { // no spikes @@ -358,7 +332,7 @@ struct get_turn_info_linear_areal if ( BOOST_GEOMETRY_CONDITION(handle_spikes) ) { append_opposite_spikes<append_collinear_opposite>( - tp, inters, is_p_last, is_q_last, out); + tp, inters, out); } // TODO: ignore for spikes? @@ -369,10 +343,9 @@ struct get_turn_info_linear_areal < TurnInfo, AssignPolicy - >::apply(pi, pj, pk, qi, qj, qk, + >::apply(range_p, range_q, tp, out, inters, - inters.sides(), transformer, - !is_p_last, true); // qk is always valid + inters.sides(), transformer); } } } @@ -384,19 +357,20 @@ struct get_turn_info_linear_areal { only_convert::apply(tp, inters.i_info()); - if ( is_p_first - && equals::equals_point_point(pi, tp.point) ) + if ( range_p.is_first_segment() + && equals::equals_point_point(range_p.at(0), tp.point, + strategy.get_point_in_point_strategy()) ) { tp.operations[0].position = position_front; } - else if ( is_p_last - && equals::equals_point_point(pj, tp.point) ) + else if ( range_p.is_last_segment() + && equals::equals_point_point(range_p.at(1), tp.point, + strategy.get_point_in_point_strategy()) ) { tp.operations[0].position = position_back; } // tp.operations[1].position = position_middle; - AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; } } @@ -417,13 +391,13 @@ struct get_turn_info_linear_areal } template <typename Operation, - typename IntersectionInfo> + typename IntersectionInfo, + typename EqPPStrategy> static inline bool calculate_spike_operation(Operation & op, IntersectionInfo const& inters, - bool is_p_last) + EqPPStrategy const& strategy) { bool is_p_spike = ( op == operation_union || op == operation_intersection ) - && ! is_p_last && inters.is_spike_p(); if ( is_p_spike ) @@ -441,7 +415,7 @@ struct get_turn_info_linear_areal // spike on the edge point // if it's already known that the spike is going out this musn't be checked if ( ! going_out - && equals::equals_point_point(inters.rpj(), inters.rqj()) ) + && detail::equals::equals_point_point(inters.rpj(), inters.rqj(), strategy) ) { int const pk_q2 = inters.sides().pk_wrt_q2(); going_in = pk_q1 < 0 && pk_q2 < 0; // Pk on the right of both @@ -453,7 +427,7 @@ struct get_turn_info_linear_areal // spike on the edge point // if it's already known that the spike is going in this musn't be checked if ( ! going_in - && equals::equals_point_point(inters.rpj(), inters.rqj()) ) + && detail::equals::equals_point_point(inters.rpj(), inters.rqj(), strategy) ) { int const pk_q2 = inters.sides().pk_wrt_q2(); going_in = pk_q1 < 0 || pk_q2 < 0; // Pk on the right of one of them @@ -483,7 +457,6 @@ struct get_turn_info_linear_areal typename OutIt> static inline bool append_collinear_spikes(TurnInfo & tp, IntersectionInfo const& inters, - bool is_p_last, bool /*is_q_last*/, method_type method, append_version_c version, OutIt out) { @@ -494,7 +467,6 @@ struct get_turn_info_linear_areal ( tp.operations[0].operation == operation_union || tp.operations[0].operation == operation_intersection ) : tp.operations[0].operation == operation_continue ) - && ! is_p_last && inters.is_spike_p(); // TODO: throw an exception for spike in Areal? @@ -543,7 +515,6 @@ struct get_turn_info_linear_areal typename OutIt> static inline bool append_opposite_spikes(TurnInfo & tp, IntersectionInfo const& inters, - bool is_p_last, bool /*is_q_last*/, OutIt out) { static const bool is_version_touches = (Version == append_touches); @@ -552,7 +523,6 @@ struct get_turn_info_linear_areal ( tp.operations[0].operation == operation_continue || tp.operations[0].operation == operation_intersection ) : // i ??? true ) - && ! is_p_last && inters.is_spike_p(); // TODO: throw an exception for spike in Areal? @@ -586,8 +556,6 @@ struct get_turn_info_linear_areal BOOST_GEOMETRY_ASSERT(inters.i_info().count > 1); base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1); - - AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters); } tp.operations[0].operation = operation_blocked; @@ -706,35 +674,46 @@ struct get_turn_info_linear_areal template <bool EnableFirst, bool EnableLast, - typename Point1, - typename Point2, + typename UniqueSubRange1, + typename UniqueSubRange2, typename TurnInfo, typename IntersectionInfo, - typename OutputIterator> + typename OutputIterator, + typename EqPPStrategy> static inline bool get_turn_info_for_endpoint( - Point1 const& pi, Point1 const& /*pj*/, Point1 const& /*pk*/, - Point2 const& qi, Point2 const& /*qj*/, Point2 const& /*qk*/, - bool is_p_first, bool is_p_last, - bool /*is_q_first*/, bool is_q_last, + UniqueSubRange1 const& range_p, + UniqueSubRange2 const& range_q, TurnInfo const& tp_model, IntersectionInfo const& inters, method_type /*method*/, - OutputIterator out) + OutputIterator out, + EqPPStrategy const& strategy) { namespace ov = overlay; - typedef ov::get_turn_info_for_endpoint<AssignPolicy, EnableFirst, EnableLast> get_info_e; + typedef ov::get_turn_info_for_endpoint<EnableFirst, EnableLast> get_info_e; const std::size_t ip_count = inters.i_info().count; // no intersection points - if ( ip_count == 0 ) + if (ip_count == 0) + { return false; + } - if ( !is_p_first && !is_p_last ) + if (! range_p.is_first_segment() && ! range_p.is_last_segment()) + { + // P sub-range has no end-points return false; + } -// TODO: is_q_last could probably be replaced by false and removed from parameters + typename IntersectionInfo::side_strategy_type const& sides + = inters.get_side_strategy(); - linear_intersections intersections(pi, qi, inters.result(), is_p_last, is_q_last); + linear_intersections intersections(range_p.at(0), + range_q.at(0), + inters.result(), + range_p.is_last_segment(), + range_q.is_last_segment(), + strategy); linear_intersections::ip_info const& ip0 = intersections.template get<0>(); linear_intersections::ip_info const& ip1 = intersections.template get<1>(); @@ -745,7 +724,7 @@ struct get_turn_info_linear_areal // IP on the first point of Linear Geometry bool was_first_point_handled = false; if ( BOOST_GEOMETRY_CONDITION(EnableFirst) - && is_p_first && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication + && range_p.is_first_segment() && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication { TurnInfo tp = tp_model; tp.operations[0].position = position_front; @@ -759,51 +738,40 @@ struct get_turn_info_linear_areal } else { - typedef typename IntersectionInfo::robust_point1_type rp1_type; - typedef typename IntersectionInfo::robust_point2_type rp2_type; - - method_type replaced_method = method_touch_interior; - + // pi is the intersection point at qj or in the middle of q1 + // so consider segments + // 1. pi at qj: qi-qj-pj and qi-qj-qk + // x: qi-qj, y: qj-qk, qz: qk + // 2. pi in the middle of q1: qi-pi-pj and qi-pi-qj + // x: qi-pi, y: pi-qj, qz: qj + // qi-pi, side the same as WRT q1 + // pi-qj, side the same as WRT q1 + // qj WRT q1 is 0 + method_type replaced_method = method_none; + int side_pj_y = 0, side_pj_x = 0, side_qz_x = 0; + // 1. ip0 or pi at qj if ( ip0.is_qj ) { - side_calculator - < - typename IntersectionInfo::cs_tag, - rp1_type, rp2_type, - typename IntersectionInfo::side_strategy_type, - rp2_type - > side_calc(inters.rqi(), inters.rpi(), inters.rpj(), - inters.rqi(), inters.rqj(), inters.rqk(), - inters.get_side_strategy()); - - std::pair<operation_type, operation_type> - operations = get_info_e::operations_of_equal(side_calc); - - tp.operations[0].operation = operations.first; - tp.operations[1].operation = operations.second; - replaced_method = method_touch; + side_pj_y = sides.apply(range_q.at(1), range_q.at(2), range_p.at(1)); // pj wrt q2 + side_pj_x = sides.apply(range_q.at(0), range_q.at(1), range_p.at(1)); // pj wrt q1 + side_qz_x = sides.apply(range_q.at(0), range_q.at(1), range_q.at(2)); // qk wrt q1 } + // 2. ip0 or pi in the middle of q1 else { - side_calculator - < - typename IntersectionInfo::cs_tag, - rp1_type, rp2_type, - typename IntersectionInfo::side_strategy_type, - rp2_type, rp1_type, rp1_type, - rp2_type, rp1_type, rp2_type - > side_calc(inters.rqi(), inters.rpi(), inters.rpj(), - inters.rqi(), inters.rpi(), inters.rqj(), - inters.get_side_strategy()); - - std::pair<operation_type, operation_type> - operations = get_info_e::operations_of_equal(side_calc); - - tp.operations[0].operation = operations.first; - tp.operations[1].operation = operations.second; + replaced_method = method_touch_interior; + side_pj_y = sides.apply(range_q.at(0), range_q.at(1), range_p.at(1)); // pj wrt q1 + side_pj_x = side_pj_y; // pj wrt q1 + side_qz_x = 0; // qj wrt q1 } + std::pair<operation_type, operation_type> operations + = get_info_e::operations_of_equal(side_pj_y, side_pj_x, side_qz_x); + + tp.operations[0].operation = operations.first; + tp.operations[1].operation = operations.second; + turn_transformer_ec<true> transformer(replaced_method); transformer(tp); } @@ -817,7 +785,6 @@ struct get_turn_info_linear_areal // here is_p_first_ip == true tp.operations[0].is_collinear = false; - AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; was_first_point_handled = true; @@ -827,7 +794,7 @@ struct get_turn_info_linear_areal // IP on the last point of Linear Geometry if ( BOOST_GEOMETRY_CONDITION(EnableLast) - && is_p_last + && range_p.is_last_segment() && ( ip_count > 1 ? (ip1.is_pj && !ip1.is_qi) : (ip0.is_pj && !ip0.is_qi) ) ) // prevents duplication { TurnInfo tp = tp_model; @@ -840,19 +807,33 @@ struct get_turn_info_linear_areal } else //if ( result.template get<0>().count == 1 ) { - side_calculator - < - typename IntersectionInfo::cs_tag, - typename IntersectionInfo::robust_point1_type, - typename IntersectionInfo::robust_point2_type, - typename IntersectionInfo::side_strategy_type, - typename IntersectionInfo::robust_point2_type - > side_calc(inters.rqi(), inters.rpj(), inters.rpi(), - inters.rqi(), inters.rqj(), inters.rqk(), - inters.get_side_strategy()); - - std::pair<operation_type, operation_type> - operations = get_info_e::operations_of_equal(side_calc); + // pj is the intersection point at qj or in the middle of q1 + // so consider segments + // 1. pj at qj: qi-qj-pi and qi-qj-qk + // x: qi-qj, y: qj-qk, qz: qk + // 2. pj in the middle of q1: qi-pj-pi and qi-pj-qj + // x: qi-pj, y: pj-qj, qz: qj + // qi-pj, the side is the same as WRT q1 + // pj-qj, the side is the same as WRT q1 + // side of qj WRT q1 is 0 + int side_pi_y = 0, side_pi_x = 0, side_qz_x = 0; + // 1. ip0 or pj at qj + if ( ip0.is_qj ) + { + side_pi_y = sides.apply(range_q.at(1), range_q.at(2), range_p.at(0)); // pi wrt q2 + side_pi_x = sides.apply(range_q.at(0), range_q.at(1), range_p.at(0)); // pi wrt q1 + side_qz_x = sides.apply(range_q.at(0), range_q.at(1), range_q.at(2)); // qk wrt q1 + } + // 2. ip0 or pj in the middle of q1 + else + { + side_pi_y = sides.apply(range_q.at(0), range_q.at(1), range_p.at(0)); // pi wrt q1 + side_pi_x = side_pi_y; // pi wrt q1 + side_qz_x = 0; // qj wrt q1 + } + + std::pair<operation_type, operation_type> operations + = get_info_e::operations_of_equal(side_pi_y, side_pi_x, side_qz_x); tp.operations[0].operation = operations.first; tp.operations[1].operation = operations.second; @@ -873,7 +854,6 @@ struct get_turn_info_linear_areal unsigned int ip_index = ip_count > 1 ? 1 : 0; base_turn_handler::assign_point(tp, tp.method, inters.i_info(), ip_index); - AssignPolicy::apply(tp, pi, qi, inters); *out++ = tp; // don't ignore the first IP if the segment is opposite @@ -883,6 +863,14 @@ struct get_turn_info_linear_areal // don't ignore anything for now return false; } + + template <typename Point1, typename Point2, typename IntersectionStrategy> + static inline bool equals_point_point(Point1 const& point1, Point2 const& point2, + IntersectionStrategy const& strategy) + { + return detail::equals::equals_point_point(point1, point2, + strategy.get_point_in_point_strategy()); + } }; }} // namespace detail::overlay |