[postgis-users] point-in-poly query

[strk at refractions.net]

On Wed, Jan 18, 2006 at 09:53:40AM -0800, Jeff Lounsbury wrote:
> Granted I wasn't around for those previous discussions, and my 
> computation geometry courses are quite a few years behind me, but:
> 
> I find it hard to believe that one could determine the distance to a 
> shape was = 0 without using a point-in-polygon algorithm (or at least 
> SOME O(n) algorithm at the least) to do it. Therefore I can't see how it 
> would be faster to do a distance() rather than within(), although 
> obviously a real life test would give you a definitive answer fairly 
> quickly.

GEOS doesn't use point-in-polygon algorithm for within().
Rather, it computes full intersection matrix and checks
for the "within" case.
This includes location detection for every graph component.
Graph build and conversion are contribute in some overhead.

We should really add a point-in-polygon short-circuit
either in GEOS or PostGIS. I'd go for GEOS to avoid having
to add the short-circuit in all topology lib wrappers
(GEOS, GEOS-CAPI, JTS).

--strk;

> Thinking out loud, it would be really nice to have algorithm complexity 
> beside each function in the docs eh? ex: within() [O(n)], that way 
> people could more easily determine which methods would be fastest. I 
> might have just assigned some work for myself... doh!
> 
> Cheers,
> -Jeff
> 
> Stephen Woodbridge wrote:
> >Arnaud Lesauvage wrote:
> >
> >>John.C.Cartwright at noaa.gov a écrit :
> >>
> >>>Hello,
> >>>
> >>>given a table of country polygons and a table of city points, I'm trying
> >>>to find all the cities that fall w/in a given country.  The query listed
> >>>below runs slowly and also produces incorrect results.  Can someone
> >>>correct what I'm doing wrong?
> >>>
> >>>select cities.city_name,cities.cntry_name
> >>>from cities p, country a where p.shape && a.shape and   
> >>>intersects(p.shape,a.shape) and   a.gmi_cntry = 'USA';   
> >>
> >>
> >>
> >>I think your query is OK (apart from what Michael pointed out).
> >>If your cities are points, I'd rather use "within" instead of 
> >>"intersects" though, but I don't know whether it will run faster or not.
> >
> >
> >I thought distance(p.shape,a.shape)=0.0 was fastest based on prior 
> >discussions on this list.
> >
> >-Steve
> >_______________________________________________
> >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

-- 

 /"\    ASCII Ribbon Campaign
 \ /    Respect for low technology.
  X     Keep e-mail messages readable by any computer system.
 / \    Keep it ASCII.