[Boost-bugs] [Boost C++ Libraries] #10890: Problem with collinear point/segment and rtree

Subject: [Boost-bugs] [Boost C++ Libraries] #10890: Problem with collinear point/segment and rtree
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-12-22 03:27:50

#10890: Problem with collinear point/segment and rtree
-----------------------------------------------+---------------------------
 Reporter:  jon brookshire <jon.brookshire@…>  |      Owner:  barendgehrels
     Type:  Bugs                               |     Status:  new
Milestone:  To Be Determined                   |  Component:  geometry
  Version:  Boost 1.57.0                       |   Severity:  Problem
 Keywords:                                     |
-----------------------------------------------+---------------------------
 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);
     }
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10890>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.