[Gdal-dev] ogr find neighbours

[Didrik Pinte]

Le mercredi 10 mai 2006 à 09:01 -0500, Howard Butler a écrit :
> Didrik,
> 
> In my experience, although I don't know for sure 
> if really true, testing for Overlaps/Disjoint is 
> much faster than doing Touches, which probably 
> has to walk a lot of vertices and may take on 
> some precision model stuff to do comparisons.  If 
> the two geometries are Disjoint, or not Overlaps, 
> then they can't Touch.  Only run the Touch test 
> on those pairs that really have a chance to do so.
> 
> I could be totally wrong here though, and GEOS 
> may already be doing this optimization for us (at 
> least testing the bounding boxes to throw out 
> obvious cases), but I haven't looked at the 
> source code to know  for sure.

Hi Howard,

I've changed my tests, removed the Touches and Overlaps test with only
one Disjoint test. This works correctly in half the time (~27 seconds in
place of 56). The profiling from the old code seems to show that the
Touches and Overlaps operations where taking nearly the same time (a
little bit more for Touches).

27 seconds is still much for 11 polygons (i can provide them for tests
if needed).

> 
> Another thing I would add is if you are trying to 
> do something like a dissolve, you need to 
> bucketize the neighbors into groups so that you 
> can go along and union them together.  I have 
> some code that uses the Python Cartographic 
> Library to do a dissolve.  Maybe some of the 
> concepts of what you are doing are similar.  Let 
> me know if you are interested.

I won't be doing any dissolve operation here but i'm very interested in
you Python code doing that. 

Didrik