id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
10890	Problem with collinear point/segment and rtree	jon brookshire <jon.brookshire@…>	Barend Gehrels	"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);
    }
}}}"	Bugs	closed	Boost 1.58.0	geometry	Boost 1.57.0	Problem	fixed