Segment R-tree with segment queries

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Segment R-tree with segment queries

Boost Geometry mailing list
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.

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. 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?

Thanks, cheers.

Jeremy


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Segment R-tree with segment queries

Boost Geometry mailing list
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

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Loading...