Fastest Way to Find Distance Between Two Lat/Long Points

I needed to solve similar problem (filtering rows by distance from single point) and by combining original question with answers and comments, I came up with solution which perfectly works for me on both MySQL 5.6 and 5.7. 

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance

coordinates is field with type POINT and has SPATIAL index
6371 is for calculating distance in kilometres
56.946285 is latitude for central point
24.105078 is longitude for central point
15 is maximum distance in kilometers

In my tests, MySQL uses SPATIAL index on coordinates field to quickly select all rows which are within rectangle and then calculates actual distance for all filtered places to exclude places from rectangles corners and leave only places inside circle.

This is visualisation of my result:

map

Gray stars visualise all points on map, yellow stars are ones returned by MySQL query. Gray stars inside corners of rectangle (but outside circle) were selected by MBRContains() and then deselected by HAVING clause.


Not a MySql specific answer, but it'll improve the performance of your sql statement.

What you're effectively doing is calculating the distance to every point in the table, to see if it's within 10 units of a given point.

What you can do before you run this sql, is create four points that draw a box 20 units on a side, with your point in the center i.e.. (x1,y1 ) . . . (x4, y4), where (x1,y1) is (givenlong + 10 units, givenLat + 10units) . . . (givenLong - 10units, givenLat -10 units). Actually, you only need two points, top left and bottom right call them (X1, Y1) and (X2, Y2)

Now your SQL statement use these points to exclude rows that definitely are more than 10u from your given point, it can use indexes on the latitudes & longitudes, so will be orders of magnitude faster than what you currently have.

e.g.

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

The box approach can return false positives (you can pick up points in the corners of the box that are > 10u from the given point), so you still need to calculate the distance of each point. However this again will be much faster because you have drastically limited the number of points to test to the points within the box.

I call this technique "Thinking inside the box" :)

EDIT: Can this be put into one SQL statement?

I have no idea what mySql or Php is capable of, sorry. I don't know where the best place is to build the four points, or how they could be passed to a mySql query in Php. However, once you have the four points, there's nothing stopping you combining your own SQL statement with mine.

select name, 
       ( 3959 * acos( cos( radians(42.290763) ) 
              * cos( radians( locations.lat ) ) 
              * cos( radians( locations.lng ) - radians(-71.35368) ) 
              + sin( radians(42.290763) ) 
              * sin( radians( locations.lat ) ) ) ) AS distance 
from locations 
where active = 1 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;

I know with MS SQL I can build a SQL statement that declares four floats (X1, Y1, X2, Y2) and calculates them before the "main" select statement, like I said, I've no idea if this can be done with MySql. However I'd still be inclined to build the four points in C# and pass them as parameters to the SQL query.

Sorry I can't be more help, if anyone can answer the MySQL & Php specific portions of this, feel free to edit this answer to do so.


  • Create your points using Point values of Geometry data types in MyISAM table. As of Mysql 5.7.5, InnoDB tables now also support SPATIAL indices.

  • Create a SPATIAL index on these points

  • Use MBRContains() to find the values:

      SELECT  *
  FROM    table
  WHERE   MBRContains(LineFromText(CONCAT(
          '('
          , @lon + 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @lat + 10 / 111.1
          , ','
          , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @lat - 10 / 111.1 
          , ')' )
          ,mypoint)

, or, in MySQL 5.1 and above:

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

This will select all points approximately within the box (@lat +/- 10 km, @lon +/- 10km).

This actually is not a box, but a spherical rectangle: latitude and longitude bound segment of the sphere. This may differ from a plain rectangle on the Franz Joseph Land, but quite close to it on most inhabited places.

  • Apply additional filtering to select everything inside the circle (not the square)

  • Possibly apply additional fine filtering to account for the big circle distance (for large distances)

Tags:

Mysql

Gis

Location

Recent Posts