Geometry Boost List: [ggl] space partitioning

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: [phone]
Mob: [phone]
Fax: [phone]
-------------------------------------
E-mail: barend.gehrels_at_[hidden]
Kvk-nummer: 33 207089
Disclaimer: www.geodan.nl/disclaimer
-------------------------------------