Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-01-21 15:13:27

Simonson, Lucanus J wrote:
> Then, in terms of implementation the most important thing is to define an iterface that is generic and sufficiently general to accommodate a range of possible implementations.  Once we have that we have a research test bed for implementing different data structures and testing them through a common iterface to assess their suitability.  Different applications are best served by different data structures, but if we can provide a common iterface then people can map their own data structures to the interface and allow boost.geometry to interoperate with their spatial query data structures when performing algorithms based on spatial query.  This is similar to how boost graph allows the same graph algorithms to work on different graph data structures.  I realize that it is tempting to implement things like nearest neighbor using internal knowledge of the query data structure, but I think it should be a priority to decouple the algorithms from the data structures.

In terms of query interface.

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

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);

Therefore I think that the idea of wrapping the interafce in the range 
object is very good.

2. Objects representation

Various spacial indexes may contain various objects (polygons/points) 
representations including:
- copies of objects
- references/pointers.
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
 > }

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)))
{
   // do something with p
}

Or

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))
{
   // do something with sorted points
}

Or

BOOST_FOREACH(my_polygon_type const& p, my_spatial_index | 
boost::geometry::adaptors::line_filter(my_line_string))
{
   // do something with sorted polygons
}

Suppose we want to iterate over points closest to some point inside some 
volume.

BOOST_FOREACH(my_point_type const& p, my_spatial_index | 
boost::geometry::adaptors::nearest_filter(my_point_type(5, 5)) | 
boost::geometry::adaptors::filter(my_polygon))
{
   // do something with sorted polygons
}

3. Interface

User should:
- Implement my_range and adapt it to the range concept.
- Overload my_range operator|(my_spacial_index, choosen_range_generator)

4. Additional queries

In addition to 3 user should:
- implement a my_range_generator

Regards,
Adam Wulkiewicz