[geos-devel] Extent-limited graph building ?

[Sandro Santilli]

On Thu, Sep 18, 2014 at 10:41:46AM -0700, Martin Davis wrote:
> Funny, this recently occurred to me as well.
> 
> The first place I'd look for introducing BBOX limiting is in the noding
> phase.  The selfNode creation (in GeometryGraph) could just checking edges
> within the overlap bounding box.  (This would work for intersection, but
> technically not difference since then the output would not be fully noded,
> which breaks the current JTS contract).
> 
> The computeEdgeIntersections could probably be limited to a BBOX as well.
> 
> Are you seeing data situations where this approach would produce a
> significant win?

So back to this, reducing the work of computeEdgeIntersections so to
only consider edges that intersect the target extent brings down the
time of the overlay operation I'm looking at from ~15 to ~9.5 seconds.
All existing testcases still succeed (also using the first geometry's
envelope for the DIFFERENCE op) so this sounds like a safe optimization.

Extending this to self-nodes computation (and copyPoint too?) should
speed things further up.

I pushed the GEOS code of this in the "ext-limited-graph" branch in
my github fork (if anyone wants to take a look).

For comparison, the RectangleIntersection based code completes the
operation in 40ms (!!). That's really hard to beat.

--strk;

> On Thu, Sep 18, 2014 at 10:10 AM, Sandro Santilli <strk at keybit.net> wrote:
> 
> > Martin,
> > in order to speed up intersection overlay operation, would it work to
> > limit the GeometryGraph building by a bounding box ?
> >
> > The current interface of GeometryGraph does not allow it, but from the
> > point of view of the algorithm, do you think it could work ?
> > If could speed up both intersection and difference.
> >
> > Basically OverlayOp and GeometryGraph would need to take an optional
> > Envelope for limiting operations.
> >
> > What do you think ?
> >
> > --strk;
> >
> >  ()  ASCII ribbon campaign  --  Keep it simple !
> >  /\  http://strk.keybit.net/rants/ascii_mails.txt
> >