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