[postgis-users] Shortest Distance from Every Point

[Paul Ramsey]

The "maximum minimum distance" has nothing to do with PostGIS, it's  
just an idea: is there a distance you expect all your minimum  
distances to be smaller than?  If so, you can winnow out pairings of  
cities that will *not* yield a minimum distance.  This is what the  
ST_Expand does, it turns a point into a box, with a distance of ?mmd?  
from each side to the center.  And the && tests containment in that  
box, using the spatial index operator.

P

On 4-Nov-07, at 4:21 PM, Matthew Pulis wrote:

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