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

[Christopher Barker]

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


-- 
Christopher Barker, Ph.D.
Oceanographer

Emergency Response Division
NOAA/NOS/OR&R            (206) 526-6959   voice
7600 Sand Point Way NE   (206) 526-6329   fax
Seattle, WA  98115       (206) 526-6317   main reception

Chris.Barker at noaa.gov