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

[sgillies at frii.com]

> 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
neighbors.

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.

Cheers,
Sean