# [postgis-users] point-in-poly query

Jeff Lounsbury jeffloun at refractions.net
Wed Jan 18 09:53:40 PST 2006

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

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

```