diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp | 199 |
1 files changed, 90 insertions, 109 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp index f9b4dee2cd..521744df88 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp @@ -2,8 +2,8 @@ // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// This file was modified by Oracle on 2013, 2014, 2017. -// Modifications copyright (c) 2013-2017 Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2017, 2018. +// Modifications copyright (c) 2013-2018 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle @@ -15,8 +15,10 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP #include <boost/core/ignore_unused.hpp> -#include <boost/geometry/core/assert.hpp> + +#include <boost/geometry/algorithms/detail/equals/point_point.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> +#include <boost/geometry/core/assert.hpp> #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> namespace boost { namespace geometry { @@ -109,11 +111,12 @@ namespace detail { namespace overlay { class linear_intersections { public: - template <typename Point1, typename Point2, typename IntersectionResult> + template <typename Point1, typename Point2, typename IntersectionResult, typename EqPPStrategy> linear_intersections(Point1 const& pi, Point2 const& qi, IntersectionResult const& result, - bool is_p_last, bool is_q_last) + bool is_p_last, bool is_q_last, + EqPPStrategy const& strategy) { int arrival_a = result.template get<1>().arrival[0]; int arrival_b = result.template get<1>().arrival[1]; @@ -133,10 +136,10 @@ public: ips[0].is_pi = equals::equals_point_point( - pi, result.template get<0>().intersections[0]); + pi, result.template get<0>().intersections[0], strategy); ips[0].is_qi = equals::equals_point_point( - qi, result.template get<0>().intersections[0]); + qi, result.template get<0>().intersections[0], strategy); ips[1].is_pj = arrival_a != -1; ips[1].is_qj = arrival_b != -1; } @@ -222,39 +225,53 @@ private: ip_info ips[2]; }; -template <typename AssignPolicy, bool EnableFirst, bool EnableLast> +template <bool EnableFirst, bool EnableLast> struct get_turn_info_for_endpoint { + typedef std::pair<operation_type, operation_type> operations_pair; + BOOST_STATIC_ASSERT(EnableFirst || EnableLast); - template<typename Point1, - typename Point2, + template<typename UniqueSubRange1, + typename UniqueSubRange2, typename TurnInfo, typename IntersectionInfo, - typename OutputIterator + typename OutputIterator, + typename EqPPStrategy > - static inline bool 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, + static inline bool apply(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) { 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 && !is_q_first && !is_q_last ) + if (! range_p.is_first_segment() + && ! range_q.is_first_segment() + && ! range_p.is_last_segment() + && ! range_q.is_last_segment()) + { + // Not an end-point from segment p or q return false; + } - 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); bool append0_last - = analyse_segment_and_assign_ip(pi, pj, pk, qi, qj, qk, - is_p_first, is_p_last, is_q_first, is_q_last, + = analyse_segment_and_assign_ip(range_p, range_q, intersections.template get<0>(), tp_model, inters, 0, out); @@ -268,8 +285,7 @@ struct get_turn_info_for_endpoint return result_ignore_ip0; bool append1_last - = analyse_segment_and_assign_ip(pi, pj, pk, qi, qj, qk, - is_p_first, is_p_last, is_q_first, is_q_last, + = analyse_segment_and_assign_ip(range_p, range_q, intersections.template get<1>(), tp_model, inters, 1, out); @@ -279,37 +295,25 @@ struct get_turn_info_for_endpoint return result_ignore_ip0 || result_ignore_ip1; } - template <typename Point1, - typename Point2, + template <typename UniqueSubRange1, + typename UniqueSubRange2, typename TurnInfo, typename IntersectionInfo, typename OutputIterator> static inline - bool analyse_segment_and_assign_ip(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, + bool analyse_segment_and_assign_ip(UniqueSubRange1 const& range_p, + UniqueSubRange2 const& range_q, linear_intersections::ip_info const& ip_info, TurnInfo const& tp_model, IntersectionInfo const& inters, unsigned int ip_index, OutputIterator out) { -#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS_LINEAR_LINEAR - // may this give false positives for INTs? - typename IntersectionResult::point_type const& - inters_pt = result.template get<0>().intersections[ip_index]; - BOOST_GEOMETRY_ASSERT(ip_info.is_pi == equals::equals_point_point(pi, inters_pt)); - BOOST_GEOMETRY_ASSERT(ip_info.is_qi == equals::equals_point_point(qi, inters_pt)); - BOOST_GEOMETRY_ASSERT(ip_info.is_pj == equals::equals_point_point(pj, inters_pt)); - BOOST_GEOMETRY_ASSERT(ip_info.is_qj == equals::equals_point_point(qj, inters_pt)); -#endif - // TODO - calculate first/last only if needed - bool is_p_first_ip = is_p_first && ip_info.is_pi; - bool is_p_last_ip = is_p_last && ip_info.is_pj; - bool is_q_first_ip = is_q_first && ip_info.is_qi; - bool is_q_last_ip = is_q_last && ip_info.is_qj; + bool is_p_first_ip = range_p.is_first_segment() && ip_info.is_pi; + bool is_p_last_ip = range_p.is_last_segment() && ip_info.is_pj; + bool is_q_first_ip = range_q.is_first_segment() && ip_info.is_qi; + bool is_q_last_ip = range_q.is_last_segment() && ip_info.is_qj; bool append_first = EnableFirst && (is_p_first_ip || is_q_first_ip); bool append_last = EnableLast && (is_p_last_ip || is_q_last_ip); @@ -318,9 +322,7 @@ struct get_turn_info_for_endpoint if ( append_first || append_last ) { - bool handled = handle_internal<0>(pi, pj, pk, qi, qj, qk, - inters.rpi(), inters.rpj(), inters.rpk(), - inters.rqi(), inters.rqj(), inters.rqk(), + bool handled = handle_internal<0>(range_p, range_q, is_p_first_ip, is_p_last_ip, is_q_first_ip, is_q_last_ip, ip_info.is_qi, ip_info.is_qj, @@ -328,9 +330,8 @@ struct get_turn_info_for_endpoint p_operation, q_operation); if ( !handled ) { - handle_internal<1>(qi, qj, qk, pi, pj, pk, - inters.rqi(), inters.rqj(), inters.rqk(), - inters.rpi(), inters.rpj(), inters.rpk(), + // Reverse p/q + handle_internal<1>(range_q, range_p, is_q_first_ip, is_q_last_ip, is_p_first_ip, is_p_last_ip, ip_info.is_pi, ip_info.is_pj, @@ -348,31 +349,29 @@ struct get_turn_info_for_endpoint // handle spikes // P is spike and should be handled - if ( !is_p_last - && ip_info.is_pj // this check is redundant (also in is_spike_p) but faster + if (ip_info.is_pj // this check is redundant (also in is_spike_p) but faster && inters.i_info().count == 2 && inters.is_spike_p() ) { - assign(pi, qi, inters.result(), ip_index, method, operation_blocked, q_operation, + assign(inters.result(), ip_index, method, operation_blocked, q_operation, p_pos, q_pos, is_p_first_ip, is_q_first_ip, true, false, tp_model, out); - assign(pi, qi, inters.result(), ip_index, method, operation_intersection, q_operation, + assign(inters.result(), ip_index, method, operation_intersection, q_operation, p_pos, q_pos, is_p_first_ip, is_q_first_ip, true, false, tp_model, out); } // Q is spike and should be handled - else if ( !is_q_last - && ip_info.is_qj // this check is redundant (also in is_spike_q) but faster + else if (ip_info.is_qj // this check is redundant (also in is_spike_q) but faster && inters.i_info().count == 2 && inters.is_spike_q() ) { - assign(pi, qi, inters.result(), ip_index, method, p_operation, operation_blocked, + assign(inters.result(), ip_index, method, p_operation, operation_blocked, p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, true, tp_model, out); - assign(pi, qi, inters.result(), ip_index, method, p_operation, operation_intersection, + assign(inters.result(), ip_index, method, p_operation, operation_intersection, p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, true, tp_model, out); } // no spikes else { - assign(pi, qi, inters.result(), ip_index, method, p_operation, q_operation, + assign(inters.result(), ip_index, method, p_operation, q_operation, p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, false, tp_model, out); } } @@ -385,25 +384,22 @@ struct get_turn_info_for_endpoint // however now it's lazily calculated and then it would be always calculated template<std::size_t G1Index, - typename Point1, - typename Point2, - typename RobustPoint1, - typename RobustPoint2, + typename UniqueRange1, + typename UniqueRange2, typename TurnInfo, typename IntersectionInfo > - static inline bool handle_internal(Point1 const& /*i1*/, Point1 const& /*j1*/, Point1 const& /*k1*/, - Point2 const& i2, Point2 const& j2, Point2 const& /*k2*/, - RobustPoint1 const& ri1, RobustPoint1 const& rj1, RobustPoint1 const& /*rk1*/, - RobustPoint2 const& ri2, RobustPoint2 const& rj2, RobustPoint2 const& rk2, + static inline bool handle_internal(UniqueRange1 const& range1, + UniqueRange2 const& range2, bool first1, bool last1, bool first2, bool last2, bool ip_i2, bool ip_j2, TurnInfo const& tp_model, IntersectionInfo const& inters, unsigned int ip_index, operation_type & op1, operation_type & op2) { - typedef typename cs_tag<typename TurnInfo::point_type>::type cs_tag; + boost::ignore_unused(ip_index, tp_model); - boost::ignore_unused(i2, j2, ip_index, tp_model); + typename IntersectionInfo::side_strategy_type const& sides + = inters.get_side_strategy(); if ( !first2 && !last2 ) { @@ -425,14 +421,11 @@ struct get_turn_info_for_endpoint } else if ( ip_j2 ) { - side_calculator<cs_tag, - RobustPoint1, RobustPoint2, - typename IntersectionInfo::side_strategy_type, - RobustPoint2> - side_calc(ri2, ri1, rj1, ri2, rj2, rk2, inters.get_side_strategy()); + int const side_pj_q2 = sides.apply(range2.at(1), range2.at(2), range1.at(1)); + int const side_pj_q1 = sides.apply(range2.at(0), range2.at(1), range1.at(1)); + int const side_qk_q1 = sides.apply(range2.at(0), range2.at(1), range2.at(2)); - std::pair<operation_type, operation_type> - operations = operations_of_equal(side_calc); + operations_pair operations = operations_of_equal(side_pj_q2, side_pj_q1, side_qk_q1); // TODO: must the above be calculated? // wouldn't it be enough to check if segments are collinear? @@ -479,13 +472,11 @@ struct get_turn_info_for_endpoint } else if ( ip_j2 ) { - side_calculator<cs_tag, RobustPoint1, RobustPoint2, - typename IntersectionInfo::side_strategy_type, - RobustPoint2> - side_calc(ri2, rj1, ri1, ri2, rj2, rk2, inters.get_side_strategy()); - - std::pair<operation_type, operation_type> - operations = operations_of_equal(side_calc); + int const side_pi_q2 = sides.apply(range2.at(1), range2.at(2), range1.at(0)); + int const side_pi_q1 = sides.apply(range2.at(0), range2.at(1), range1.at(0)); + int const side_qk_q1 = sides.apply(range2.at(0), range2.at(1), range2.at(2)); + + operations_pair operations = operations_of_equal(side_pi_q2, side_pi_q1, side_qk_q1); // TODO: must the above be calculated? // wouldn't it be enough to check if segments are collinear? @@ -534,13 +525,10 @@ struct get_turn_info_for_endpoint ( is_ip_last_j ? position_back : position_middle ); } - template <typename Point1, - typename Point2, - typename IntersectionResult, + template <typename IntersectionResult, typename TurnInfo, typename OutputIterator> - static inline void assign(Point1 const& pi, Point2 const& qi, - IntersectionResult const& result, + static inline void assign(IntersectionResult const& result, unsigned int ip_index, method_type method, operation_type op0, operation_type op1, @@ -591,33 +579,27 @@ struct get_turn_info_for_endpoint } } - // TODO: this should get an intersection_info, which is unavailable here - // Because the assign_null policy accepts any structure, we pass the result instead for now - AssignPolicy::apply(tp, pi, qi, result); *out++ = tp; } - template <typename SidePolicy> - static inline std::pair<operation_type, operation_type> operations_of_equal(SidePolicy const& side) + static inline operations_pair operations_of_equal(int side_px_q2, + int side_px_q1, + int side_qk_q1) { - int const side_pk_q2 = side.pk_wrt_q2(); - int const side_pk_p = side.pk_wrt_p1(); - int const side_qk_p = side.qk_wrt_p1(); - - // If pk is collinear with qj-qk, they continue collinearly. - // This can be on either side of p1 (== q1), or collinear + // If px (pi or pj) is collinear with qj-qk (q2), they continue collinearly. + // This can be on either side of q1, or collinear // The second condition checks if they do not continue // oppositely - if ( side_pk_q2 == 0 && side_pk_p == side_qk_p ) + if (side_px_q2 == 0 && side_px_q1 == side_qk_q1) { return std::make_pair(operation_continue, operation_continue); } // If they turn to same side (not opposite sides) - if ( ! base_turn_handler::opposite(side_pk_p, side_qk_p) ) + if ( ! base_turn_handler::opposite(side_px_q1, side_qk_q1) ) { - // If pk is left of q2 or collinear: p: union, q: intersection - if ( side_pk_q2 != -1 ) + // If px is left of q2 or collinear: p: union, q: intersection + if (side_px_q2 != -1 ) { return std::make_pair(operation_union, operation_intersection); } @@ -630,7 +612,7 @@ struct get_turn_info_for_endpoint { // They turn opposite sides. If p turns left (or collinear), // p: union, q: intersection - if ( side_pk_p != -1 ) + if (side_px_q1 != -1 ) { return std::make_pair(operation_union, operation_intersection); } @@ -641,16 +623,15 @@ struct get_turn_info_for_endpoint } } - static inline bool operations_both( - std::pair<operation_type, operation_type> const& operations, - operation_type const op) + static inline bool operations_both(operations_pair const& operations, + operation_type const op) { return operations.first == op && operations.second == op; } - static inline bool operations_combination( - std::pair<operation_type, operation_type> const& operations, - operation_type const op1, operation_type const op2) + static inline bool operations_combination(operations_pair const& operations, + operation_type const op1, + operation_type const op2) { return ( operations.first == op1 && operations.second == op2 ) || ( operations.first == op2 && operations.second == op1 ); |