CODEWITHSUNDEEP
mysqlsqlpostgresqlgeolocationneo4j
T5i
T5i

Reputation: 1530

Order results by proximity (with coordinates & radius)

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?

Upvotes: 5

Views: 1271

Answers (4)

Jester
Jester

Reputation: 3329

I would souggest you the following:

Create 1 table for calculation of relative distances in relation to the start circle

for instance:

id | calc1  | calc2    
---+--------+----------
 1 |  9.42  |    1.97
 3 |  10.21 |    6.42
 4 |  30.86 |   62.86

Calc1 being the calculation without the radius calc2 being the calculation with radius

then create a store procedure that will first when it is run delete the table and then fill it with the correct data and then just read the result from the destination table

Intrudoction to store procedures You will allso need cursor for this

Upvotes: 0

Peter Neubauer
Peter Neubauer

Reputation: 6331

In neo4j, you can look at Neo4j Spatial, tests for the different operations at https://github.com/neo4j/spatial/blob/master/src/test/java/org/neo4j/gis/spatial/pipes/GeoPipesTest.java, amongst them proximity search, too, e.g. https://github.com/neo4j/spatial/blob/master/src/test/java/org/neo4j/gis/spatial/pipes/GeoPipesTest.java#L150

Upvotes: 0

araqnid
araqnid

Reputation: 133702

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.

Upvotes: 1

podiluska
podiluska

Reputation: 51504

I'd suggest looking at the PostGIS Geography data types and its associated functions (eg: ST_Distance)rather than reinventing the wheel

Upvotes: 0

Related Questions