Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DE9IM_HPP
Chris@16: #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DE9IM_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <boost/geometry/strategies/intersection_result.hpp>
Chris@16: #include <boost/geometry/util/math.hpp>
Chris@16: #include <boost/geometry/util/select_coordinate_type.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: namespace policies { namespace relate
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: template <typename S1, typename S2>
Chris@16: struct segments_de9im
Chris@16: {
Chris@16:     typedef de9im_segment return_type;
Chris@16:     typedef S1 segment_type1;
Chris@16:     typedef S2 segment_type2;
Chris@16:     typedef typename select_coordinate_type<S1, S2>::type coordinate_type;
Chris@16: 
Chris@16:     static inline return_type rays_intersect(bool on_segment,
Chris@16:                     double ra, double rb,
Chris@16:                     coordinate_type const& dx1, coordinate_type const& dy1,
Chris@16:                     coordinate_type const& dx2, coordinate_type const& dy2,
Chris@16:                     coordinate_type const& wx, coordinate_type const& wy,
Chris@16:                     S1 const& s1, S2 const& s2)
Chris@16:     {
Chris@16:         if(on_segment)
Chris@16:         {
Chris@16:             // 0 <= ra <= 1 and 0 <= rb <= 1
Chris@16:             // Now check if one of them is 0 or 1, these are "touch" cases
Chris@16:             bool a = math::equals(ra, 0.0) || math::equals(ra, 1.0);
Chris@16:             bool b = math::equals(rb, 0.0) || math::equals(rb, 1.0);
Chris@16:             if (a && b)
Chris@16:             {
Chris@16:                 // Touch boundary/boundary: i-i == -1, i-b == -1, b-b == 0
Chris@16:                 // Opposite: if both are equal they touch in opposite direction
Chris@16:                 return de9im_segment(ra,rb,
Chris@16:                         -1, -1, 1,
Chris@16:                         -1,  0, 0,
Chris@16:                          1,  0, 2, false, math::equals(ra,rb));
Chris@16:             }
Chris@16:             else if (a || b)
Chris@16:             {
Chris@16:                 // Touch boundary/interior: i-i == -1, i-b == -1 or 0, b-b == -1
Chris@16:                 int A = a ? 0 : -1;
Chris@16:                 int B = b ? 0 : -1;
Chris@16:                 return de9im_segment(ra,rb,
Chris@16:                         -1,  B, 1,
Chris@16:                          A, -1, 0,
Chris@16:                          1,  0, 2);
Chris@16:             }
Chris@16: 
Chris@16:             // Intersects: i-i == 0, i-b == -1, i-e == 1
Chris@16:             return de9im_segment(ra,rb,
Chris@16:                      0, -1, 1,
Chris@16:                     -1, -1, 0,
Chris@16:                      1,  0, 2);
Chris@16:         }
Chris@16: 
Chris@16:         // Not on segment, disjoint
Chris@16:         return de9im_segment(ra,rb,
Chris@16:                 -1, -1, 1,
Chris@16:                 -1, -1, 0,
Chris@16:                  1,  0, 2);
Chris@16:     }
Chris@16: 
Chris@16:     static inline return_type collinear_touch(coordinate_type const& x,
Chris@16:                 coordinate_type const& y, bool opposite, char)
Chris@16:     {
Chris@16:         return de9im_segment(0,0,
Chris@16:                 -1, -1, 1,
Chris@16:                 -1,  0, 0,
Chris@16:                  1,  0, 2,
Chris@16:                 true, opposite);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename S>
Chris@16:     static inline return_type collinear_interior_boundary_intersect(S const& s,
Chris@16:                 bool a_within_b, bool opposite)
Chris@16:     {
Chris@16:         return a_within_b
Chris@16:             ? de9im_segment(0,0,
Chris@16:                  1, -1, -1,
Chris@16:                  0,  0, -1,
Chris@16:                  1,  0, 2,
Chris@16:                 true, opposite)
Chris@16:             : de9im_segment(0,0,
Chris@16:                  1,  0, 1,
Chris@16:                 -1,  0, 0,
Chris@16:                 -1, -1, 2,
Chris@16:                 true, opposite);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:     static inline return_type collinear_a_in_b(S1 const& s, bool opposite)
Chris@16:     {
Chris@16:         return de9im_segment(0,0,
Chris@16:                 1, -1, -1,
Chris@16:                 0, -1, -1,
Chris@16:                 1,  0,  2,
Chris@16:                 true, opposite);
Chris@16:     }
Chris@16:     static inline return_type collinear_b_in_a(S2 const& s, bool opposite)
Chris@16:     {
Chris@16:         return de9im_segment(0,0,
Chris@16:                  1,  0,  1,
Chris@16:                 -1, -1,  0,
Chris@16:                 -1, -1,  2,
Chris@16:                 true, opposite);
Chris@16:     }
Chris@16: 
Chris@16:     static inline return_type collinear_overlaps(
Chris@16:                     coordinate_type const& x1, coordinate_type const& y1,
Chris@16:                     coordinate_type const& x2, coordinate_type const& y2, bool opposite)
Chris@16:     {
Chris@16:         return de9im_segment(0,0,
Chris@16:                 1,  0, 1,
Chris@16:                 0, -1, 0,
Chris@16:                 1,  0, 2,
Chris@16:                 true, opposite);
Chris@16:     }
Chris@16: 
Chris@16:     static inline return_type segment_equal(S1 const& s, bool opposite)
Chris@16:     {
Chris@16:         return de9im_segment(0,0,
Chris@16:                  1, -1, -1,
Chris@16:                 -1,  0, -1,
Chris@16:                 -1, -1,  2,
Chris@16:                  true, opposite);
Chris@16:     }
Chris@16: 
Chris@16:     static inline return_type degenerate(S1 const& segment, bool a_degenerate)
Chris@16:     {
Chris@16:             return a_degenerate
Chris@16:                 ? de9im_segment(0,0,
Chris@16:                      0, -1, -1,
Chris@16:                     -1, -1, -1,
Chris@16:                      1,  0,  2,
Chris@16:                      false, false, false, true)
Chris@16:                 : de9im_segment(0,0,
Chris@16:                      0, -1,  1,
Chris@16:                     -1, -1,  0,
Chris@16:                     -1, -1,  2,
Chris@16:                      false, false, false, true);
Chris@16:     }
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: }} // namespace policies::relate
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DE9IM_HPP