Geometry Boost List: [ggl] rtree query expression

Subject: [ggl] rtree query expression
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-08-24 16:00:52

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?

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?

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.

Other thing is that in Boost new features are implemented and if we use 
EDSL we can allways say that we brings something new to spatial indexes 
like Boost allways did. Just not mention increased compile times ;).

So I guess that by now I can implement this simplified interface and 
maby later we can extend it somehow.

I'd like to hear what Barend have to say about it?

Regards,
Adam