[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.

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:17 UTC