Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-01-24 07:13:59

Barend Gehrels wrote:
> 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?

Yes this is an existing library, 3D graphics engine.

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

Yes, I'm writing about what the interface should look like. The 
interface that is generic and can handle many cases. At this step, I 
don't write about our spacial index but about possible user 
implementations. Something which user or we might want to adapt to our 
query concept.

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

No, I was thinking about an index performing automatic translation from 
IDs to Objects, e.g. containing the reference to the polygon_collection.

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

Sorry, I wasn't clear. The user who wants to adapt his spacial index to 
our concept or we doing it once per index.

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

Or wants to add other, specialized queries.

>>
>> Another option is to have lazily evaluated queries
>
> IIRC, most Boost.Range adaptors are implemented lazy. So yes, this is a
> good option

Yes, and with some user defined indexes It would be possible and not 
possible with others. But ranges covers both methods.

In the Ogre ray query example we could have initialization in the 
range's constructor, querry in the constructor or begin() method, and 
destruction in the range's destructor.

> Regards, Barend
>
>