Boost logo

Geometry :

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 && ...


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:


Functions returning geometries:

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

Functions returning other values:


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.


Geometry list run by mateusz at