[gdal-dev] Re: Looking for advice on finding neighboring features

sgillies at frii.com sgillies at frii.com
Wed Dec 3 15:39:12 EST 2008

> I'm no expert, but I have some thoughts.
> A) this really isn't a GDAL issue -- GDAL is about reading ant writing
> the data -- you're interested in processing. you might want to look at
> the geos lib.
>> In order to get this profile, I want to do a spatial query on DEM
>> shapefiles
> DEMs are usually gridded data -- a shapefile is odd for this. Is it
> gridded?
>> someone gives me a large shapefile, e.g. that of a whole country, I
>> don't know if computationally it's reasonable to perform a proximity
>> check on every single feature in the shapefile. I suppose this would
>> be O(2), which could get quite expensive/long for a microprocessor or
>> some kind of embedded platform.
> yup.
> What you need is a spatial index. I think shapelib has one built in --
> you load the shapefile, index it, and then these sorts of neighbor
> queries are fast. (order logN, I think).
> You could also use:
> http://trac.gispython.org/spatialindex/wiki/
> and there are python bindings for geos and rtree:
> http://pypi.python.org/pypi/Rtree
> http://pypi.python.org/pypi/Shapely/1.0.11
> which may be helpful for prototyping.
>> What I was hoping to discover is whether shapefiles have some field in
>> a feature that says what other features share common points.
> nope -- they are pretty simple, really.
> -Chris

Spatialindex/Rtree also support efficient queries for the N nearest

FWTools includes a program called shptree, which makes quad trees for
shapefiles. Once you have one of those, you could find all neighbors
fairly efficiently using nothing other than ogr.py.


More information about the gdal-dev mailing list