diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/get_turn_info.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/get_turn_info.hpp | 294 |
1 files changed, 248 insertions, 46 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp index 6d92b1bd3c..c6429bc558 100644 --- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp @@ -21,11 +21,12 @@ #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/assert.hpp> +#include <boost/geometry/core/config.hpp> #include <boost/geometry/core/exception.hpp> #include <boost/geometry/algorithms/convert.hpp> +#include <boost/geometry/algorithms/detail/overlay/get_distance_measure.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> -#include <boost/geometry/algorithms/detail/recalculate.hpp> #include <boost/geometry/geometries/segment.hpp> @@ -142,6 +143,72 @@ struct base_turn_handler ctype const dy = get<1>(a) - get<1>(b); return dx * dx + dy * dy; } + + template + < + std::size_t IndexP, + std::size_t IndexQ, + typename UniqueSubRange1, + typename UniqueSubRange2, + typename UmbrellaStrategy, + typename TurnInfo + > + static inline void both_collinear( + UniqueSubRange1 const& range_p, + UniqueSubRange2 const& range_q, + UmbrellaStrategy const&, + std::size_t index_p, std::size_t index_q, + TurnInfo& ti) + { + boost::ignore_unused(range_p, range_q); + BOOST_GEOMETRY_ASSERT(IndexP + IndexQ == 1); + BOOST_GEOMETRY_ASSERT(index_p > 0 && index_p <= 2); + BOOST_GEOMETRY_ASSERT(index_q > 0 && index_q <= 2); + +#if ! defined(BOOST_GEOMETRY_USE_RESCALING) + ti.operations[IndexP].remaining_distance = distance_measure(ti.point, range_p.at(index_p)); + ti.operations[IndexQ].remaining_distance = distance_measure(ti.point, range_q.at(index_q)); + + // pk/q2 is considered as collinear, but there might be + // a tiny measurable difference. If so, use that. + // Calculate pk // qj-qk + typedef detail::distance_measure + < + typename select_coordinate_type + < + typename UniqueSubRange1::point_type, + typename UniqueSubRange2::point_type + >::type + > dm_type; + + const bool p_closer = + ti.operations[IndexP].remaining_distance + < ti.operations[IndexQ].remaining_distance; + dm_type const dm + = p_closer + ? get_distance_measure<typename UmbrellaStrategy::cs_tag>(range_q.at(index_q - 1), + range_q.at(index_q), range_p.at(index_p)) + : get_distance_measure<typename UmbrellaStrategy::cs_tag>(range_p.at(index_p - 1), + range_p.at(index_p), range_q.at(index_q)); + + if (! dm.is_zero()) + { + // Not truely collinear, distinguish for union/intersection + // If p goes left (positive), take that for a union + + bool p_left = p_closer ? dm.is_positive() : dm.is_negative(); + + ti.operations[IndexP].operation = p_left + ? operation_union : operation_intersection; + ti.operations[IndexQ].operation = p_left + ? operation_intersection : operation_union; + return; + } +#endif + + both(ti, operation_continue); + } + }; @@ -159,14 +226,16 @@ struct touch_interior : public base_turn_handler typename UniqueSubRange2, typename IntersectionInfo, typename DirInfo, - typename SidePolicy + typename SidePolicy, + typename UmbrellaStrategy > static inline void apply(UniqueSubRange1 const& range_p, UniqueSubRange2 const& range_q, TurnInfo& ti, IntersectionInfo const& intersection_info, DirInfo const& dir_info, - SidePolicy const& side) + SidePolicy const& side, + UmbrellaStrategy const& umbrella_strategy) { assign_point(ti, method_touch_interior, intersection_info, 0); @@ -266,19 +335,8 @@ struct touch_interior : public base_turn_handler // Q intersects on interior of P and continues collinearly if (side_qk_q == side_qi_p) { - // Collinearly in the same direction - // (Q comes from left of P and turns left, - // OR Q comes from right of P and turns right) - // Omit second intersection point. - // Union: just continue - // Intersection: just continue - both(ti, operation_continue); - - // Calculate remaining distance. - // Q arrives at p, at point qj, so use qk for q - // and use pj for p - ti.operations[index_p].remaining_distance = distance_measure(ti.point, range_p.at(1)); - ti.operations[index_q].remaining_distance = distance_measure(ti.point, range_q.at(2)); + both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy, 1, 2, ti); + return; } else { @@ -326,14 +384,16 @@ struct touch : public base_turn_handler typename UniqueSubRange2, typename IntersectionInfo, typename DirInfo, - typename SidePolicy + typename SideCalculator, + typename UmbrellaStrategy > static inline void apply(UniqueSubRange1 const& range_p, UniqueSubRange2 const& range_q, TurnInfo& ti, IntersectionInfo const& intersection_info, DirInfo const& dir_info, - SidePolicy const& side) + SideCalculator const& side, + UmbrellaStrategy const& umbrella_strategy) { assign_point(ti, method_touch, intersection_info, 0); @@ -369,13 +429,12 @@ struct touch : public base_turn_handler // (#BRL2) if (side_pk_q2 == 0 && ! block_q) { - both(ti, operation_continue); + both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti); return; } int const side_pk_q1 = has_pk && has_qk ? side.pk_wrt_q1() : 0; - // Collinear opposite case -> block P // (#BRL4, #BLR8) if (side_pk_q1 == 0) @@ -513,14 +572,16 @@ struct equal : public base_turn_handler typename UniqueSubRange2, typename IntersectionInfo, typename DirInfo, - typename SidePolicy + typename SideCalculator, + typename UmbrellaStrategy > static inline void apply(UniqueSubRange1 const& range_p, UniqueSubRange2 const& range_q, TurnInfo& ti, IntersectionInfo const& info, DirInfo const& , - SidePolicy const& side) + SideCalculator const& side, + UmbrellaStrategy const& umbrella_strategy) { // Copy the intersection point in TO direction assign_point(ti, method_equal, info, non_opposite_to_index(info)); @@ -538,8 +599,7 @@ struct equal : public base_turn_handler // oppositely if (side_pk_q2 == 0 && side_pk_p == side_qk_p) { - both(ti, operation_continue); - + both_collinear<0, 1>(range_p, range_q, umbrella_strategy, 2, 2, ti); return; } @@ -562,6 +622,132 @@ struct equal : public base_turn_handler template < + typename TurnInfo +> +struct start : public base_turn_handler +{ + template + < + typename UniqueSubRange1, + typename UniqueSubRange2, + typename IntersectionInfo, + typename DirInfo, + typename SideCalculator, + typename UmbrellaStrategy + > + static inline bool apply(UniqueSubRange1 const& range_p, + UniqueSubRange2 const& range_q, + TurnInfo& ti, + IntersectionInfo const& info, + DirInfo const& dir_info, + SideCalculator const& side, + UmbrellaStrategy const& ) + { + // For now disabled. TODO: remove all code or fix inconsistencies + // within validity and relations + return false; + + if (dir_info.opposite) + { + // They should not be collinear + return false; + } + + int const side_pj_q1 = side.pj_wrt_q1(); + int const side_qj_p1 = side.qj_wrt_p1(); + + // Get side values at starting point + typedef detail::distance_measure + < + typename select_coordinate_type + < + typename UniqueSubRange1::point_type, + typename UniqueSubRange2::point_type + >::type + > dm_type; + + typedef typename UmbrellaStrategy::cs_tag cs_tag; + dm_type const dm_pi_q1 = get_distance_measure<cs_tag>(range_q.at(0), range_q.at(1), range_p.at(0)); + dm_type const dm_qi_p1 = get_distance_measure<cs_tag>(range_p.at(0), range_p.at(1), range_q.at(0)); + + if (dir_info.how_a == -1 && dir_info.how_b == -1) + { + // Both p and q leave + if (dm_pi_q1.is_zero() && dm_qi_p1.is_zero()) + { + // Exactly collinear, not necessary to handle it + return false; + } + + if (! (dm_pi_q1.is_small() && dm_qi_p1.is_small())) + { + // Not nearly collinear + return false; + } + + if (side_qj_p1 == 0) + { + // Collinear is not handled + return false; + } + + ui_else_iu(side_qj_p1 == -1, ti); + } + else if (dir_info.how_b == -1) + { + // p ---------------> + // | + // | q q leaves + // v + // + + if (dm_qi_p1.is_zero() || ! dm_qi_p1.is_small()) + { + // Exactly collinear + return false; + } + + if (side_qj_p1 == 0) + { + // Collinear is not handled + return false; + } + + ui_else_iu(side_qj_p1 == -1, ti); + } + else if (dir_info.how_a == -1) + { + if (dm_pi_q1.is_zero() || ! dm_pi_q1.is_small()) + { + // It starts exactly, not necessary to handle it + return false; + } + + // p leaves + if (side_pj_q1 == 0) + { + // Collinear is not handled + return false; + } + + ui_else_iu(side_pj_q1 == 1, ti); + } + else + { + // Not supported + return false; + } + + // Copy intersection point + assign_point(ti, method_start, info, 0); + return true; + } + +}; + + +template +< typename TurnInfo, typename AssignPolicy > @@ -950,7 +1136,7 @@ struct get_turn_info typename UniqueSubRange1, typename UniqueSubRange2, typename TurnInfo, - typename IntersectionStrategy, + typename UmbrellaStrategy, typename RobustPolicy, typename OutputIterator > @@ -958,7 +1144,7 @@ struct get_turn_info UniqueSubRange1 const& range_p, UniqueSubRange2 const& range_q, TurnInfo const& tp_model, - IntersectionStrategy const& intersection_strategy, + UmbrellaStrategy const& umbrella_strategy, RobustPolicy const& robust_policy, OutputIterator out) { @@ -966,30 +1152,24 @@ struct get_turn_info < UniqueSubRange1, UniqueSubRange2, typename TurnInfo::point_type, - IntersectionStrategy, + UmbrellaStrategy, RobustPolicy > inters_info; - inters_info inters(range_p, range_q, - intersection_strategy, robust_policy); + inters_info inters(range_p, range_q, umbrella_strategy, robust_policy); char const method = inters.d_info().how; // Copy, to copy possibly extended fields TurnInfo tp = tp_model; + bool do_only_convert = false; + // Select method and apply switch(method) { - case 'a' : // collinear, "at" - case 'f' : // collinear, "from" - case 's' : // starts from the middle - if (AssignPolicy::include_no_turn - && inters.i_info().count > 0) - { - only_convert::apply(tp, inters.i_info()); - *out++ = tp; - } + case 'a' : // "angle" + do_only_convert = true; break; case 'd' : // disjoint: never do anything @@ -1000,19 +1180,19 @@ struct get_turn_info typedef touch_interior < TurnInfo - > policy; + > handler; // If Q (1) arrives (1) if ( inters.d_info().arrival[1] == 1 ) { - policy::template apply<0>(range_p, range_q, tp, inters.i_info(), inters.d_info(), - inters.sides()); + handler::template apply<0>(range_p, range_q, tp, inters.i_info(), inters.d_info(), + inters.sides(), umbrella_strategy); } else { // Swap p/q - policy::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(), - inters.get_swapped_sides()); + handler::template apply<1>(range_q, range_p, tp, inters.i_info(), inters.d_info(), + inters.get_swapped_sides(), umbrella_strategy); } *out++ = tp; } @@ -1026,17 +1206,31 @@ struct get_turn_info case 't' : { // Both touch (both arrive there) - touch<TurnInfo>::apply(range_p, range_q, 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(), umbrella_strategy); *out++ = tp; } break; + case 'f' : + case 's' : + { + // "from" or "start" without rescaling, it is in some cases necessary to handle + if (start<TurnInfo>::apply(range_p, range_q, tp, inters.i_info(), inters.d_info(), inters.sides(), umbrella_strategy)) + { + *out++ = tp; + } + else + { + do_only_convert = true; + } + } + break; case 'e': { if ( ! inters.d_info().opposite ) { // Both equal // or collinear-and-ending at intersection point - equal<TurnInfo>::apply(range_p, range_q, 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(), umbrella_strategy); *out++ = tp; } else @@ -1059,7 +1253,7 @@ struct get_turn_info { // Collinear, but similar thus handled as equal equal<TurnInfo>::apply(range_p, range_q, tp, - inters.i_info(), inters.d_info(), inters.sides()); + inters.i_info(), inters.d_info(), inters.sides(), umbrella_strategy); // override assigned method tp.method = method_collinear; @@ -1105,6 +1299,14 @@ struct get_turn_info break; } + if (do_only_convert + && AssignPolicy::include_no_turn + && inters.i_info().count > 0) + { + only_convert::apply(tp, inters.i_info()); + *out++ = tp; + } + return out; } }; |