Geometry Boost List: [ggl] rtree query expression

Subject: [ggl] rtree query expression
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-08-25 18:20:11

Adam Wulkiewicz wrote:
> Simonson, Lucanus J wrote:
>> 
>> I like the idea of having a concept.  Normal query tree semantics
>> are to return everything that is overlapping or touching a single
>> axis-parallel query rectangle.  It is acceptable, in my view, to
>> make a query tree concept with simplified interface and a query tree
>> data structure and algorithms that can model the concept, but
>> provide quite a few options that aren't required by the concept. 
>> For example, we wouldn't expect a model of the concept to provide
>> sorting queries like nearest neighbor, but we might implement such
>> an algorithm using the concept, but the implementation might be less
>> efficient than the one provided by your own query tree data
>> structure.  With repeated rectangle queries you can find the k
>> nearest neighbors, but a query tree can do the same with a single
>> query if the query algorithm has direct access to the internals of
>> the tree.  We can't require direct access to internals for the
>> concept.              
> 
> Ok, so as a starting point I propose something like this:
> 
>  From the view of the user-interface:
> 
> index::query(tree, index::intersects(Geometry))
> index::query(tree, index::within(Geometry))
> index::query(tree, index::covered_by(Geometry))
> index::query(tree, index::overlaps(Geometry))
> 
> index::nearest(tree, Point, k)
> index::nearest(tree, Point, k, index::intersects(Geometry))
> index::nearest(tree, Point, k, index::within(Geometry))
> index::nearest(tree, Point, k, index::covered_by(Geometry))
> index::nearest(tree, Point, k, index::overlaps(Geometry))
> 
> Possibly:
> 
> index::query(
>    tree,
>    std::pair<
>      index::intersects(Geometry1)
>    , index::intersects(Geometry2)
>    >
> )
> 
> index::query(
>    tree,
>    boost::tuple<
>      index::intersects(Geometry1)
>    , index::intersects(Geometry2)
>    , index::within(Geometry3)
>    >
> )

That looks like an entirely reasonable proposal to me assuming you also intend also possibly:

 index::nearest(
    tree, Point, k,
    boost::tuple<
      index::intersects(Geometry1)
    , index::intersects(Geometry2)
    , index::within(Geometry3)
    >
 )

We get variadic argument packs to the query functions by using tuple and don't have to do any of the work of building our own EDSL for combining query criteria.

Might I suggest that Geometry default to intersects semantics for the query critera so that
 index::query(tree, Geometry)
 index::nearest(tree, Point, k, Geometry)
are equivalent to:
 index::query(tree, index::intersects(Geometry))
 index::nearest(tree, Point, k, index::intersects(Geometry))

That way we can write:

results = index::query(my_tree, query_box);

and get the expected behavior out of the tree for the simplest cases with the simplest code?  This could extend to tuples but there is the slight problem that tuple stores a copy of each element, while intersects<> could store a reference and make light weight use of the geometry.  Perhaps we would require that tuple not include bare geometry elements, or just document that doing so incurs a performance penalty due to extra copying.

Regards,
Luke