Order results by proximity (with coordinates & radius)

Question

Given a database of 4 circles, where each circle has a radius and a geolocated centre:

id | radius | latitude | longitude
---+--------+----------+----------
 1 |      3 |    40.71 |    100.23
 2 |     10 |    50.13 |    100.23
 3 |     12 |    39.92 |    100.23
 4 |      4 |    80.99 |    100.23

Note: the longitude is the same for each circle, in order to keep things simple.

Assuming that we are on the circle 2, I would like to find every circle nearby, according to the latitude/longitude coordinates and the radius of each circle.

For example, according to the latitude/longitude coordinates, we have this order:

1. circle 1 (because of proximity: 9.42 <- 50.13 - 40.71)
2. circle 3 (because of proximity: 10.21 <- 50.13 - 39.92)
3. circle 4 (because of proximity: 30.86 <- 80.99 - 50.13)

But according to the latitude/longitude coordinates and the radius of each circle, we should have:

1. circle 3 (because of proximity: 1.79 <- 12 - 10.21)
2. circle 1 (because of proximity: 6.42 <- 9.42 - 3)
3. circle 4 (because of proximity: 26.86 <- 30.86 - 4)

Is there a simple way to do so in SQL?

Answer 1

The cube and earthdistance extensions provided in postgresql's contrib can handle doing this, to produce at least approximate answers. Specifically, they assume the Earth is a simple sphere, which makes the math a lot easier.

With those extensions you can produce the distance between circle 2 and the others like this:

select circle.id,
       earth_distance(ll_to_earth(circle.latitude, circle.longitude),
                      ll_to_earth(x.latitude, x.longitude))
 from circle,
      circle x
 where x.id = 2 and circle.id <> x.id
 order by 2;

Correcting for the circle radius should just involve subtracting x.radius and circle.radius from the distance above, although you need to think about what units the radius is in. By default, earth_distance will calculate a value in metres.

Now, making the query do something other than scan the entire list of circles and calculate the distance for each one, then sort and limit them, that's much more challenging. There are a couple of approaches:

• using cube's ability to be indexed with gist, so you can create indices to search within certain boxes around any circle's centre, and hence cut down the list of circles to consider.
• precalculate the distance between each circle and all the others any time a circle is edited, using triggers to maintain this calculation in a separate table.

The second options basically starts with:

create table circle_distance as
select a.id as a_id, b.id as b_id,
 earth_distance(ll_to_earth(a.latitude, a.longitude),
                ll_to_earth(b.latitude, b.longitude))
 from circle a, circle b
 where a.id <> b.id;
alter table circle_distance add unique(a_id, b_id);
create index on circle_distance(a_id, earth_distance);

Then some rather tedious functions to delete/insert relevant rows in circle_distance, called by triggers on circle. This means you can do:

select b_id from earth_distance where a_id = $circle_id order by earth_distance limit $n

This query will be able to use that index on (a_id,earth_distance) to do a quick scan.