Boost logo

Geometry :

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;
 Â Â Â  }

 Â Â Â  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 list run by mateusz at