[geos-devel] Extent-limited graph building ?

[Sandro Santilli]

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.

--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