Boost C++ Libraries: Ticket #10890: Problem with collinear point/segment and rtree https://svn.boost.org/trac10/ticket/10890 <p> When running a point intersection query on an rtree containing segments, collinear segments/points always returns true. </p> <pre class="wiki"> { typedef bg::model::point&lt;float, 2, bg::cs::cartesian&gt; type_point; typedef bg::model::segment&lt;type_point&gt; type_segment; typedef type_segment type_value; typedef std::vector&lt;type_value&gt; type_valuevector; typedef bgi::rtree&lt;type_value, bgi::quadratic&lt;16&gt; &gt; type_rtree; // create a segment: (0,0) --------&gt; (0,1) // then query as : (0,0) --------&gt; (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 &lt;&lt; is.size() &lt;&lt; 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 &lt;&lt; is.size() &lt;&lt; std::endl; //should be 0, is 0. (correct) } </pre><p> 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: </p> <pre class="wiki"> static inline return_type relate_one_degenerate( DegenerateSegment const&amp; degenerate_segment , RobustType d , RobustType s1, RobustType s2 , bool a_degenerate ) { // Calculate the ratios where ds starts in s // a1---------&gt;a2 (2..6) // b1/b2 (4..4) // Ratio: (4-2)/(6-2) if ( !( s1 &lt;= d &amp;&amp; d &lt;= s2 || s2 &lt;= d &amp;&amp; d &lt;= s1 ) ) return Policy::disjoint(); RatioType const ratio(d - s1, s2 - s1); return Policy::one_degenerate(degenerate_segment, ratio, a_degenerate); } </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/10890 Trac 1.4.3 jon brookshire <jon.brookshire@…> Mon, 22 Dec 2014 03:38:28 GMT <link>https://svn.boost.org/trac10/ticket/10890#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/10890#comment:1</guid> <description> <p> Better still: </p> <pre class="wiki"> static inline return_type relate_one_degenerate( DegenerateSegment const&amp; degenerate_segment , RobustType d , RobustType s1, RobustType s2 , bool a_degenerate ) { // Calculate the ratios where ds starts in s // a1---------&gt;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); } </pre> </description> <category>Ticket</category> </item> <item> <dc:creator>awulkiew</dc:creator> <pubDate>Sat, 27 Dec 2014 22:33:56 GMT</pubDate> <title>status, milestone changed; resolution set https://svn.boost.org/trac10/ticket/10890#comment:2 https://svn.boost.org/trac10/ticket/10890#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> <li><strong>milestone</strong> <span class="trac-field-old">To Be Determined</span> → <span class="trac-field-new">Boost 1.58.0</span> </li> </ul> <p> Thanks for the report. </p> <p> This bug is already fixed in develop branch (the same way how you suggested btw), see <a class="ext-link" href="https://github.com/boostorg/geometry/commit/b2683f48f23a9db0a577ca52b6c7edeeb4c8c0a2"><span class="icon">​</span>https://github.com/boostorg/geometry/commit/b2683f48f23a9db0a577ca52b6c7edeeb4c8c0a2</a>. </p> Ticket