Geometry Boost List: Re: [geometry] Segment R-tree with segment queries

Subject: Re: [geometry] Segment R-tree with segment queries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2017-04-14 17:14:09

Hi Jeremy,

Jeremy Murphy Via Geometry wrote:
> Hi,
>
> I was just wondering about the current state of rtree of line 
> segments. That is, what queries does it support? Is the list of 
> predicates on the queries page complete or just a sample? There 
> doesn't seem to be any segment-segment predicates listed, just the 
> nearest query.
>

No, it's not complete, more combinations is supported. rtree predicates 
internally call Boost.Geometry predicates. E.g. for rtree storing segments:

bgi::rtree<segment_t, bgi::rstar<4> > rt;

during intersects spatial query:

rt.query(bgi::intersects(segment), std::back_inserter(result));

internally the following functions are called:

bg::intersects(node_box, segment)
bg::intersects(value_segment, segment)

So rtree query works if corresponsing algorithms are  implemented for 
pairs of geometries. Similar with nearest predicate which calls 
bg::comparable_distance().

> I tried to search with index::intersects() to find segments that 
> intersect with another segment and was just surprised to find that it 
> is not implemented.

My guess is that you tried to do this in 3D but bg::intersects(seg, seg) 
is implemented only for 2D, correct?

> Is the most efficient way to achieve this behaviour at the moment to 
> query with the bounding box of the segment and then check the results 
> for actual intersection with the segment?

Assuming you're testing 3D segments you'll be forced to implement your 
own version of intersects(seg, seg) anyway. So either store boxes with 
some segment IDs and then check corresponding segments with your 
implementation of intersection check or overload bg::intersects(seg, 
seg) for your segments and store segments directly in the R-tree.

Version storing boxes could look like this (in C++14):

std::vector<segment_t> input;

// value_type is a pair of segment's envelope and index in the above vector
bgi::rtree<std::pair<box_t, size_t>, bgi::rstar<4> > rt;
// fill the rtree here or pass (possibly transformed) range into the 
ctor above

std::vector<segment_t> result;
rt.query(bgi::intersects(segment_box),
          boost::make_function_output_iterator([&](auto const& value) {
              if (segments_intersect(input[value.second], segment))
result.push_back(input[value.second]);
          }));

Regards,
Adam