[Gdal-dev] Fast Polygon intersections

[Frank Warmerdam]

On 7/20/05, Chris Padwick <cpadwick at digitalglobe.com> wrote:
>  
>  
> 
> Greetings, 
> 
>   
> 
> I have a collection of 60 polygons and I'm using OGR to compare each polygon
> to every other polygon and test whether one is inside the other.  I'm using
> the OGRGeometry::Within() method to test them.  I've noticed that this test
> is really slow, taking many seconds to compare one polygon against 59 other
> polygons.  Is there another method I might use to speed up this test or
> another approach I could take all together? 

Chris,

You might want to try doing an extents comparison before doing the hard
test.   

But internally each request will convert the two geometries into GEOS
geometries, and then do the GEOS comparison operation.  You can likely
achieve much better performance by using GEOS directly, avoiding alot
of reconversion work at least.  You might also find that there are ways to
invoke GEOS that build and preserve the spatial index for a given polygon
over many comparisons.  I haven't tried this but for somewhat similar operations
I believe Safe Software has gotten big performance improvements. 

I would add that currently OGR converts to GEOS objects via WKT format, and
this may be a poor choice from a performance point of view.  I may well 
reimplement the conversion functions at some point. 

Even if you use GEOS directly, if you are reading your polygons with OGR
you may still find it helpful to OGRGeometry::exportToGEOS() method (with
the above caveats). 

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    | Geospatial Programmer for Rent