[gdal-dev] Open source vector geoprocessing libraries?

[Jason Roberts]

Mateusz,

I'm not an expert in this area, but I think that big performance gains can
be obtained by using a spatial index. For example, consider a situation
where you want to clip out a study region from the full resolution GSHHS
shoreline database, a polygon layer. The shoreline polygons have very large,
complicated geometries. It would be expensive to loop over every polygon,
loading its full geometry and calling GEOS. Instead, you would use the
spatial index to isolate the polygons that are likely to overlap with the
study region, then loop over just those ones. I do not know much about
spatial indexes yet, but I suspect they do something like store the
rectangular envelope of each feature, which can then be quickly compared to
other envelopes to determine whether it is possible for features to overlap.

If OGR takes advantage of spatial indexes internally (e.g. if the data
source drivers can tell the core about these indexes, and the core can use
them when OGRLayer::SetSpatialFilter is called), then many scenarios could
be efficiently implemented by just OGR and GEOS alone. Of course, it might
get more complicated when you have two layers to perform the operation on,
rather than one layer and a single feature. I'm sure that others have done a
lot of thinking about how to optimize the different scenarios, while I
haven't done much. This is why I wondered if there was another library for
doing this kind of thing.

If not, then your suggestion may be as fast as any other. For example, the
idea of loading the features in to PostGIS or SpatiaLite will require
loading all of the full geometries, passing them to another database system,
etc, etc. It may be that shuffling all of the data around will be hugely
expensive and that just using OGR functions with simple approaches like
calling GEOS from nested loops will be faster than shuffling the data to a
system that implements a more efficient approach once the data gets there.
Is that basically what you are saying? Or have I totally missed the point?

Thanks for your thoughts,

Jason

-----Original Message-----
From: Mateusz Loskot [mailto:mateusz at loskot.net] 
Sent: Tuesday, January 12, 2010 5:51 PM
To: Jason Roberts
Cc: 'gdal-dev'
Subject: Re: [gdal-dev] Open source vector geoprocessing libraries?

Jason Roberts wrote:
> By integrating with GEOS, OGR can perform various spatial operations on
> individual geometries, such as buffer, intersection, union, and so on. Is
> there a library that efficiently performs these kinds of operations on
> entire OGRLayers? For example, this library would have functions that
would
> buffer all of the features in a layer, or intersect all of the features in
> one layer with all of those in another. Basically, I am looking for an
open
> source technology that replicates the "geoprocessing tools" found in
ArcGIS
> and other GIS packages. These tools traditionally operate on one or more
> layers as input and produce one or more layers as output.

What prevents you from calling GEOS and process all features in a layer?

I've used GEOS processing layers of large number of features
in similar manner as PostGIS would, but programmatically (C++).

For example, generating buffer from tens of polygons
or performing boolean operations like cookie-cutting
layer of 1000-2000 polygons with one polygon.

IMHO, I can't see much point making a new library.

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org