[Qgis-developer] Lib_Refactoring-branch update

[Martin Dobias]

On 12/6/06, Marco Hugentobler <marco.hugentobler at karto.baug.ethz.ch> wrote:
> Hi Martin,
>
> I have a question regarding the spatial indexing. Do you use it additionally
> to the indexing on the provider level or just for providers which do not
> offer indexing (but AFAIK most do)?

Hi Marco,

currently spatial indexing is just a feature that no other part of
QGIS uses (so far).  But I have a long-time vision of offering some
functionality for provider if it doesn't support that natively:
- fast spatial lookup - using spatial indexing
- filtering features by attributes - using search strings
- fast feature retreiving - by caching of features in memory
- maybe also fast attribute searching - using B-trees or similar

Of course PostGIS or GRASS can do all or most of them, but e.g. OGR
has only limited support for this and some providers doesn't support
such things at all. With this we could enforce creation of new
interesting providers and allowing them good performance.


> I implemented spatial indexing in the WFS provider using the geos library.
> They provide STR tree (modified R-Tree) and Quadtree. It would be interesting
> to know about the pros and cons of geos compared to spatial indexing library.

I took a look at STR tree in geos, but I must say I wasn't very happy
with it. Cons:
- lack of documentation and quite hard to find information about STR
trees anywhere
- supports only intersection query
- unable to insert/delete/modify it once built
- supports storing index only in memory
- I haven't studied the code to details but it looks like that it's
using only vertical slices for indexing instead of using regions (?)

Thus R-tree is winner for me - it's much more flexible. But it might
be interesting to compare the performance of the stuctures.

Martin