Boost logo

Geometry :

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:



then the user could choose if he want to use some predefined common
predicate e.g.

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

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?


Geometry list run by mateusz at