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