Finding closest point to a given point

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Finding closest point to a given point

Adrian Holovaty
Hello,

I have a point (longitude/latitude), and I want to find the closest point to
it, from my DB table, that matches given criteria. I tried this (assuming the
point is (-80, 45)) --

SELECT the_point
FROM foo
WHERE some_criteria='t'
ORDER BY distance(the_point, GeomFromText('POINT(-80 45)', -1))
LIMIT 1;

...but it's slow, because the database has to calculate the distance to each
other point in the table and cannot use the index, as pointed out in the
docs: http://postgis.refractions.net/docs/ch04.html#id3213331

Following those docs, I added a bounding box to reduce the number of distance
calculations required.

SELECT the_point
FROM foo
WHERE some_criteria='t'
AND the_point && 'BOX3D(-180 -55, 20 145)'::box3d
ORDER BY distance(the_point, GeomFromText('POINT(-80 45)', -1))
LIMIT 1;

It's faster, but it's still slow because the table has 20,000+ records.

Note that the point (-80 45) is variable. I can't just create an index on a
custom function that calculates the distance() to that point.

Is there a more efficient way to do this, which doesn't involve putting
distance() in the ORDER BY clause?

This seems like a FAQ, but I can't find any good solutions in the list
archives, or on Google. Thanks in advance!

Adrian
_______________________________________________
postgis-users mailing list
[hidden email]
http://postgis.refractions.net/mailman/listinfo/postgis-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding closest point to a given point

strk
You can try using a bounding box being an extension of
your input point bbox and growing until it contains
at least another one. Then use distance() on the reduced
set.

With a good amount of fuzzyness you might get a speedup.
Checkout expand and estimated_extent.

--strk;

On Sat, Jun 04, 2005 at 07:31:29PM -0500, Adrian Holovaty wrote:

> Hello,
>
> I have a point (longitude/latitude), and I want to find the closest point to
> it, from my DB table, that matches given criteria. I tried this (assuming the
> point is (-80, 45)) --
>
> SELECT the_point
> FROM foo
> WHERE some_criteria='t'
> ORDER BY distance(the_point, GeomFromText('POINT(-80 45)', -1))
> LIMIT 1;
>
> ...but it's slow, because the database has to calculate the distance to each
> other point in the table and cannot use the index, as pointed out in the
> docs: http://postgis.refractions.net/docs/ch04.html#id3213331
>
> Following those docs, I added a bounding box to reduce the number of distance
> calculations required.
>
> SELECT the_point
> FROM foo
> WHERE some_criteria='t'
> AND the_point && 'BOX3D(-180 -55, 20 145)'::box3d
> ORDER BY distance(the_point, GeomFromText('POINT(-80 45)', -1))
> LIMIT 1;
>
> It's faster, but it's still slow because the table has 20,000+ records.
>
> Note that the point (-80 45) is variable. I can't just create an index on a
> custom function that calculates the distance() to that point.
>
> Is there a more efficient way to do this, which doesn't involve putting
> distance() in the ORDER BY clause?
>
> This seems like a FAQ, but I can't find any good solutions in the list
> archives, or on Google. Thanks in advance!
>
> Adrian
> _______________________________________________
> postgis-users mailing list
> [hidden email]
> http://postgis.refractions.net/mailman/listinfo/postgis-users
_______________________________________________
postgis-users mailing list
[hidden email]
http://postgis.refractions.net/mailman/listinfo/postgis-users
Loading...