diff options
Diffstat (limited to 'boost/geometry/policies/relate/intersection_points.hpp')
| -rw-r--r-- | boost/geometry/policies/relate/intersection_points.hpp | 245 |
1 files changed, 155 insertions, 90 deletions
diff --git a/boost/geometry/policies/relate/intersection_points.hpp b/boost/geometry/policies/relate/intersection_points.hpp index d7d5199051..aa2f697a2a 100644 --- a/boost/geometry/policies/relate/intersection_points.hpp +++ b/boost/geometry/policies/relate/intersection_points.hpp @@ -16,12 +16,12 @@ #include <boost/concept_check.hpp> #include <boost/numeric/conversion/cast.hpp> -#include <boost/geometry/arithmetic/determinant.hpp> +#include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> #include <boost/geometry/core/access.hpp> #include <boost/geometry/strategies/side_info.hpp> #include <boost/geometry/util/select_calculation_type.hpp> #include <boost/geometry/util/select_most_precise.hpp> - +#include <boost/geometry/util/math.hpp> namespace boost { namespace geometry { @@ -30,106 +30,153 @@ namespace policies { namespace relate { -template <typename S1, typename S2, typename ReturnType, typename CalculationType = void> +/*! +\brief Policy calculating the intersection points themselves + */ +template +< + typename ReturnType +> struct segments_intersection_points { typedef ReturnType return_type; - typedef S1 segment_type1; - typedef S2 segment_type2; - - typedef typename select_calculation_type - < - S1, S2, CalculationType - >::type coordinate_type; - - template <typename R> - static inline return_type segments_intersect(side_info const&, - R const& r, - coordinate_type const& dx1, coordinate_type const& dy1, - coordinate_type const& dx2, coordinate_type const& dy2, - S1 const& s1, S2 const& s2) - { - typedef typename geometry::coordinate_type - < - typename return_type::point_type - >::type return_coordinate_type; - - coordinate_type const s1x = get<0, 0>(s1); - coordinate_type const s1y = get<0, 1>(s1); - - return_type result; - result.count = 1; - set<0>(result.intersections[0], - boost::numeric_cast<return_coordinate_type>(R(s1x) + r * R(dx1))); - set<1>(result.intersections[0], - boost::numeric_cast<return_coordinate_type>(R(s1y) + r * R(dy1))); - return result; - } - - static inline return_type collinear_touch(coordinate_type const& x, - coordinate_type const& y, int, int) + template + < + typename Point, + typename Segment, + typename SegmentRatio, + typename T + > + static inline void assign(Point& point, + Segment const& segment, + SegmentRatio const& ratio, + T const& dx, T const& dy) { - return_type result; - result.count = 1; - set<0>(result.intersections[0], x); - set<1>(result.intersections[0], y); - return result; + typedef typename geometry::coordinate_type<Point>::type coordinate_type; + + // Calculate the intersection point based on segment_ratio + // Up to now, division was postponed. Here we divide using numerator/ + // denominator. In case of integer this results in an integer + // division. + BOOST_ASSERT(ratio.denominator() != 0); + set<0>(point, boost::numeric_cast<coordinate_type>( + get<0, 0>(segment) + + ratio.numerator() * dx / ratio.denominator())); + set<1>(point, boost::numeric_cast<coordinate_type>( + get<0, 1>(segment) + + ratio.numerator() * dy / ratio.denominator())); } - template <typename S> - static inline return_type collinear_inside(S const& s, int index1 = 0, int index2 = 1) + + template + < + typename Segment1, + typename Segment2, + typename SegmentIntersectionInfo + > + static inline return_type segments_crosses(side_info const&, + SegmentIntersectionInfo const& sinfo, + Segment1 const& s1, Segment2 const& s2) { return_type result; - result.count = 2; - set<0>(result.intersections[index1], get<0, 0>(s)); - set<1>(result.intersections[index1], get<0, 1>(s)); - set<0>(result.intersections[index2], get<1, 0>(s)); - set<1>(result.intersections[index2], get<1, 1>(s)); - return result; - } + result.count = 1; - template <typename S> - static inline return_type collinear_interior_boundary_intersect(S const& s, bool a_in_b, - int, int, bool opposite) - { - int index1 = opposite && ! a_in_b ? 1 : 0; - return collinear_inside(s, index1, 1 - index1); - } + if (sinfo.robust_ra < sinfo.robust_rb) + { + assign(result.intersections[0], s1, sinfo.robust_ra, + sinfo.dx_a, sinfo.dy_a); + } + else + { + assign(result.intersections[0], s2, sinfo.robust_rb, + sinfo.dx_b, sinfo.dy_b); + } - static inline return_type collinear_a_in_b(S1 const& s, bool) - { - return collinear_inside(s); - } - static inline return_type collinear_b_in_a(S2 const& s, bool opposite) - { - int index1 = opposite ? 1 : 0; - return collinear_inside(s, index1, 1 - index1); - } + result.fractions[0].assign(sinfo); - static inline return_type collinear_overlaps( - coordinate_type const& x1, coordinate_type const& y1, - coordinate_type const& x2, coordinate_type const& y2, - int, int, bool) - { - return_type result; - result.count = 2; - set<0>(result.intersections[0], x1); - set<1>(result.intersections[0], y1); - set<0>(result.intersections[1], x2); - set<1>(result.intersections[1], y2); return result; } - static inline return_type segment_equal(S1 const& s, bool) + template <typename Segment1, typename Segment2, typename Ratio> + static inline return_type segments_collinear( + Segment1 const& a, Segment2 const& b, + Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b, + Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a) { return_type result; - result.count = 2; - // TODO: order of IP's - set<0>(result.intersections[0], get<0, 0>(s)); - set<1>(result.intersections[0], get<0, 1>(s)); - set<0>(result.intersections[1], get<1, 0>(s)); - set<1>(result.intersections[1], get<1, 1>(s)); + int index = 0, count_a = 0, count_b = 0; + Ratio on_a[2]; + + // The conditions "index < 2" are necessary for non-robust handling, + // if index would be 2 this indicate an (currently uncatched) error + + // IMPORTANT: the order of conditions is different as in direction.hpp + if (ra_from_wrt_b.on_segment() + && index < 2) + { + // a1--------->a2 + // b1----->b2 + // + // ra1 (relative to b) is between 0/1: + // -> First point of A is intersection point + detail::assign_point_from_index<0>(a, result.intersections[index]); + result.fractions[index].assign(Ratio::zero(), ra_from_wrt_b); + on_a[index] = Ratio::zero(); + index++; + count_a++; + } + if (rb_from_wrt_a.in_segment() + && index < 2) + { + // We take the first intersection point of B + // a1--------->a2 + // b1----->b2 + // But only if it is not located on A + // a1--------->a2 + // b1----->b2 rb_from_wrt_a == 0/1 -> a already taken + + detail::assign_point_from_index<0>(b, result.intersections[index]); + result.fractions[index].assign(rb_from_wrt_a, Ratio::zero()); + on_a[index] = rb_from_wrt_a; + index++; + count_b++; + } + + if (ra_to_wrt_b.on_segment() + && index < 2) + { + // Similarly, second IP (here a2) + // a1--------->a2 + // b1----->b2 + detail::assign_point_from_index<1>(a, result.intersections[index]); + result.fractions[index].assign(Ratio::one(), ra_to_wrt_b); + on_a[index] = Ratio::one(); + index++; + count_a++; + } + if (rb_to_wrt_a.in_segment() + && index < 2) + { + detail::assign_point_from_index<1>(b, result.intersections[index]); + result.fractions[index].assign(rb_to_wrt_a, Ratio::one()); + on_a[index] = rb_to_wrt_a; + index++; + count_b++; + } + + // TEMPORARY + // If both are from b, and b is reversed w.r.t. a, we swap IP's + // to align them w.r.t. a + // get_turn_info still relies on some order (in some collinear cases) + if (index == 2 && on_a[1] < on_a[0]) + { + std::swap(result.fractions[0], result.fractions[1]); + std::swap(result.intersections[0], result.intersections[1]); + } + + result.count = index; + return result; } @@ -142,17 +189,35 @@ struct segments_intersection_points return return_type(); } - static inline return_type collinear_disjoint() + // Both degenerate + template <typename Segment> + static inline return_type degenerate(Segment const& segment, bool) { - return return_type(); + return_type result; + result.count = 1; + set<0>(result.intersections[0], get<0, 0>(segment)); + set<1>(result.intersections[0], get<0, 1>(segment)); + return result; } - static inline return_type degenerate(S1 const& s, bool) + // One degenerate + template <typename Segment, typename Ratio> + static inline return_type one_degenerate(Segment const& degenerate_segment, + Ratio const& ratio, bool a_degenerate) { return_type result; result.count = 1; - set<0>(result.intersections[0], get<0, 0>(s)); - set<1>(result.intersections[0], get<0, 1>(s)); + set<0>(result.intersections[0], get<0, 0>(degenerate_segment)); + set<1>(result.intersections[0], get<0, 1>(degenerate_segment)); + if (a_degenerate) + { + // IP lies on ratio w.r.t. segment b + result.fractions[0].assign(Ratio::zero(), ratio); + } + else + { + result.fractions[0].assign(ratio, Ratio::zero()); + } return result; } }; |