
Geometry : 
Subject: [ggl] rtree query expression
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 20110825 18:20:11
Adam Wulkiewicz wrote:
> 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
>> axisparallel 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 userinterface:
>
> 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)
> >
> )
That looks like an entirely reasonable proposal to me assuming you also intend also possibly:
index::nearest(
tree, Point, k,
boost::tuple<
index::intersects(Geometry1)
, index::intersects(Geometry2)
, index::within(Geometry3)
>
)
We get variadic argument packs to the query functions by using tuple and don't have to do any of the work of building our own EDSL for combining query criteria.
Might I suggest that Geometry default to intersects semantics for the query critera so that
index::query(tree, Geometry)
index::nearest(tree, Point, k, Geometry)
are equivalent to:
index::query(tree, index::intersects(Geometry))
index::nearest(tree, Point, k, index::intersects(Geometry))
That way we can write:
results = index::query(my_tree, query_box);
and get the expected behavior out of the tree for the simplest cases with the simplest code? This could extend to tuples but there is the slight problem that tuple stores a copy of each element, while intersects<> could store a reference and make light weight use of the geometry. Perhaps we would require that tuple not include bare geometry elements, or just document that doing so incurs a performance penalty due to extra copying.
Regards,
Luke
Geometry list run by mateusz at loskot.net