Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Bruno Lalande (bruno.lalande)
Date: 2011-03-02 08:05:00

Hi,

>> The Translator is an object that translates Value const& to some Point/Box
>> const&. I've also added method:
>>
>> bool equals(Value const&, Value const&) const
>>
>> but I don't know if it's the best place for it.
>>
>
> Yes, I see what you mean. Can either stay there or become a free function.
> If existing structures are adapted etc, a free function would be better. But
> this is not so probable here.
>
> Bruno, any preference?

Actually I was wondering if we shouldn't have some namespace "indexable" in
which all the functions possibly needed by an indexing structure to manage
its indexables would live (by "indexable" I mean "any stuff that can be put
into a spatial index structure", i.e. your "Values"). An r-tree needs to
know whether an indexable is within some box. A BSP tree needs to know
whether an indexable intersects with a plane and if not, on which side it
is. Etc... so maybe each of those should be a function template like:

namespace indexable {

template <class Indexable>
bool equals(const Indexable&, const Indexable&);

template <class Indexable, class Box>
bool is_in_box(const Indesable&, const Box&);

template <class Indexable, class Plane> // Plane is a future concept of
course...
book intersects(const Indexable&, const Plane&);

etc...

}

and the default implementation would try to use what we already know about
the Indexable if it happens to be something known. For instance if it's a
Point, we perfectly know how to compare 2 points or how to determine if a
point is in a box so there would be some tag-dispatching-based
specializations that would forward to the appropriate boost::geometry
functions. And if the user wants to use a complicated 3D-mesh structure as
the indexable for instance, and doesn't want to (or cannot!) fully adapt it
to Boost.Geometry, he can just define those few functions so that the index
structure can work on it. If his 3D mesh uses some complicated oriented
bounding box tree internally to determine intersections, he can use them to
implement those functions.

Does that make sense? Sorry I'm still catching up on this discussion, maybe
I'll have more to say later about the big picture, I still have to think
about some details... I might have more general suggestions to make but not
sure. Anyway, the Translator principle generally sounds like a good idea.

Regards
Bruno

>
>
>
>  Default translator
>>
>> translator::def<Value> translates from:
>>
>> 1. SomePoint/SomeBox;
>> 2. std::pair<T1, T2> - One of the types must be SomePoint or SomeBox;
>> 3. iterator holding 1. or 2.;
>> 4. smart pointer pointing on 1. or 2.;
>> 5. pointer pointing on 1. or 2.;
>>
>> There is also a translator::index which handles indexed geometries in some
>> container.
>>
>> The Box is the box type used by the rtree which by default is SomeBox or
>> geometry::model::box<SomePoint>.
>>
>> There are a few examples in tests/rtree_native.cpp.
>>
>
> I really like this new interface! Just added (to play with it) two
> functions of a combination which was not there (pair of point/int):
>
> template <typename R>
> void print_point_pair_range(R const& r)
> {
>    BOOST_FOREACH(typename boost::range_value<R const>::type const& item, r)
>    {
>        std::cout << item.second << ": " << boost::geometry::dsv(item.first)
> << std::endl;
>    }
>    std::cout << std::endl;
> }
>
>
> void test_point_pair()
> {
>    typedef boost::geometry::model::point<double, 2,
> boost::geometry::cs::cartesian> P;
>
>    boost::geometry::index::rtree< std::pair<P, int> > index(3, 0);
>    index.insert(std::make_pair(P(0, 0), 0));
>    index.insert(std::make_pair(P(2, 2), 1));
>    index.insert(std::make_pair(P(4, 4), 2));
>    index.insert(std::make_pair(P(6, 6), 3));
>    print_point_pair_range(index |
> boost::geometry::index::filters::spatially_filtered(
>                boost::geometry::model::box<P>(P(2.5, 2.5), P(4.5, 4.5))));
> }
>
> And it is working and looking good like this.
>
> Thanks, Barend
>
>
>
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110302/db432211/attachment.html