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.


On 11 April 2018 at 10:34, Adam Wulkiewicz via Geometry <geometry@lists.boost.org> wrote:
Hi Jeremy,

Jeremy Murphy wrote:
On Wed, 11 Apr 2018, 2:54 AM Adam Wulkiewicz via Geometry <geometry@lists.boost.org> 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;

    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);


Geometry mailing list