Geometry Boost List: [ggl] rtree query interface

Subject: [ggl] rtree query interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-07-30 16:33:35

Hi,

I've got some thoughts about the query interface I want to share with 
you. We previously talked about using Boost.Range syntax in the spatial 
queries:

rtree | filter1(...) | filter2(...) | ...

1. Geometrical relationship filters

Some filters may be taken directly from ggl algorithms:

within(g)
covered_by(g)
intersects(g)  or intersected_by or intersecting
overlaps(g)    or overlapped_by or overlapping

t | within(g) - get values within some geometry
t | intersects(g) - get values intersecting some geometry

Note that some filters may refer to the geometry which is passed or to 
the values stored in the rtree. Someone may want to get values within 
some geometry or to get values containing some geometry. He may just use 
previously described filters and connect them (described further) but 
then e.g. 2 operations must be done instead of 1. And for some queries 
this couldn't be possible (with operator| only). So there could be:

- additional filters:                   t | outside(g)
- filters generated by some operator:   t | ~within(g) - confusing
- object passed before in the sequence: t | inv | within(g) - even more 
confusing
- object passed with filter:            t | inv(within(g))

In addition to this every filter can have it's negation generated by 
operator!

!within(g) == not_within(g)
!intersects(g) == not_intersects(g)

Eventually there could be additional filters e.g. "get objects with 0 
coordinate greather than some other object" coords<0, more>(g) etc. It 
would be nice to have e.g. "get points on the right of the linestring"

2. K nearest neighbour filters

nearest(g)	- get nearest value to the geometry g
nearest(g, 5)	- get nearest 5 values to the geometry g

Folowing filters describes geometrical relationship but they'd probably 
be used with NN filter.

further(g, comp_dist1)
closer(g, comp_dist2)
range(g, comp_dist1, comp_dist2)

In addition there could be k furthest neighbor filter:
furthest(g) == !nearest(g)

3. Filters connection

3.1. operator|

"get values within geometry g1 AND not intersecting geometry g2"
t | within(g1) | !intersects(g2)

"get 5 nearest to g2 values overlapping g1" which means
"get values overlapping g1 AND 5 nearest to g2"
t | overlaps(g1) | nearest(g2, 5)

Using this operator filters may be processed sequentially from left to 
right. Like in streams there may be manipulators used e.g. "get objects 
which centroids are nearest to the geometry g1" could look like this:

t | centroid | nearest(g1, 5)

instead of e.g.

t | nearest<centroid_tag>(g1, 5) or
t | nearest(g1, 5, centroid) or
t | nearest(g1, 5, some_strategy)

but

t | centroid::nearest(g1, 5)

looks nice.

But, queries with logical alternatives can't be described this way e.g. 
"get objects within g1 OR intersecting g2". This kind of query performed 
by one tree traversal could be faster than two separate queries. 
Moreover one probably will have to check if there are repeated values in 
both results.

Btw pipe operator| is used here as a conjunction and this is c++ binary 
alternative.

3.2. expressions

By using more operators we lose sequential nature of the querry but we 
get more powerful expressions which may be passed to the query e.g.

"get objects within g1 AND not intersecting g2"
t[within(g1) & !intersects(g2)]

"get objects within g1 OR intersecting g2"
t[within(g1) | intersects(g2)]

"get points closest to the linestring in the areas intersecting geometry 
g1 or within geometry g2"
t[(intersects(g1) | within(g2)) & nearest(ls, 10)]

"get boxes which centroids are closest to the g3 in the areas 
intersecting geometry g1 or within geometry g2" e.g.
t[(intersects(g1) | within(g2)) & centroid(nearest(g3, 10))] or
t[(intersects(g1) | within(g2)) & centroid::nearest(g3, 10)]

But I don't know if all future expresions would be easy to implement 
e.g. expressions with some number of KNN filters alternatives would 
probably gather results in appropriate number of containers because 
objects must be sorted by distance for each KNN filter. Then results 
would probably be connected (checks for repeating objects). But this is 
probably possible.

Or there could be only one KNN search per query but this isn't nice.

Thoughts?

Regards,
Adam