Re: [gdal-dev] Re: Looking for advice on finding neighboring features
Kenn Sebesta wrote: If you release the shapefile constraint, GMT's grdtrack program is lightning fast in interpolating a grid into a series of x,y positions. Well, the only reason I'm using shapefiles is because that's what the mapping department gave me. If a shapefile can be converted into a grdtrack, using some sort of automatic process, then I'm completely ready to switch. Since I don't need much from the data, and won't ever, it doesn't hurt right now to change directions. grdtrack takes plain ascii x,y coordinates. You can get them by converting your shapefiles to gmt formats using ogr2ogr. Joaquim ___ gdal-dev mailing list gdal-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/gdal-dev
Re: [gdal-dev] Re: Looking for advice on finding neighboring features
> 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 ___ gdal-dev mailing list gdal-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/gdal-dev
Re: [gdal-dev] Re: Looking for advice on finding neighboring features
> If you release the shapefile constraint, GMT's grdtrack program is lightning > fast > in interpolating a grid into a series of x,y positions. Well, the only reason I'm using shapefiles is because that's what the mapping department gave me. If a shapefile can be converted into a grdtrack, using some sort of automatic process, then I'm completely ready to switch. Since I don't need much from the data, and won't ever, it doesn't hurt right now to change directions. Kenn P.S. Since it's now clear to me that my my request is outside the scope of GDAL/OGR, if someone wants to steer me to a better forum I'd be happy to repost there. ___ gdal-dev mailing list gdal-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/gdal-dev
Re: [gdal-dev] Re: Looking for advice on finding neighboring features
Kenn Sebesta wrote: 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. Ken, If you release the shapefile constraint, GMT's grdtrack program is lightning fast in interpolating a grid into a series of x,y positions. Joaquim Luis ___ gdal-dev mailing list gdal-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/gdal-dev
Re: [gdal-dev] Re: Looking for advice on finding neighboring features
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 [EMAIL PROTECTED] ___ gdal-dev mailing list gdal-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/gdal-dev
[gdal-dev] Re: Looking for advice on finding neighboring features
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 ___ gdal-dev mailing list gdal-dev@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/gdal-dev
