Subject: [ggl] space partitioning
From: Barend Gehrels (barend.gehrels)
Date: 2011-01-24 05:07:33
Hi Adam,
Thanks for your four messages on this spatial indexes.
>
> 1. Types of queries and interfaces
>
> We may have various types of queries. Returned data may be different.
> It may be just an iterator performing the incremental search or some
> data structure which must be initialized, and destroyed after the
> search is finished. In general, if elements must be sorted somehow
> it's big probability that the spacial index will return some data
> structure containing sorted objects. These containers may or may not
> define iterators.
>
> Examples of queries:
> - not sorted objects inside some bounding volume (aabb, sphere, etc.).
> - sorted objects closest to some point in space, or some number of
> closest objects, or even some number of closest objects inside some
> bounding volume.
> - sorted objects on a way of a ray (may be line segment or even a
> n-dimensional beam of some kind).
I agree with this.
>
> Examples of interfaces:
>
> found_photons fp(max_distance, max_photons);
> kdtree.search(fp);
> for(size_t i= 0; i < fp.number(); ++i)
> do_something(fp.get(i));
>
> mRaySceneQuery = mSceneMgr->createRayQuery(Ogre::Ray(...));
> Ogre::RaySceneQueryResult &result = mRaySceneQuery->execute();
> for( Ogre::RaySceneQueryResult::iterator itr = result.begin();
> itr != result.end();
> ++itr)
> {
> do_something(*itr);
> }
> mSceneMgr->destroyQuery(mRaySceneQuery);
I prefer a pointerless approach, if possible. Or are these copied as a
sample from another (Ogre) library?
>
> Therefore I think that the idea of wrapping the interafce in the range
> object is very good.
Prefect
>
> 2. Objects representation
>
> Various spacial indexes may contain various objects (polygons/points)
> representations including:
> - copies of objects
> - references/pointers.
Storing copies is possible but (I think) inconvenient in many cases.
Storing references and/or pointers is normally dangerous. What if you
add something to the container?
Therefore Federico invented the coupling with any kind of
(user-definable) Identifier and I that works well. If there are really
no identifiers, then storing copies might be a solution. By the way, a
geometry itself, OR even a pointer, might be an identifier (though I
would not advise this) so this scenario probably covers everything.
> But may be able to contain some other types of ids (indexes, handles,
> etc.). Should the spacial index perform the translation between ids
> and references to objects or should it be performed on the interface
> level? It would be nice to have simple interface and shouldn't
> implement all possibilities. Instead of
>
> > BOOST_FOREACH(my_polygon_type const& p, polygon_collection |
> > boost::geometry::adaptors::spatial_filter(my_box_type(my_spatial_index,
> > 5, 5, 10, 10)))
> > {
> > // do something with this polygon p, guaranteed intersecting the
> > specified box
> > }
Note that my sample was not 100% correct, I meant
BOOST_FOREACH(my_polygon_type const& p, polygon_collection |
boost::geometry::adaptors::spatial_filter(my_spatial_index,
my_box_type(5, 5, 10, 10)))
{
// do something with this polygon p, guaranteed intersecting the
specified box
}
so the index is not within the box (of course).
>
> We would have
>
> BOOST_FOREACH(my_polygon_type const& p, my_spatial_index |
> boost::geometry::adaptors::spatial_filter(my_box_type(5, 5, 10, 10)))
I see, so here the index contains the polygons. I prefer to keep them
separate, at least in the default case.
>
> BOOST_FOREACH(my_point_type const& p, my_spatial_index |
> boost::geometry::adaptors::nearest_filter(my_point_type(5, 5),
> max_distance, max_number_of_points))
> BOOST_FOREACH(my_polygon_type const& p, my_spatial_index |
> boost::geometry::adaptors::line_filter(my_line_string))
> BOOST_FOREACH(my_point_type const& p, my_spatial_index |
> boost::geometry::adaptors::nearest_filter(my_point_type(5, 5))
Thanks for all your nice samples here, and in your other mails. It looks
great if all these would be there!
> User should:
> - Implement my_range and adapt it to the range concept.
> - Overload my_range operator|(my_spacial_index, choosen_range_generator)
The library user? Basically the scenario is to implement the operator |
as is done in Boost.Range, I think this need to be done only once per
filter.
>
> 4. Additional queries
>
> In addition to 3 user should:
> - implement a my_range_generator
I don't get this, or my remark on 3 applies.
>
> Another option is to have lazily evaluated queries
IIRC, most Boost.Range adaptors are implemented lazy. So yes, this is a
good option
Regards, Barend
-- ------------------------------------- Barend Gehrels ------------------------------------- http://trac.osgeo.org/ggl http://www.geodan.nl ------------------------------------- Geodan President Kennedylaan 1 1079 MB Amsterdam The Netherlands ------------------------------------- Tel: +31 (0)20 5711 335 Mob: +31 (0)6 175 447 62 Fax: +31 (0)20 5711 333 ------------------------------------- E-mail: barend.gehrels_at_[hidden] Kvk-nummer: 33 207089 Disclaimer: www.geodan.nl/disclaimer -------------------------------------