Geometry Boost List: [ggl] rtree query expression

Subject: [ggl] rtree query expression
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-08-24 16:19:34

Adam Wulkiewicz wrote:
> Simonson, Lucanus J wrote:
>> 
>> Before we create an EDSL for this lets see if a simple design will
>> work. 
>> 
>> It seems to me that sorting queries are fundamentally different from
>> query criteria, no need to mix them. 
>> 
>> Why not have a regular query operation that is a fuction named
>> query() that accepts query criteria such as inside/outside of query
>> boxes.  Then for each type of sorting query you have an alternative
>> function call like nearest_neighbors() that accepts arguments
>> specific to nearest neighbor query and then the normal arguments
>> that query would accept.  For predicates why do we need to combine
>> them with operators?  Why not just compute the query region and have
>> a flag (or enum) whether to accept geometries that touch the query
>> region versus are completely contained within it.  For example:
>> "find k objects closest to some point but further than 10 and
>> objects should be within some geometry" would become:          
>> 
>> neighbor_result = nearest_neighbors(query_tree, some_point, k, 10,
>> some_geometry, contained_completely); 
>> 
>> Why not use the boolean operations on polygons to generate the
>> single geometry that is your query region.  Use the bounding box of
>> the query_treen NOT whatever keepout region to invert the logic of
>> the query region.  Only if you have a complex case such as give me
>> objects completely inside box1 AND touching or completely inside
>> box2 would you need something more, since different semantics apply
>> to different areas of the query region.  That is a pretty strange
>> query, not at all the common case.  I would find support for it
>> surprising.        
> 
> Have you any preference if contained_completely should be run-time or
> compile-time parameter Lucanus?

The only argument for compile time is better compiler optimization.  As an interface I would prefer runtime, but if you choose to dispatch to compile time functions as an optimization that would be fine.  I don't like to see interface usability harmed by optimization concerns if avoidable.
 
> Ideally we'd have to pass some predicate as it was suggested
> previously: 
> 
> index::nearest_neighbors(
>    tree,
>    some_point_or_other_geometry,
>    k,
>    some_predicate_function
> );
> 
> index::query(
>    tree,
>    some_predicate_function
> )
> 
> then the user could choose if he want to use some predefined common
> predicate e.g.
> 
> index::within(some_geometry),
> index::intersects(some_geometry)
> index::contained_completely(some geometry)
> 
> or whatever. Or maby use some self-implemented
> 
> my_within_and_not_intersects(some_geometry1, some_geometry2)
> 
> or even some Phoenix/lambda expression.
> 
> But the problem is that different tests should be called for e.g.
> values in rtree leafs and for rtree children nodes in the traversing
> process. E.g. if we search for values within some geometry, nodes
> should intersect this geometry (possibly without border case i.e.
> [(0,0),(1,1)] and [(1,1),(2,2)] should give false). Or if we want
> that values should disjoint some geometry then nodes shouldn't be
> covered by this geometry. So the user would be forced to define 2
> predicates. What is more, possibly other tests would be needed in
> various spatial indexes (kdtrees, qctrees, grids etc). So if we don't
> take an expression, analyzes/transforms it to the right form we
> should implement as simple query as possible with some predefined
> predicates and don't handle anything else. Quite restrictive... Or
> maby someone has other idea? 

I don't believe the user will be able to define their own predicate to pass as a template paramter because this is too complex and requires too much knowledge of the inner workings of the tree.  Such a predicate could be an implementation detail of the query, however.

> Another issue is that there may be some algorithms inside
> Boost.Geometry which may be using spatial indexes. Maby we should
> design some spatial_index concept (which is partially done) because
> the user may want to adapt his own spatial index and use it inside
> this algorithm. What do you think about this Barend? Do you expect
> something like this to be created? If so, then maby the interface
> should be even simpler because user-defined index may not implement
> predicates or implement some types of queries. I'm worried that this
> algorithm would look like: 
> 
> if ( index::implements<some_user_index, something1>::value )
>    // do something
> else if ( index::implements<some_user_index, something2>::value )
>    // do something else less efficiently
> else
>    some_assert();
> 
> But with simple interface it will be at least possible and with EDSL
> rather not. And A LOT simpler to implement and maintain.

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.

Regards,
Luke