Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-08-11 13:08:13

Barend Gehrels wrote:
> Adam Wulkiewicz wrote:
>> Mathias Gaunard wrote:
>>> Le 08/08/2010 21:32, Adam Wulkiewicz wrote:
>>> 
>>>> It depends, how you see these things. You may want spatial index or
>>>> various spacial indexes in Boost.Geometry. But you may also want
>>>> multi-purpose space partitioning containers enclosed in separate
>>>> library. It's a matter of view. Where user should search this
>>>> functionality for? And for what data should these containers work
>>>> for? 
>>> 
>>> Boost.Geometry works with un-intrusive concepts, and allows to use
>>> arbitrary types.
>> 
>> I'm talking about something different. There are many fields where
>> spacial indexes are used. Does user who wants to implement an
>> algorithm extracting features from the picture or searching data in
>> the database should look for needed data structures somwhere deep in
>> the geometry library? Or maby, the geometry library should use
>> functionality provided by the space partitioning library (both using
>> the same concepts)?
> I don't think these are structures deep in the geometry library. It
> can 
> be the structures of the users, something in a picture or database.
> Which is "adapted" to the Boost.Geometry Point Concept (this is
> normally 
> done by one Macro call).
> 
> The spatial index could then use the Point Concept of Boost.Geometry,
> and both libraries will work together happily.

Why would a person doing image processing or database development think that their need for spacial indexes are somehow not a need for computational geometry?  I'm quite sure the database developers feel the spatial indexes they already have are superior to anything we are using in VLSI or GIS, and they are undoubtedly right to the extent that their data structures are better suited to the needs of their application.  Their spacial indexes would likely not be suitable for VLSI compared to our own data structures.  The performance of a spacial index is heavily dependent on the characteristics of the data it stores.  I hope we all understand that up front because it will cut down on silly arguments about performance later on.  If Adam said he was writing a database building blocks library that was going to feature spacial indexese tailored to meet the needs of database query then Boost.Geometry would be a bad place to put it.  However, Adam is saying he plans to implement a generic spacial indexes library with several different types of data structures and wants it to be used in multiple application domains.  Adam may not realize it, but computational geometry is not an application domain.  There are many application domains where computational geometry is used.  Does a user who wants to implement an algorithm for extracting features from an image or searching for data in a Geospacial database want to look in the geometry library to find something they both need?  Maybe not, but it is better to put those things that are needed in several application domains in a common library which is meaninfully named and easy to find instead of having a separate application domain specific library for each type of user.  Geometry is the right name for a library that contains spacial indexes because spacial indexes are computational geometry unless they are otherwise encumbered with domain specific jargon in the interfaces or tailored to domain specific needs.

So now lets talk about software design.  If spacial indexes will depend on the Boost.Geometry library for low level features like point concept and traits that we generally agree will be a good idea for interoperability and Boost.Geometry will depend on spacial indexes to implement high level algorithms like closest neighbor query (which they provide now, but would like to optimize by using a good spacial index) then spacial indexes should go in Boost.Geometry to avoid cyclic dependency between libraries.  The alternative is to partition Geometry into algorithms that do depend on spacial indexes, which would go in the spacial indexes library, and algorithms that do not, which would stay in Geometry.  Such a partition is abitrary and nonsensical.

I don't think it would be inconvenient for Adam to work with the Geometry library authors and I think he could benefit from their experience and direct help with the implementation of his vision for a generic spacial indexes capability in boost.  Given recent experience I don't think the community would accept spacial indexes as its own library now that Geometry has been accepted.

Regards,
Luke