[postgis-users] Shortest Distance from Every Point

[Paul Ramsey]

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 at postgis.refractions.net
>> 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 at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users