7

I have a table with 2000 records and with those columns OutletName, longitude, latitude, geom

I would like to find a way to find the farthest outlet between a selection of outlets

For example we have outletnames : A,B,C,D,E,F,G,H,I,J,K...

And we would like to know who is the farthest outlet from A between those outlets 'B' 'F' and 'D'

Now I am doing it with lot of queries calculating distances between all of them and comparing the distances in java, but it takes time. Is there a better way to do it?

Improve this question
1
  • 3
    This problem is efficiently solved with a farthest-point Voronoi diagram. Few GISes (if any) can compute it. But it's worth knowing that any farthest point must be a vertex of the convex hull of the point cloud. Because convex hulls typically have relatively few vertices, you can likely achieve a substantial speedup by precomputing the convex hull and limiting your search to its vertices.
    – whuber
    Commented Apr 19, 2012 at 13:30

2 Answers 2

Reset to default
6

If it is just 2000 records and only points (no complex polygons or linestrings) it shouldn't take many milliseconds to calculate.

If it would have been a few million points to check distance between you could consider using knn-distance with PostgreSQL 9.1 and PostGIS 2.0.

But I think you should do fine with something like?

SELECT b."OutletName" FROM the_table AS a, the_table AS b 
WHERE a."OutletName" = 'A' AND b."OutletName" in ('B', 'F', 'D') 
ORDER BY ST_Distance(a.geom, b.geom) desc
limit 1;

The bottleneck in this query will not be the spatial calculation since it is only three distance calculations between points, but to find the OutletName fast. Because of that you will maybe save a efw milliseconds if you put an index n the OutletName column.

edit:
From Whubers comment I guess I am misunderstanding something here, but I let it be for now.

HTH

Nicklas

Improve this answer
2
  • I may have misinterpreted the question, Nicklas: I took it to be asking to obtain, for each point in a point cloud, the identifier of the point furthest from it. With just 2000 points this can be solved with about 2 million distance calculations, which is no problem, but with tens of thousands of points or more, a better approach is needed.
    – whuber
    Commented Apr 19, 2012 at 14:52
  • 1
    @whuber, yes I see what you mean. In PostGIS then ST_MaxDistance can be used (together with ST_Collect). Or ST_LongestLine, together with ST_EndPoint to find the furthest point in a collection, linestring or polygon. Both ST_MaxDistance ans ST_Longestline uses the trick to first calculate the convex hull.
    – Nicklas Avén
    Commented Apr 19, 2012 at 17:27
3

For evaluating this problem with many more points, use a KNN-distance method, with a CROSS JOIN LATERAL to gather each point's closest point. As always, make sure you have a spatial index on the geometry column, and it's recommended to use a projected spatial reference system (not lat/long).

This is a query that returns the top 10 farthest points in my_points with 650,000 rows, taking only one minute to complete:

SELECT a.gid, b.gid, a.geom <-> b.geom AS distance
FROM my_points a
CROSS JOIN LATERAL (
  SELECT b.gid, b.geom
  FROM my_points b
  WHERE a.gid <> b.gid
  ORDER BY a.geom <-> b.geom ASC LIMIT 1
) AS b
ORDER BY a.geom <-> b.geom DESC LIMIT 10;
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.