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

[Kenn Sebesta]

Based on some conversations of the list, I've come to understand a
little better what I'm looking for, so I'll update my original
question here so it's a bit clearer.

I need to write a program that automatically determines elevation
profiles based on a predetermined path/route. This data needs to come
be in some form that it automatically can be read by further functions
in my controls package. I plan to do everything in C, but any other
processing language would be acceptable.

In order to get this profile, I want to do a spatial query on DEM
shapefiles in order to find nearest neighbors, without spending mass
amounts of computing power doing it. I really don't have a good sense
of the nitty-gritty of how shapefiles are made and organized, so if
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.

What I was hoping to discover is whether shapefiles have some field in
a feature that says what other features share common points. Looking
at the data I can extract with GDAL, and then being pointed to
OpenJump and getting a good look at the fields in the feature table,
it doesn't seem this is the case. Can someone confirm this?

I suppose I can just go feature by feature and check, based on its
coordinates, how far away from a given feature the other features are.
I could then save into a database all other features within a certain
epsilon, say 10m. This would work, but it seems to me that there are
far more efficient ways of doing this. Moreover, it seems that this
method is a little naive and could wind up being far from robust,
which would imply redoing the algorithm every time I change map
editions/distributors/companies/etc.

I would like to avoid reinventing the wheel, so I'm asking your advice
to what way is the best to program this. Perhaps there's already an
algorithm/library to do this?

If not, are there any pitfalls I should know of? Could I do it with a
simple raster, knowing that it is absolutely necessary that I can
differentiate between a path that passes above another path without
physically crossing, such as a tunnel or bridge?

Cheers,
Kenn Sebesta