Use MySQL spatial extensions to select points inside circle

Question

I have a table called flags that contains a column called coordinates that is full of MySQL 'points'. I need to perform a query where I get all the flags within a circle based on a latitude and longitude position with 100m radius.

From a usage point of view this is based around the user's position. For example, the mobile phone would give the user's latitude and longitude position and then pass it to this part of the API. It's then up to the API to create an invisible circle around the user with a radius of 100 metres and then return the flags that are in this circle.

It's this part of the API I'm not sure how to create as I'm unsure how to use SQL to create this invisible circle and select points only within this radius.

Is this possible? Is there a MySQL spatial function that will help me do this?

I believe the Buffer() function can do this but I can't find any documentation as to how to use it (eg example SQL). Ideally I need an answer that shows me how to use this function or the closest to it. Where I'm storing these coordinates as geospatial points I should be using a geospatial function to do what I'm asking to maximize efficiency.

Flags table:

• id
• coordinates
• name

Example row:

1 | [GEOMETRY - 25B] | Tenacy AB

For the flags table I have latitude, longitude positions and easting and northing (UTM)

The user's location is just standard latitude/longitude but I have a library that can conver this position to UTM

Loosejointed

You will want to use the Haversine function of the radius > 20Km, otherwise you can get away with using Pythagoras formulae on an equilateral rectangular projection. here's a previous stack overflow question on the former: #575191 – Solve

What version of the MySQL (or possibly the MariaDB) server are you using in this project? Does your flags table actually contain UTM coordinates? Are they all projected into the same UTM zone? – Tensile

@OllieJones Hi Ollie. The version of MySQL is 5.6.14 (can be upgraded if necessary). The flags table does contain UTM coordinates yes. The user's position however is just a latitude/longitude position but I have a class that converts latitude/longitude into northing/easting based on lat/lng/time zone. For this question, because of the converter class, you can just imagine that everything is UTM should that be necessary – Loosejointed

Are your UTM coordinates specified as North / East / Zone or just North / East? In other words, are they all in the same zone? – Tensile

They're not, no. They span across 5 different zones, 29v, 30v, 29u, 30u, 31u (the UK) – Loosejointed

aha. So we have to do distance computations using lat/long. One more question. How much accuracy is required? Is this a civil engineering project, or a "find the coffee shop" project? – Tensile

The solutions may not perform well for large datasets. If that is an issue, see mysql.rjweb.org/doc.php/find_nearest_in_mysql – Kaliningrad

Answer 1

There are no geospatial extension functions in MySQL supporting latitude / longitude distance computations. There is as of MySQL 5.7.

You're asking for proximity circles on the surface of the earth. You mention in your question that you have lat/long values for each row in your flags table, and also universal transverse Mercator (UTM) projected values in one of several different UTM zones. If I remember my UK Ordnance Survey maps correctly, UTM is useful for locating items on those maps.

It's a simple matter to compute the distance between two points in the same zone in UTM: the Cartesian distance does the trick. But, when points are in different zones, that computation doesn't work.

Accordingly, for the application described in your question, it's necessary to use the Great Circle Distance, which is computed using the haversine or another suitable formula.

MySQL, augmented with geospatial extensions, supports a way to represent various planar shapes (points, polylines, polygons, and so forth) as geometrical primitives. MySQL 5.6 implements an undocumented distance function st_distance(p1, p2). However, this function returns Cartesian distances. So it's entirely unsuitable for latitude and longitude based computations. At temperate latitudes a degree of latitude subtends almost twice as much surface distance (north-south) as a degree of longitude(east-west), because the latitude lines grow closer together nearer the poles.

So, a circular proximity formula needs to use genuine latitude and longitude.

In your application, you can find all the flags points within ten statute miles of a given latpoint,longpoint with a query like this:

 SELECT id, coordinates, name, r,
        units * DEGREES(ACOS(LEAST(1.0, COS(RADIANS(latpoint))
                  * COS(RADIANS(latitude))
                  * COS(RADIANS(longpoint) - RADIANS(longitude))
                  + SIN(RADIANS(latpoint))
                  * SIN(RADIANS(latitude))))) AS distance
   FROM flags
   JOIN (
        SELECT 42.81  AS latpoint,  -70.81 AS longpoint, 
               10.0 AS r, 69.0 AS units
        ) AS p ON (1=1)
  WHERE MbrContains(GeomFromText (
        CONCAT('LINESTRING(',
              latpoint-(r/units),' ',
              longpoint-(r /(units* COS(RADIANS(latpoint)))),
              ',', 
              latpoint+(r/units) ,' ',
              longpoint+(r /(units * COS(RADIANS(latpoint)))),
              ')')),  coordinates)

If you want to search for points within 20 km, change this line of the query

               20.0 AS r, 69.0 AS units

to this, for example

               20.0 AS r, 111.045 AS units

r is the radius in which you want to search. units are the distance units (miles, km, furlongs, whatever you want) per degree of latitude on the surface of the earth.

This query uses a bounding lat/long along with MbrContains to exclude points that are definitely too far from your starting point, then uses the great circle distance formula to generate the distances for the remaining points. An explanation of all this can be found here. If your table uses the MyISAM access method and has a spatial index, MbrContains will exploit that index to get you fast searching.

Finally, the query above selects all the points within the rectangle. To narrow that down to only the points in the circle, and order them by proximity, wrap the query up like this:

 SELECT id, coordinates, name
   FROM (
         /* the query above, paste it in here */
        ) AS d
  WHERE d.distance <= d.r
  ORDER BY d.distance ASC 

Tensile

Just for curious, st_within is it suitable for checking a lattitude and longitude is inside or not. Because as you said st_distance is not suitable for latitude and longitude based computations. – Primogenial

st_within will work if you create a bounding polygon. My example here uses simply a diagonal line and its bounding rectangle. st_within will do a bit more work for the same result as MBRContains. If you had polygonal geographic boundaries, st_within might be suitable. – Tensile

This is a great comment, Ollie, kudos for the clear, exhaustive and well written explanation. Just in case I did not understand it all: a) if you use UTM, a simple euclidean distance within the same zone works b) if you have to use the Degree (Lat/Lon) the Great Circle Distance and last part of your post comes into play. Is that correct? – Vaucluse

@sc0p, within the same UTM zone (or other projection zone) Cartesian distance works. Whether or not you use Cartesian or Great Circle (haversine) distance computations, a bounding-rectangle search helps optimize your search. A distance criterion, alone, can't exploit an index to narrow down the search for matching points. – Tensile

ST_Distance_Sphere(g1, g2[, radius]) link as of 5.7.6 – Colcothar

Warning! MbrContains doesn't properly work when LINESTRING crosses antimeridian. SELECT MbrContains(ST_GeomFromText('LINESTRING(170 60, 185 70)', 4326), ST_GeomFromText('POINT(-179 65)', 4326)) will return 0. Here point 185 70 is the way to let MySQL know that the line crosses antimeridian and what will be calculated according to this answer. If these coords will be corrected to be -175 70, then MySQL will create a long line across the globe (in the opposite direction) that doesn't cross antimeridian, so the bounding box will be almost all globe. I didn't find a solution. – Jamilla

Answer 2

UPDATE

Use ST_Distance_Sphere() to calculate distances using a lat/long

http://dev.mysql.com/doc/refman/5.7/en/spatial-convenience-functions.html#function_st-distance-sphere

Minster

Sample usage (in the end Update): mysqlserverteam.com/mysql-5-7-and-gis-an-example – Megaphone

Answer 3

This assumes the coordinates in the table are stored as a POINT() datatype in a column labeled 'point'. The function X(point) and Y(point) extract the latitude and longitude values from the point value respectively.

SET @lat = the latitude of the point
SET @lon = the longitude of the point
SET @rad = radius in Kilometers to search from the point
SET @table = name of your table

SELECT
    X(point),Y(point),*, (
      6373 * acos (
      cos ( radians( @lat ) )
      * cos( radians( X(point) ) )
      * cos( radians( Y(point) ) - radians( @lon ) )
      + sin ( radians( @lat ) )
      * sin( radians( X(point) ) )
    )
) AS distance
FROM @table
HAVING distance < @rad

If you want to do it in miles, replace the constant 6373 with 3959

For those wanting to reduce the query syntax, here's a common implementation of a user defined MySQL function for implementing a distance function based on the Haversine formulae.

CREATE FUNCTION HAVERSINE ( coord1 POINT, coord2 POINT )
RETURNS DOUBLE
DETERMINISTIC
BEGIN
    DECLARE dist DOUBLE;
    SET rlat1 = radians( X( coord1 ) );
    SET rlat2 = radians( X( coord2 ) );
    SET rlon1 = radians( Y( coord1 ) );
    SET rlon2 = radians( Y( coord2 ) );
    SET dist  = ACOS( COS( rlat1 ) * COS( rlon1 ) * COS( rlat2 ) * COS( rlon2 ) + COS( rlat1 ) * SIN( rlon1 ) * COS( rlat2 ) * SIN( rlon2 ) + SIN( rlat1 ) * SIN( rlat2 ) ) * 6372.8;
    RETURN dist;
END

Solve

not sure why someone downvoted without an explanation. All the other answers I've seen on the site assume the lat/lon are stored as decimal or float. This poster asked for a solution where they are stored as POINT datatype. – Solve

Hi Andrew, thanks for your answer. Is there not a better way to do this like the Geospatial function 'Buffer'? It's designed for this exact thing I just can't find any documentation/usage examples – Loosejointed

The buffer() function is a proposed addition to MySQL but to the best of my knowledge it has not been implemented yet. I found this reference on the online version 5.5 documentation: These functions are not implemented in MySQL. Buffer(g,d) Returns a geometry that represents all points whose distance from the geometry value g is less than or equal to a distance of d. – Solve

If you are doing this in a single local area (e.g., one city), you can use far more efficient approximations such as Euclidean geometry, bounding boxes, etc.Look at the MBRxxxx and ST_xxx functions in MySQL. – Solve

Thanks Andrew. All of the points in the circle will be close proximity so definitely within city distance. Could I ask you to update your answer using either MBR/ST functions with the extra info that the areas will be small? – Loosejointed

Seems like it would be neater to bundle that up in a distance() function (albeit one that takes advantage of the POINT data type) – Obligatory

@Obligatory I've heard about a distance function in MySQL already? Has that been implemented? – Loosejointed

I've no idea, but it seems like it would be possible to write one! – Obligatory

I've updated my answer to include a copy of the Haversine formulae as a user defined MySQL function. – Solve

Answer 4

Buffers won't help you much in MySQL < 5.6, since buffer is a polygon, and polygon operations in MySQL < 5.6 are implemented as "Minimal Bounding Rectangles" (MBR), which are pretty useless.

Since MySQL 5.6, the full non-MBR st_* operations were implemented. But the best solution for you, in case of circle, is to use undocumented function st_distance:

select *
from waypoints
where st_distance(point(@center_lon, @center_lat), coordinates) <= radius;

It was hard to find, since it's undocumented :-) But it's mentioned on this blog, whose author also filled the mentioned bugreport. There are caveats though (citing the blog):

The bad news is:

1) All functions still only use the planar system coordinates. Different SRIDs are not supported.

2) Spatial indexes (RTREE) are only supported for MyISAM tables. One can use the functions for InnoDB tables, but it will not use spatial keys.

Point 1) means that the unit of distance will be the same as the unit of coordinates (degrees in case of WGS84). If you need distance in meters, you have to use projected coordination system (e.g. UTM or similar) that has units corresponding to meters.

So, in case you don't want to go with these caveats, or in case of MySQL < 5.6, you will have to write your own custom distance function.

Insatiable

When specifying a radius of 100 the query takes forever. Is the radius measured in metres or something a lot larger? – Loosejointed

@Loosejointed in the linked blog (there are not much resources as it is undocumented) he mentions that "All functions still only use the planar system coordinates." That means that the unit of distance will be the same as the unit of coordinates (degrees in case of WGS84). If you need distance in meters, you have to use projected coordination system (e.g. UTM or similar) that has units corresponding to meters. – Insatiable

Is there any way you could try and find something that would convert this type of measurement into meters? 100 meters is a fixed value that would never change. When using radius 0.001 it seems pretty close to 100 meters but I have no way to check how close until it's converted (needs to be pretty exact) – Loosejointed

@Loosejointed that wouldn't work well because latitude and longitude degrees will have different ratio to meters depending on the position on earth. st_distance will work best on the UTM projected coordinates. – Insatiable

Even if we're talking about geodesic geometry? These measurements are only over the UK, not measuring across the world. Not sure how to change things to work better on 'UTM' coordinates – Loosejointed

@Loosejointed what CRS do you use? – Insatiable

let us continue this discussion in chat – Loosejointed

Answer 5

for the sake of completeness, as of MySQL 5.7.6. you can use the ST_Distance_Sphere function which achieves the same result:

SET @pt1 = ST_GeomFromText('POINT(12.3456 34.5678)');

SELECT * from 
(SELECT * ,(ST_Distance_Sphere(@pt1, location, 6373)) AS distance FROM mydb.Event ORDER BY distance) x WHERE x.distance <= 30;

In this case, we provide the approximate radius of the Earth in kilometers (6373) and a point (@pt1). This code will calculate the distance (in kilometers) between that point (long 12.3456, lat 34.5678) and all the points contained in the database where the distance is 30km or less.

Macaroon

Answer 6

from: https://gis.stackexchange.com/questions/31628/find-points-within-a-distance-using-mysql

SELECT
    id, (
      6371 * acos (
      cos ( radians(78.3232) )
      * cos( radians( lat ) )
      * cos( radians( lng ) - radians(65.3234) )
      + sin ( radians(78.3232) )
      * sin( radians( lat ) )
    )
) AS distance
FROM markers
HAVING distance < 30
ORDER BY distance
LIMIT 0 , 20;

(remember to replace all constants, this example is for kilometers)

Selig

Answer 7

You can use:

SELECT name, lat, lng   
FROM vw_mytable 
WHERE ST_Contains(ST_Buffer(
          ST_GeomFromText('POINT(12.3456 34.5678)'), (0.00001*1000)) , mypoint) = 1  

The expression: 0.00001*1000 inside statement above give to you a circle with 1000 Meters of diameter, it's being applied on a view here, name column is just a label to point, mypoint is the name of my point column, lat was calculated inside view with ST_X(mytable.mypoint) and lng with ST_Y(mytable.mypoint) and they simply show me the literal values of lat and lng.

It will give to you all coordinates that belongs to circle.

Glorification

Answer 8

Hope my version helps

SELECT 
    *
FROM 
    `locator`
WHERE
    SQRT(POW(X(`center`) - 49.843317 , 2) + POW(Y(`center`) - 24.026642, 2)) * 100 < `radius`

details here http://dexxtr.com/post/83498801191/how-to-determine-point-inside-circle-using-mysql

Azucenaazure