Geometry Boost List: [ggl] rtree query expression

Subject: [ggl] rtree query expression
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-08-25 17:42:04

Simonson, Lucanus J wrote:
>
> I like the idea of having a concept.  Normal query tree semantics are to return everything that is overlapping or touching a single axis-parallel query rectangle.  It is acceptable, in my view, to make a query tree concept with simplified interface and a query tree data structure and algorithms that can model the concept, but provide quite a few options that aren't required by the concept.  For example, we wouldn't expect a model of the concept to provide sorting queries like nearest neighbor, but we might implement such an algorithm using the concept, but the implementation might be less efficient than the one provided by your own query tree data structure.  With repeated rectangle queries you can find the k nearest neighbors, but a query tree can do the same with a single query if the query algorithm has direct access to the internals of the tree.  We can't require direct access to internals for the concept.

Ok, so as a starting point I propose something like this:

 From the view of the user-interface:

index::query(tree, index::intersects(Geometry))
index::query(tree, index::within(Geometry))
index::query(tree, index::covered_by(Geometry))
index::query(tree, index::overlaps(Geometry))

index::nearest(tree, Point, k)
index::nearest(tree, Point, k, index::intersects(Geometry))
index::nearest(tree, Point, k, index::within(Geometry))
index::nearest(tree, Point, k, index::covered_by(Geometry))
index::nearest(tree, Point, k, index::overlaps(Geometry))

Possibly:

index::query(
   tree,
   std::pair<
     index::intersects(Geometry1)
   , index::intersects(Geometry2)
   >
)

index::query(
   tree,
   boost::tuple<
     index::intersects(Geometry1)
   , index::intersects(Geometry2)
   , index::within(Geometry3)
   >
)

Regards,
Adam