Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Mateusz Loskot (mateusz)
Date: 2010-09-10 17:43:27

On 17/08/10 18:52, Adam Wulkiewicz wrote:
> Barend Gehrels wrote:
>>> I'd like to implement kd-tree, quadtree/octree/... and regular grid
>>> because these are data structures I've been playing with. Is it ok? Or
>>> maby should we design one spacial index?
>>
>> For your information, Federico (the student who built the indexes in
>> 2008) did implement a quadtree implementation as well. It is not yet in
>> the extension folder, because I didn't rework the
>> conventions/namings/etc, but I can provide it of course. Yes it is good
>> to add the things that are available. I just forgot after a while.
>>
>> I think it would be good if there is one library "interface" (Concept)
>> with some different implementations. However, the r-tree implementation
>> which is currently there does not follow this.
> 
> Is this n-dimensional "quad tree"?

Adam,

AFAIR, Frederico's implemenation was only for 2d space.

> Has it proper interface?

If you define what you mean as "proper", it will be possible to answer.

Generally, it does not follow Boost.Geometry design rationale.
It is based on runtime polymorphism. The index is parametrized by box.
In my opinion, it is good to take a look at it as at a proof of concept,
a prototype which can be useful to derive new final design and
implementation.

Just to allow you to take a look at this work, I have attached
ggl-index.7z archive with one of latest version.

>>> Btw, do you plan to have some generic linear algebra in the library?
>>
>> There is some which might be given that name, but note that there is (at
>> least one) another library being developed within Boost. That is a very
>> promising one and I hope it is reviewed soon.
>>
>> http://www.revergestudios.com/boost-la/
>>
>> As soon as that is sure, we might use that library for our vector/matrix
>> calculations (also instead of the uBlas we're currently using).
> 
> Yes, I've got similar classes in my 'library' but with different
> interface. This functionality is indispensable.

One of the principles in Boost.Geometry is to stick to Boost collection
as much as possible and to avoid introducing new (sub)libraries if for
functionality that already exists in Boost.

BTW, big thanks for your contributions to Boost.Geometry.

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ggl-index.7z
Type: application/x-7z-compressed
Size: 7201 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/ggl/attachments/20100910/b756f2bd/ggl-index-0001.bin