[Gdal-dev] ogr find neighbours

[Frank Warmerdam]

Didrik Pinte wrote:
> Hi,
> 
> In the process of implementing a model, I need to get a list of
> neighbours for a shapefile containing polygons.
> 
> The file contains 11 polygons having lots of points.
> 
> The very simple python code i've developped now is just to test if for
> each polygon it touches or overlaps the other polygons from the file.
> 
> BUT :
> 
> with 11 polygons, I makes 122 (11 * 11) tests of geometry.Touches and
> 122 tests of geometry.Overlaps. This is done in 60 seconds and thus is
> too slow.
> 
> By hand, I can do it in 15 seconds maximum taking into account the time
> to open the file with GRASS ;-)
> 
> Does anyone here have a great idea on how to do this more quickly ? 
> 
> I've pasted the code below.
> 
> Thanks for your help

Didrik,

I would suggest only using Touches() and Overlaps() on polygons whose extent
overlaps.  Touches() and Overlaps() are very expensive.

In fact, you might want to install a spatial filter with a box slightly
larger than your polygon.  Then if you build a spatial index for your
shapefile you will only have to read and examine a very small number of
polygons assuming your polygons aren't too extreme.

Best regards,
-- 
---------------------------------------+--------------------------------------
I set the clouds in motion - turn up   | Frank Warmerdam, warmerdam at pobox.com
light and sound - activate the windows | http://pobox.com/~warmerdam
and watch the world go round - Rush    | President OSGF, http://osgeo.org