[Gdal-dev] Fast Polygon intersections

[Chris Padwick]

Hi Frank, 

Thanks for the suggestion.  Using GEOS directly seems to go much faster.

Regards,

Chris

-----Original Message-----
From: Frank Warmerdam [mailto:fwarmerdam at gmail.com] 
Sent: Wednesday, July 20, 2005 1:44 PM
To: Chris Padwick
Cc: gdal-dev at lists.maptools.org
Subject: Re: [Gdal-dev] Fast Polygon intersections

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