Finding the Nearest Neighbor

Summary

This post may describe functionality for an old version of CARTO. Find out about the latest and cloud-native version here.
Finding the Nearest Neighbor
Won't you be my Neighbor?

Apps with maps on phones and on the web are frequently built around "nearest neighbor" queries sifting through a database to find the records that are contextually appropriate given an input location.

  • Find me all the records that fit in the map!
  • Find me all the records within 1km of the user location!
  • Find me the 10 records nearest to the user!

For "records" replace with "restaurants" or "gas stations" or "future close friends" depending on the application you are building.

All of these questions can be answered with SQL and with the CartoDB SQL API it's easy to send them to the database to get back the data your app needs!

Find Things Within a Box

The map window in an app defines a box and it's not uncommon to just want a list of things that are visible right now. ##_INIT_REPLACE_ME_PRE_##

SELECT *
FROM mytable
WHERE ST_Intersects(
    ST_MakeEnvelope(%minlon  %minlat  %maxlon  %maxlat  4326) 
    the_geom
);
##_END_REPLACE_ME_PRE_## 
The query just builds a query envelope and then finds all the records that intersect it.

Find Things Within a Radius

Frequently an app will use a query point either the center of a view or the location of a zip code or other named place to center a radius query. ##_INIT_REPLACE_ME_PRE_##

SELECT *
FROM mytable
WHERE ST_DWithin(
    ST_Transform(CDB_LatLng(%lat  %lon)  3857) 
    the_geom_webmercator 
    %radius / cos(%lat * pi()/180)
);
##_END_REPLACE_ME_PRE_## 
In order to do a distance calculation  this query uses the the_geom_webmercator column  which (surprise!) is in the Mercator projection (aka "EPSG:3857"). Because Mercator distorts features at the poles by stretching them larger  we have to scale up the distance the further north the query is  hence the trigonometry applied to the radius parameter.

Find the Nearest Things

Like the previous example a query point can seed a list of "things nearest to the point". Unlike the radius query we don't care how far away (or near) the results are we just want the closest ones. ##_INIT_REPLACE_ME_PRE_##

SELECT *
FROM mytable
ORDER BY the_geom_webmercator
  <-> ST_Transform(CDB_LatLng(%lat  %lon)  3857)
LIMIT %numrecords
##_END_REPLACE_ME_PRE_## 
The query returns the records in order of closest to furthest  stopping when the LIMIT number of records is reached. If you omit the LIMIT you'll get the whole table back  in sorted order (ouch!).