[postgis] Nearest To Searching

[Paul Ramsey]

Spoken like a true computer scientist Eric! :)

Let me take a stab at the question as a practitioner of ugly solutions.
For the more usual question, "give me all things within X units of Y",
the bounding rectangle solution is to construct a query box centred on Y
with sides 2*X in length, then test the results of that query for strict
distance < X.

John's problem is harder, as you note. However, if he has some idea of
the approximate distribution characteristics of his data, he can use a
bounding box to get a subset of points which is "fairly near" to his
query location. "Select geom,distance(geom,Q) as dist from geomtable
where geom && QBox order by dist" for example. Then just take the top N
entries. The only imponderable is how large to make the QBox. As you
say, iteratively a "good guess" initialization value could be used, and
if the result set is too small for some reason, the query just repeated
with a bigger box.

Erik Brenn wrote:
> 
> Hi John,
> 
> I might be too daring to answer this one, but I'll try anyway.
> I don't think your problem of proximity between points can be solved
> efficiently with a spatial index like in PostGIS. I'm not sure about Gist
> but a spatial index normally work with the bounding rectangles of objects,
> and not on the topological interconnections(e.g. distance) between them. I
> believe your problem could be described as a bi-directional graph with
> distance between points as the edge-costs.  Graph algorithms are expensive
> and perhaps better left to be handled by specialised client GIS software
> etc.
> 
> Anyway, assuming that you can iterate a circle query in PostGIS, you could
> increase the radius until you have a count of N points from your query. The
> number of required iterations would depend on your data heuristics to set
> initial circle size and the radius-increase for each iteration.
> 
> regards,
>   erik brenn
> 
> ----- Original Message -----
> From: "John Grange" <john.grange at locavista.com>
> To: <postgis at yahoogroups.com>
> Sent: Monday, October 08, 2001 15:21
> Subject: [postgis] Nearest To Searching
> 
> > Hi,
> >
> > Is there any way to easily find the nearest n points to another point.  I
> > have tables with many many (millions) of records and I need to locate
> > nearest neighbours.
> >
> > Any ideas?
> >
> >
> > John Grange
> > BSc. (Hons) Dunelm
> > LocaVista Ltd.
> > Orchard House
> > Castle Garth
> > Kendal, Cumbria
> > LA9 7ATTel +441539 739554
> > Fax +44 1539 729995
> > Mobile +44 7876 038 058
> >

------------------------ Yahoo! Groups Sponsor ---------------------~-->
Get your FREE VeriSign guide to security solutions for your web site: encrypting transactions, securing intranets, and more!
http://us.click.yahoo.com/UnN2wB/m5_CAA/yigFAA/PhFolB/TM
---------------------------------------------------------------------~->

To unsubscribe from this group, send an email to:
postgis-unsubscribe at yahoogroups.com

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/