« Return to Thread: Shortest Distance from Every Point

RE: Shortest Distance from Every Point

by Regina Obe :: Rate this Message:

Matt,

The expand function creates a bbox that expands out mmd units. So the EXPAND && basically limits your search to only those cities that fall within the expand box and since && is an indexable operator, the search is indexable. The only issue with the EXPAND is that you have to guess at an expand box that will cover all your cities (e.g. guarantee that no near result would fall outside your EXPAND guess) and yet limit the size of your expand box to something that doesn't trap too many fish so to speak. the more fish you trap, the more checks your distance function has to do.

One way to guess at an expand is to do the following query (start fairly small) and keep on increasing the size of your expand until you get no results. The exception query I think runs fairly fast since it doesn't do the costly distance check.

    SELECT
    c1.city_name
FROM
     city c1
LEFT JOIN
     city c2
     ON (
         c1.city_name <> c2.city_name AND EXPAND(c1.the_geom, 10000) && c2.the_geom
     )
WHERE c2.city_name IS NULL

You know I completely forgot about using DISTINCT ON to do more than one neighbor search for a set of records at a time. I guess I don't use that much. So I second Paul's comment "very nice query".

Hope that helps,

Regina

From: postgis-users-bounces@... [mailto:postgis-users-bounces@...] On Behalf Of Matthew Pulis
Sent: Sunday, November 04, 2007 7:21 PM
To: PostGIS Users Discussion
Subject: Re: [postgis-users] Shortest Distance from Every Point

Can you please explain further why u used the EXPAND? Didn't much get what is its use? And is mmd a thing which has to do with PostGis ?

On 11/4/07, Paul Ramsey <pramsey@...> wrote:

Well, you have to build the cartesian product of every city
combination and then measure every distance in that virtual table, so
it's not going to scale well at all as the input table gets bigger.

However, if you know the "maximum minimum distance" (?mmd?) you can
add a spatial constraint that should at least keep the calculations
in the O(n*log(n)) range... (you'll need a spatial index on the table
for best effect as the table gets larger)

SELECT DISTINCT ON (c1)
     c1.city_name AS "c1",
     c2.city_name AS "c2",
     distance(c1.the_geom, c2.the_geom),
     makeline(c1.the_geom, c2.the_geom)
FROM
     city c1
JOIN
     city c2
     ON (
         c1.city_name <> c2.city_name AND
         c1.the_geom && ST_Expand(c2.the_geom, ?mmd?)
     )
ORDER BY c1, distance ASC
;

Paul

PS - Nice query, BTW.

On 4-Nov-07, at 9:15 AM, Yancho wrote:

>
> Just wanted to say that I managed to write this Query :
>
> SELECT DISTINCT ON (c1)
>     c1.city_name AS "c1",
>     c2.city_name AS "c2",
>     distance( c1.the_geom, c2.the_geom),
>     makeline(c1.the_geom, c2.the_geom)
> FROM
>     city c1
> JOIN
>     city c2
>     ON (
>         c1.city_name <> c2.city_name
>     )
> ORDER BY c1, distance ASC
> ;
>
> It works perfectly, however how much do you think it can scale ? On
> 16 rows
> it didnt take long, however or 28,000 rows? Will it use the O(n^2)
> scalability?
>
> Thanks
>
>
> Yancho wrote:
>>
>> Hi,
>>
>> I am trying to make a query so it parses through all the 16 cities
>> i have
>> in
>> a table called city, and for each city, picks the nearest city,
>> and gives
>> me
>> the distance between both cities.
>>
>> This is the query I made :
>>
>> select
>> c.city_name, astext(c.the_geom), distance(c.the_geom, d.the_geom) AS
>> Distance, d.city_name, astext(d.the_geom)
>> from city c, city d
>> where
>> c.city_name = (
>> select c.city_name order by c.city_name ASC
>> )
>> and
>> d.city_name = (
>> select d.city_name order by d.city_name DESC
>> )
>> group by c.city_name
>> order by Distance DESC
>> LIMIT 1;
>>
>> But I am getting this error : ERROR: column "c.the_geom" must
>> appear in
>> the
>> GROUP BY clause or be used in an aggregate function
>>
>> I am seeing no reason why I should add c.the_geom, anyone can
>> enlighten me
>> more on why I should group by the_geom and after all if it does make
>> sense?
>>
>> Thanks
>>
>> --
>> Matthew Pulis
>> www.solutions-lab.net // www.mepa-clan.info
>>
>> _______________________________________________
>> postgis-users mailing list
>> postgis-users@...
>> http://postgis.refractions.net/mailman/listinfo/postgis-users
>>
>>
>
> --
> View this message in context: http://www.nabble.com/Shortest-
> Distance-from-Every-Point-tf4743229.html#a13575499
> Sent from the PostGIS - User mailing list archive at Nabble.com.
>
> _______________________________________________
> postgis-users mailing list
> postgis-users@...
> http://postgis.refractions.net/mailman/listinfo/postgis-users

_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users

--
Matthew Pulis
www.solutions-lab.net // www.mepa-clan.info

The substance of this message, including any attachments, may be confidential, legally privileged and/or exempt from disclosure pursuant to Massachusetts law. It is intended solely for the addressee. If you received this in error, please contact the sender and delete the material from any computer.

_______________________________________________
postgis-users mailing list
postgis-users@...
http://postgis.refractions.net/mailman/listinfo/postgis-users

« Return to Thread: Shortest Distance from Every Point