Boost logo

Geometry :

Subject: [ggl] rtree query expression
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-08-25 20:00:38


Simonson, Lucanus J wrote:
> Adam Wulkiewicz wrote:
>> Simonson, Lucanus J wrote:
>>
>> 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)
>> >
>> )
>
> 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)
> >
> )
>

Yes of course.

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

This sounds good. The user may just use boost::cref(). Or we may have
other version of make_tuple() e.g. make_cref_tuple().

In addition to this, there should be some metafunction to define result
type of a query, possibly

index::query_result<Tree>::type
index::nearest_result<Tree>::type

or maby more explicitly

index::query_result<Tree, index::intersects_tag>::type
index::nearest_result<Tree, index::intersects_tag>::type

however the second proposal is going complicated with tuples

index::query_result<
   Tree,
   tuple<index::intersects_tag, index::intersects_tag>
>::type

so I guess the first one is better.

Or maby should it be definable by the user?

// this can't be used as a range
index::query(tree, Geometry, std::back_inserter(...))

or

// this complicates the interface
cont = index::query<ContType>(tree, Geometry)

or reference to the container might be passed optionally as a third
parameter and then returned.

ContType cont;
ContType & cont_ref = index::query(tree, Geometry, cont)

Next thing... I recall that someone have asked about nearest neighbor
queries outside of the spatial index topic. Maby the same interface
should be usable with e.g. stl containers/ranges? Probably in the
different namespace, e.g. geometry::query.

query::query(vect_of_geometires, Geometry) // or query::spatial
query::nearest(vect_of_geometires, Point, k)

Regards,
Adam


Geometry list run by mateusz at loskot.net