[geos-devel] Extent-limited graph building ?

[Sandro Santilli]

So I completed the work adding copyPoint filtering too.
The time went from ~3 to ~2.8 seconds.

I re-enabled the optimization for DIFFERENCE as the real
problem was indeed with fixed precision model, as evidently
it could possible enlarge the "target extent" (could be easy
to determine the growing value for it, in that case).
an easy-to-determine growing value).

So, to recap, we go from ~15 seconds to ~2.8 seconds with my
specific case (polygon with ~250k holes, intersected with small
box).

Some nice debugging output:

  Copied 467 nodes out of 10711 for geom 0
  Copied 0 nodes out of 1 for geom 1
  (computeSelfNodes) Self edges reduced from 10711 to 470
  (computeSelfNodes) Self edges reduced from 1 to 1
  Self edges reduced from 10711 to 470
  Other edges reduced from 1 to 1

It looks like the majority of the time is still spent after
the last output line. Now profiling that one.

Whole testsuite still succeed, and latest code is pushed to github:
https://github.com/strk/libgeos/tree/ext-limited-graph

--strk;

On Fri, Sep 19, 2014 at 05:31:50PM +0200, Sandro Santilli wrote:
> 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  

-- 

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