[geos-devel] Extent-limited graph building ?

[Sandro Santilli]

On Fri, Sep 19, 2014 at 05:24:12PM +0200, Sandro Santilli wrote:
> On Fri, Sep 19, 2014 at 04:45:58PM +0200, Sandro Santilli wrote:
> > 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.
> 
> It does, time is down to ~3 seconds now, despite edges selection happening
> twice (once in computeEdgeIntersections and once in computeSelfNodes).
> Time to add it to copyPoints, I guess. But then we'd better not to add
> those elements in the graph from the start, to save even more time.

One note: with computeSelfNodes skipping non-overlapping edges there's
indeed a failure in a testcase computing DIFFERENCE. As I'm looking at
speeding up clipping for now I'll just enable the optimization for
INTERSECTION and move on.

The code is still in "ext-limited-graph" branch.

--strk;

> > 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
> > > >
> 
> -- 
> 
>  ()  ASCII ribbon campaign  --  Keep it simple !
>  /\  http://strk.keybit.net/rants/ascii_mails.txt  

-- 

 ()  ASCII ribbon campaign  --  Keep it simple !
 /\  http://strk.keybit.net/rants/ascii_mails.txt