[geos-devel] Extent-limited graph building ?

Sandro Santilli strk at keybit.net
Fri Sep 19 06:34:37 PDT 2014

On Fri, Sep 19, 2014 at 03:05:51PM +0200, Vincent Picavet wrote:
> Le vendredi 19 septembre 2014 14:46:52, Sandro Santilli a écrit :
> > Another use case: a polygon with 250k holes intersected with another
> > with the same structure. Also in this case it would be better to split
> > the polygon into multiple smaller ones, but it's a bit harder to do,
> > and requires invoking the intersection again (for the split).
> As far as I know, this is the kind of use cases Korotkov & al are trying to 
> get fast in PostgreSQL (and PostGIS) with their VODKA indexing concept, a kind 
> of subindexing.
> Some information here :
> http://www.pgcon.org/2014/schedule/events/696.en.html

Interesting pointer, thanks!
Anyway, this is outside the scope of GEOS, which would benefit from
restricting work to the one really needed for the result of intersection.

The real case at hand computes in 21 seconds with OverlayOp, while it
takes 0.7 seconds to compute by the RectangleIntersection class, which
scans off-sight holes just once to find they are outside of the area
of interest.


More information about the geos-devel mailing list