[geos-devel] [Fwd: Re: [Qgis-developer] Lib_Refactoring-branch update]

[Mateusz Loskot]

Hi,

I'm forwarding some post from QGIS list about GEOS indexing support.
QGIS team is discussing about spatial indexing and pros/cons of GEOS
indexing support.

I believe it may be interesting for GEOS developer and may be there is
something worth to explain to QGIS team regarding GEOS features.

Cheers
Mateusz

-------- Original Message --------
Subject: Re: [Qgis-developer] Lib_Refactoring-branch update
Date: Wed, 6 Dec 2006 15:06:58 +0100
From: Martin Dobias <wonder.sk at gmail.com>
To: Marco Hugentobler <marco.hugentobler at karto.baug.ethz.ch>
CC: qgis-developer at lists.qgis.org
References:
<e8e7199c0612060450j27908280ndf0fdf5303dafcce at mail.gmail.com>
<200612061408.54902.marco.hugentobler at karto.baug.ethz.ch>

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
_______________________________________________
Qgis-developer mailing list
Qgis-developer at lists.qgis.org
http://lists.qgis.org/cgi-bin/mailman/listinfo/qgis-developer


-- 
Mateusz Loskot
http://mateusz.loskot.net