[postgis-users] Shortest Distance from Every Point

[Obe, Regina]

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 at postgis.refractions.net
[mailto:postgis-users-bounces at postgis.refractions.net] 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 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 



-----------------------------------------
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20071105/c1ac13a2/attachment.html>