Geometry Boost List: [ggl] rtree query expression

Subject: [ggl] rtree query expression
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-08-22 14:22:22

In order to perform a query some expression could be passed to the 
container. It doesn't matter how (see rtree query interface thread). For 
simplicity, lets say that it looks like this:

result_type result = tree.query(Expression);

How this expression should look like is another thing. I'd like to 
propose something and listen to your arguments.

Below I assume that everything is in the geometry::index namespace.

Placeholder (which is later replaced by value stored inside index inside 
the query) is _. So intersects(_, g1) means that returned values should 
intersect geometry g1.

Basic form of an expression looks like this:

factor && factor && factor && ...

e.g.

within(_, g1) && !intersects(_, g2) && disjoint(g3, _)

operator || isn't used because the query build with subexpressions 
connected by || will be performed slower than some number of queries 
without ||. More nodes will be choosen at each traversing step than it 
should be. Alternative is rebuilding the expression at each traversing 
step but this will be slow as well. Moreover this makes problems with 
kNN, well kNN makes a lot of problems btw.

Factor may be a function or some relation operator possibly preceeded by !.

operator! can't be applied to operator&&: !(within() && intersects()) is 
invalid because it's equal to !within() || !intersects(). Or maby could 
this kind of operation be usefull? E.g. This is the only way to describe 
some relation.

Below I'll write some examples, be patient.

Functions returning logical value:

covered_by
disjoint
intersects
overlaps
within

Functions returning geometries:

return_centroid/centroid - should be return_centroid I guess
intersection		 - what if there is no intersection? (below)

Functions returning other values:

area
perimeter
comparable_distance
distance

For now without kNN.

// Values within g1 and not intersecting g2
within(_, g1) && !intersects(_, g2)

// Values within g1 and having g2 inside
within(_, g1) && within(g2, _)

// Values which centroids are in g1 and arent intersecting g2
within(return_centroid(_), g1) && !intersects(_, g2)

// Intersection problem may be solved like this:
// Values intersecting g1 and which this intersection is within g2 for
intersects(_, g1) && within(intersection(_, g1), g2)

// Values in g which area is < 10 and perimeter > 10
within(_, g) && (area(_) < 100) && (perimeter(_) > 10)

kNN in the next email.

Regards,
Adam