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

Subject: Re: [geometry] R-tree segment query optimization
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2018-04-11 00:34:38

Hi Jeremy,

Jeremy Murphy wrote:
> On Wed, 11 Apr 2018, 2:54 AM Adam Wulkiewicz via Geometry 
> <geometry_at_[hidden] <mailto: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