5

I have 2 tables like the examples below, towns and things, and need to get a list of towns that have nearby things that are within x distance from that town record. Latitude and longitude will be used to do the distance calculation.

I've looked at some other questions and have managed to get records from things for a single specified town, but can't think how to get a list of all towns that have nearby things that are closer than x distance from them.

Being able to sort the resulting towns by number of nearby things within x distance would be a bonus.

TOWNS
+--------+----------+---------+---------+
| townId | townName | townLat | townLng |
+--------+----------+---------+---------+
|      1 | town a   |     1.5 |     1.9 |
|      2 | town b   |     1.4 |     3.8 |
|      3 | town c   |     2.3 |     2.7 |
|      4 | town d   |     3.2 |     1.6 |
|    ... | ...      |     ... |     ... |
+--------+----------+---------+---------+

THINGS
+---------+-----------+----------+----------+
| thingId | thingName | thingLat | thingLng |
+---------+-----------+----------+----------+
|       1 | thing a   | 2.1      | 3.1      |
|       2 | thing b   | 1.1      | 2.3      |
|       3 | thing c   | 3.2      | 0.2      |
|       4 | thing d   | 1.3      | 1.1      |
|     ... | ...       | ...      | ...      |
+---------+-----------+----------+----------+

Thanks in advance

user2959229
  • 1,360
  • 2
  • 11
  • 21
  • The big problem here is going to be using the Haversine formula to determine the distance between two sets of latitude/longitude pairs. Have you done any work on this yet? – Tim Biegeleisen Jul 08 '15 at 10:49
  • With that schema any solution will get very slow for more than a few thousand rows. You basically have to calculate the distance from **every** town to **every** thing. – Vatev Jul 08 '15 at 10:54
  • Not yet - I don't know where to start. I can't seem to get my head around how to apply the formula to coordinates from both tables in the single query. – user2959229 Jul 08 '15 at 10:55
  • @Vatev - any suggestions for alternatives? – user2959229 Jul 08 '15 at 10:56
  • there are few topics already regarding distance calculation in mysql http://stackoverflow.com/questions/1006654/fastest-way-to-find-distance-between-two-lat-long-points http://stackoverflow.com/questions/24370975/find-distance-between-two-points-using-latitude-and-longitude-in-mysql – ogres Jul 08 '15 at 11:04
  • If the minimum distance (`x`) is static you can add a polygon column to the `things` which would be the MBR of the circle with radius `x` and center the thing's coords. Then you can try join-ing things to cities with [MBRContains](https://dev.mysql.com/doc/refman/5.7/en/spatial-relation-functions-mysql-specific.html) (I haven't tried this). After that you can add the proper distance (harvesine formula) to the condition to remove the few rows that are within the MBR but outside of the circle. – Vatev Jul 08 '15 at 11:11

1 Answers1

2

You can do a CROSS JOIN to obtain all possible combinations of towns and things, and then calculate the Haversine distance between each town and thing. I use SELECT DISTINCT to make sure a town is only listed once in the result set.

SELECT DISTINCT TOWNS.townName FROM
TOWNS CROSS JOIN THINGS
WHERE 3959 * acos( 
  cos(radians( TOWNS.townLat ))
* cos(radians( THINGS.thingLat ))
* cos(radians( TOWNS.townLng ) - radians( THINGS.thingLng ))
+ sin(radians( TOWNS.townLat )) 
* sin(radians( THINGS.thingLat ))
) < x

The formula I used is for x in miles (the mean radius of Earth is 3959 miles).

Tim Biegeleisen
  • 502,043
  • 27
  • 286
  • 360