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-23 19:55:21

Jeremy Murphy Via Geometry wrote:
> Hi Adam,
>
>
> On 11 April 2018 at 10:34, Adam Wulkiewicz via Geometry 
> <geometry_at_[hidden] <mailto:geometry_at_[hidden]>> wrote:
>
>     Hi Jeremy,
>
>     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:
>
>
> I ended up implementing a hemisphere geometry, because I realized that 
> I only need to search in that finite area.
>
>
>     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);
>     }
>
>     }}
>
>
> So I implemented these, but then using them with the rtree is not 
> 'simply' working.  :)
>
>
>     // 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);
>
>
> Â At this point the hemisphere geometry fails a concept check on this 
> line from intersects():
>
>
> .../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::hemisphere_tag, 
> void, 
> void>::THIS_OPERATION_IS_NOT_OR_NOT_YET_IMPLEMENTED::************)(mpl_::assert_::types<boost::geometry::hemisphere_tag, 
> void, void, mpl_::na>))’
>

If that's the case then this means that your overloads of 
bg::intersects() are not used by the compiler.

Adding new kinds of geometries and implementing algorithms for them is 
more complex than writing an overload. If you want to go this way I 
could guide you but in general this shouldn't be needed.

With some compilers the order of includes WRT the overloads may be the 
problem. E.g. try to implement the overloads before the library is 
included or instead of writing a function template (with typename Box) 
write a function taking a specific box type. The R-tree uses 
bg::model::box<bg::model::point<CoordinateType, Dimension, 
CoordinateSystem>> where the three template attributes of 
bg::model::point are taken from the Indexable. Or you could take this 
type from the R-tree (it's rtree::bounds_type).

See also: 
https://stackoverflow.com/questions/19490435/boost-geometry-spatial-query-shapes

I wonder if something could be done about it. Maybe I'll look into it.

> I have put the geometry in bg::model and given it a tag.
> The next error seems meaningful, so I'll include it:
>
> .../boost/geometry/algorithms/detail/disjoint/interface.hpp:65:21: 
> error: ‘value’ is not a member of 
> ‘boost::geometry::topological_dimension<boost::geometry::model::hemisphere<boost::geometry::model::point<double, 
> 2ul, boost::geometry::cs::cartesian> > >’
>
> How do I satisfy these kind of requirements?

This shouldn't be needed if your overload of intersects() was used. This 
is only needed if you want to add a new kind (Concept) of Geometry.

Adam