Boost logo

Geometry :

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-02 09:42:23

Bruno Lalande wrote:
> 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.

I thought about traits approach too. The reason why I've decided to use
some object passed to rtree (I've called it translator) is that if
someone wants to store values of the same type in two spacial indexes
but interpret it differently then traits should have some additional
tag. In addition, someone may store values which don't contain data
needed by the spacial index.
E.g. someone have two containers one with boxes, second with points and
he can store just indexes of boxes in one spacial index and indexes of
points in the second one. He must pass the reference to the container
somehow and can do it in the translator.

But I'm open to suggestions.

Later, if there are additional containers, additional methods will be
added. So the name of the translator may be changed.


Geometry list run by mateusz at