[postgis-users] performance of intersects(a,b)

[Willy-Bas Loos]

yes, of course. I use this example just to illustrate the case.
What i really mean is: as soon as one of the veritices has a "hit",
Intersects should return true and exit, no need to evaluate the rest (and
Disjoint should return false).

As i come to think of how this might work: the one whole polygon should be
evaluated against each veritice of the other. I guess that this means that
the number of vertices that have to be parsed is equal to N(a) x N(b). But
once you've detected that the first veritice in "a" intersects with polygon
"b", youre done (or should be).
I'm not sure if GEOS works this way (compare all 10000 vertices with all the
other 10000 verices), but the difference in performance between the previous
query and this next one, kind of suggests that is does. (added
pointonsurface(a)).

select 'yes' as foo
 from table1 a, table1 b
 where a.gid=4
 and b.gid=4
 and intersects(pointonsurface(a.the_geom), b.the_geom);

Maybe i should check the source code, even though i'm not a C programmer.
Sry, my time is limited.

WBL


On Feb 19, 2008 1:54 AM, Paul Ramsey <pramsey at cleverelephant.ca> wrote:

> Right, this:
>
>  select 'yes' as foo
>  from table1 a, table1 b
>  where a.gid=4
>  and b.gid=4
>  and st_intersects(a.the_geom, b.the_geom)
>
> seems likely to a LOT less common than
>
>  select 'yes' as foo
>  from table1 a, table1 b
>  where a.gid=4
>  and st_intersects(a.the_geom, b.the_geom)
>
> and the latter gets far less benefit from the a.getpoint(0) =
> b.getpoint(0) test, though the test would still be run on every
> candidate.  I'm not sure where the cost/benefit inflection point is,
> but I know identity is a pretty rare case.
>
> P.
>
> On 2/18/08, Martin Davis <mbdavis at refractions.net> wrote:
> > There's some new code on the way in GEOS and PostGIS which will improve
> > the performance of this case.  Bu it won't be anywhere near as fast as
> > your proposed check for an identical start point.
> >
> > The "identical start point" check is great for the particular case of
> > comparing identical polygons.  But it does nothing for the general
> > case.  The question is:  is the identical compare case common enough
> > that it's worth adding in this check for all cases?
> >
> > Willy-Bas Loos wrote:
> > > Hi,
> > >
> > > I´ve noticed that intersect(a,b) is slow when i compare a (nice and
> > > large) geometry with itself.
> > > so the syntax is:
> > >
> > > select 'yes' as foo
> > > from table1 a, table1 b
> > > where a.gid=4
> > > and b.gid=4
> > > and intersects(a.the_geom, b.the_geom)
> > >
> > > This particular polygon has about 10 000 points, and the query runs
> > > for 4 whole seconds.
> > > At the first point that is being compared, however, PostGIS should
> > > notice that it has a "positive".
> > >
> > > I´m only using postgis 1.0, so this migt have been changed allready.
> > > Has it?
> > >
> > > WBL
> > >
> > >
> ------------------------------------------------------------------------
> > >
> > > _______________________________________________
> > > postgis-users mailing list
> > > postgis-users at postgis.refractions.net
> > > http://postgis.refractions.net/mailman/listinfo/postgis-users
> > >
> >
> > --
> > Martin Davis
> > Senior Technical Architect
> > Refractions Research, Inc.
> > (250) 383-3022
> >
> > _______________________________________________
> > postgis-users mailing list
> > postgis-users at postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-users
> >
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20080219/9517054e/attachment.html>