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

The case I'm looking at is a collection of 250000+ components.
Profiling, the most expensive operation is PointInRing checking,
which happens at adding the rings endpoints to the topology, I think.
REF: http://trac.osgeo.org/postgis/ticket/2933#comment:6

The rectangle-based intersection helps a lot in this case, probably
just because it skips components that do not intersect the rectangle.
A kind of "cascaded" intersection should also help there.

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