Geometry Boost List: Re: [geometry] R-tree segment query optimization

Subject: Re: [geometry] R-tree segment query optimization
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2018-04-16 14:28:34

Hi Adam,

thanks for the detailed answer. I haven't used Boost.Geometry rtree in a
while, so I'm stuck already.  :\
I created an rtree of 2D Cartesian points, that's fine. But when I tried to
do a query using a nearest(segment, 1) predicate, I get a compilation error
that looks like comparable_distance is not-yet-implemented between SEGMENT
and BOX.

.../boost/mpl/assert.hpp:440:42: error: no matching function for call to
‘assertion_failed(mpl_::failed************
(boost::geometry::nyi::not_implemented_error<boost::geometry::info::SEGMENT,
boost::geometry::info::BOX,
void>::THIS_OPERATION_IS_NOT_OR_NOT_YET_IMPLEMENTED::************)(mpl_::assert_::types<boost::geometry::info::SEGMENT,
boost::geometry::info::BOX, void, mpl_::na>))’

.../boost/geometry/algorithms/detail/comparable_distance/interface.hpp:83:21:
error: ‘apply’ is not a member of
‘boost::geometry::dispatch::distance<boost::geometry::model::referring_segment<boost::geometry::model::point<double,
2ul, boost::geometry::cs::cartesian> >,
boost::geometry::model::box<boost::geometry::model::point<double, 2ul,
boost::geometry::cs::cartesian> >,
boost::geometry::strategy::distance::projected_point<void,
boost::geometry::strategy::distance::comparable::pythagoras<void> >,
boost::geometry::segment_tag, boost::geometry::box_tag,
boost::geometry::strategy_tag_distance_point_segment, false>’

Did I use it incorrectly or is it actually just not yet supported? I'm
using the head of develop.

Thanks, cheers.

Jeremy

On 11 April 2018 at 10:34, Adam Wulkiewicz via Geometry <
geometry_at_[hidden]> wrote:

> Hi Jeremy,
>
> Jeremy Murphy wrote:
>
> On Wed, 11 Apr 2018, 2:54 AM Adam Wulkiewicz via Geometry <
> geometry_at_[hidden]> wrote:
>
>> For your case it'd be bg::intersects() for both nodes (boxes) and values
>> (points) as the first parameter and your segment as the second parameter.
>>
>> I'm not sure what do you mean by "right-hand side of the query segment",
>> the whole "half" of space on the right side of the line defined by segment
>> or a region enclosed by the segment and 2 perpendicular half-lines starting
>> at segment endpoints and going in some direction. Writing the comments
>> below I assumed the latter. If you had the former in mind then sideness
>> test (as performed by side strategy) would be enough.
>>
>
> Yes, I meant the first interpretation, the infinite 'half-space' that is
> not on the left-hand side nor collinear with the query segment, although we
> can ignore collinearity for simplicity.
>
> Btw, using the cartesian side strategy the side of a point wrt line
>> defined by segment can be checked like this:
>>
>> // left of segment (> 0), right of segment (< 0), on segment (0)
>> int side = boost::geometry::strategy::side::side_by_triangle<>::apply(segment_p1,
>> segment_p2, point);
>>
>
> Aha, so that's what I need, but how can I pass that as a predicate to the
> rtree? Also by writing a custom predicate that basically just calls it?
>
> No, you can pass your segment to existing spatial predicate as usual. E.g.
> if you pass bgi::intersects(my_segment) into rtree::query() then internally
> bg::intersects(node_box, my_segment) and bg::intersects(point_value,
> my_segment) is called. So after overloading bg::intersects() the rtree
> should just work automatically. Something like this:
>
> struct segment_side_region
> {
>     typedef bg::model::point<double, 2, bg::cs::cartesian> point_t;
>     enum side_t { right, left };
>
>     segment_side_region(point_t const& p0, point_t const& p1, side_t side)
>         : m_p0(p0), m_p1(p1), m_side(side == right ? 1 : -1)
>     {}
>
>     template <typename Point>
>     bool intersects_point(Point const& p) const
>     {
>         return bg::strategy::side::side_by_triangle
>                 <>::apply(m_p0, m_p1, p) == m_side;
>     }
>
>     template <typename Box>
>     bool intersects_box(Box const& b) const
>     {
>         typename bg::point_type<Box>::type p;
>         bg::set<0>(p, bg::get<min_corner, 0>(b));
>         bg::set<1>(p, bg::get<min_corner, 1>(b));
>         if (intersects(p))
>             return true;
>         bg::set<1>(p, bg::get<max_corner, 1>(b));
>         if (intersects(p))
>             return true;
>         bg::set<0>(p, bg::get<max_corner, 0>(b));
>         if (intersects(p))
>             return true;
>         bg::set<1>(p, bg::get<min_corner, 1>(b));
>         if (intersects(p))
>             return true;
>         return false;
>     }
>
> private:
>     point_t m_p0, m_p1;
>     int m_side;
> };
>
> namespace boost { namespace geometry {
>
> template <typename Point>
> inline bool intersects(Point const& p, segment_side_region const& s)
> {
>     return s.intersects_point(p);
> }
>
> template <typename Box>
> inline bool intersects(Box const& b, segment_side_region const& s)
> {
>     return s.intersects_box(b);
> }
>
> }}
>
> // and then simply
>
> segment_side_region region{p0, p1, segment_side_region::right};
> some_segment_type segment{p0, p1};
> rtree.query(bgi::intersects(region) && bgi::nearest(segment, 5), result);
>
> Adam
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> https://lists.boost.org/mailman/listinfo.cgi/geometry
>
>