Problem with collinear point/segment and rtree

[jon brookshire <jon.brookshire@…>]

When running a point intersection query on an rtree containing segments, collinear segments/points always returns true.

   {
      typedef bg::model::point<float, 2, bg::cs::cartesian> type_point;
      typedef bg::model::segment<type_point> type_segment;
      typedef type_segment type_value;
      typedef std::vector<type_value> type_valuevector;
      typedef bgi::rtree<type_value, bgi::quadratic<16> > type_rtree;

      // create a segment: (0,0) --------> (0,1)
      //  then query as  : (0,0) --------> (0,1)   *(0,2)  (incorrect result: intersection)
      //  and            :                         *(1,2)  (correct result: no intersection)

      type_valuevector values;
      values.push_back(type_segment(type_point(0,0), type_point(0,1)));
      type_rtree rt(values.begin(), values.end());

      type_valuevector is;
      rt.query(bgi::intersects(type_point(0,2)), std::back_inserter(is));

      std::cout << is.size() << std::endl; //should be 0, instead is 1 (incorrect)

      is.clear();
      rt.query(bgi::intersects(type_point(1,2)), std::back_inserter(is));

      std::cout << is.size() << std::endl; //should be 0, is 0. (correct)
    }

Issue may be in cart_intersect.hpp, relate_one_degenerate. There seems to be no check on the ratio. One fix may be to do:

   static inline return_type relate_one_degenerate(
            DegenerateSegment const& degenerate_segment
            , RobustType d
            , RobustType s1, RobustType s2
            , bool a_degenerate
            )
    {
        // Calculate the ratios where ds starts in s
        //         a1--------->a2         (2..6)
        //              b1/b2      (4..4)
        // Ratio: (4-2)/(6-2)
      if ( !( s1 <= d && d <= s2 || s2 <= d && d <= s1 ) )
	return Policy::disjoint();

        RatioType const ratio(d - s1, s2 - s1);
        return Policy::one_degenerate(degenerate_segment, ratio, a_degenerate);
    }

[jon brookshire <jon.brookshire@…>]

Better still:

 static inline return_type relate_one_degenerate(
            DegenerateSegment const& degenerate_segment
            , RobustType d
            , RobustType s1, RobustType s2
            , bool a_degenerate
            )
    {
        // Calculate the ratios where ds starts in s
        //         a1--------->a2         (2..6)
        //              b1/b2      (4..4)
        // Ratio: (4-2)/(6-2)

        RatioType const ratio(d - s1, s2 - s1);

	if ( !ratio.on_segment() )
	  return Policy::disjoint();

        return Policy::one_degenerate(degenerate_segment, ratio, a_degenerate);
    }

[awulkiew]

Thanks for the report.

This bug is already fixed in develop branch (the same way how you suggested btw), see ​https://github.com/boostorg/geometry/commit/b2683f48f23a9db0a577ca52b6c7edeeb4c8c0a2.