Get most left|right|top|bottom point contained in box

Question

I'm storing Points Of Interest (POI) in PostgreSQL database, and retrieve them via PHP script to Android application. To reduce internet usage I want my mobile app to know if there are any points in the neighborhood of currently displayed area.

My idea is to store bounds of the rectangle containing all points already retrieved (in other words: nearest point on the left (West) of most west already retrieved, nearest point above (North) of most north already retrieved etc.) and I will make next query when any edge of screen goes outside of this bounds.

Currently I can retrieve points which are in "single screen" (in the area covered by currently displayed map) using:

SELECT * FROM ch WHERE loc <@ (box '((".-$latSpan.", ".$lonSpan."),(".$latSpan.", ".-$lonSpan."))' + point '".$loc."')

Now I need to know four most remote points in each direction, than I will be able to retrieve next four "more remote" points.

Is there any possibility to get those points (or box) directly from PostgreSQL (maybe using some "aggregate points to box" function)?

Answer 1

You can use the distance-to operator (<->) combined with the MIN aggregate function to find the closest distance, thus reducing the problem to finding the other columns for the row with some minimal quantity. The strictly left of/right of/above/below operators (<<, >>, |>>, <<|) can be used to limit the points to one side of the box. Since two different points might have the same distance, we'll limit the result to 1 row. Assuming screen orientation, where coordinates increase down and to the right (rather than map orientation, which increases North and East), we get:

-- Above, or North
SELECT * FROM ch WHERE loc <<| screen AND (loc <-> screen) = (
  SELECT MIN(loc <-> screen) AS mindist FROM ch
    WHERE loc <<| screen
) LIMIT 1

-- Right, or East
SELECT * FROM ch WHERE loc >> screen AND (loc <-> screen) = (
  SELECT MIN(loc <-> screen) AS mindist FROM ch 
    WHERE loc >> screen
) LIMIT 1

-- Below, or South
SELECT * FROM ch WHERE loc |>> screen AND (loc <-> screen) = (
  SELECT MIN(loc <-> screen) AS mindist FROM ch
    WHERE loc |>> screen
) LIMIT 1

-- Left, or West
SELECT * FROM ch WHERE loc << screen AND (loc <-> screen) = (
  SELECT MIN(loc <-> screen) AS mindist FROM ch 
    WHERE loc << screen
) LIMIT 1

Note that the closest point in a horizontal direction might also be the closest point in a vertical direction; that is, the union of the above four statements might be less than four rows.

We can get the four closest points with:

SELECT *, (loc <-> screen) AS distance FROM ch 
  WHERE NOT loc <@ screen
  ORDER BY distance
  LIMIT 4

However, note that some of the closest points might be in the same direction as each other.

We can get the closest point overall with

SELECT *, (loc <-> screen) AS distance FROM ch 
  WHERE distance = (
      SELECT MIN(loc <-> screen) AS mindist FROM ch
  )
  LIMIT 1

or

SELECT *, (loc <-> screen) AS distance FROM ch 
  WHERE NOT loc <@ screen
  ORDER BY distance
  LIMIT 1

When calculating the minimum (or maximum) of a column, the first would be preferable, since the DBMS could use an index on the column (if any) and not need to scan the table. Since the distance is a calculated value, a table scan is always needed and the queries will have similar performance. A query analysis might turn up some other reason to prefer a statement, so you should do so before picking an approach.