Use MySQL Spatial Extensions to Select Points Inside Circle

Use MySQL spatial extensions to select points inside circle

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 

MySQL - Find points within radius from database

I'm currently working on a project where I'm calculating distances between multiple locations. I'm using the following query for selecting object_id's which are within a given radius.

SELECT id, 
( 6371 * 
    ACOS( 
        COS( RADIANS( db_latitude ) ) * 
        COS( RADIANS( $user_latitude ) ) * 
        COS( RADIANS( $user_longitude ) - 
        RADIANS( db_longitude ) ) + 
        SIN( RADIANS( db_latitude ) ) * 
        SIN( RADIANS( $user_latitude) ) 
    ) 
) 
AS distance FROM the_table HAVING distance <= $the_radius ORDER BY distance ASC"

I can't explain the ACOS formula itself because I got it from research.

db_latitude = database latitude field
db_longitude = database longitude field
$user_latitude = browser latitude coördinate
$user_longitude = browser longitude coördinate
$the_radius = the radius that you want to search in

This is in kilometers.

MySQL Spatial Extensions: Getting records that fall with in a certain area

You want to use the 'geometry' mysql extension.
If your location is of type 'geometry' you could do such a query

SELECT *, AsWKT(location) as geomWKT
FROM myTable
WHERE Intersects(location,GeomFromText('POINT(1.9845 49.8543)'))

Some examples about the format here

Find records within Geofence (circle) using MySQL Spatial fields

Assuming you have a spatial key on location, you can do something like this:

select * from locations where 
contains(geomfromtext('polygon($bounding_rect_coords)'),location) 
and earth_distance(location,point($lat,$lon)) < $radius

The bounding rectangle coordinates should be computed using the following formulas:

$deg_to_rad = $PI/180.0
$rad_to_deg = 1.0/$deg_to_rad
$delta_y = $rad_to_deg *($radius / ($earth_radius * cos($lat*$deg_to_rad))) // the length of the parallel = EARTH_R * cos(lat)
$delta_x = $rad_to_deg * ($radius/$earth_radius)
$x1 = $lat - $delta_x
$x2 = $lat + $delta_x
$y1 = $lon - $delta_y
$y2 = $lon + $delta_y

Then the rectangle is obtained with

geomfromtext('polygon(($x1 $y1,$x2 $y1,$x2 $y2, $x1 $y2, $x1 $y1))')

This is best done in the application to offload the database server.

This rectangle is actually a spherical rectangle, thus the use of the PI constant in its computation. The idea is simple. For the given parallel, convert the search radius into degrees of longitude. That is how many degrees east and west we need to go from the target to cover our candidate points. Then compute the same for degrees of latitude - unlike longitude, this will not be coordinate-dependent as all meridians have the same length. That is how many degrees we need to go north and south.

The above computation assumes that the search radius is smaller than the length of the parallel, which will be the case in most of the United States for a reasonable search radius, but might not hold in some parts of Alaska, for example. So it would be a good idea to check for that (if delta_y > 90) and clip it accordingly. You should also check to see if you are right on the North or South pole, things break there completely. But hopefully your data does not have too many polar records.

For earth_distance() you have several options:

• Use my UDF (http://github.com/spachev/mysql_udf_bundle) (fastest, but you need to have the ability to install UDFs on your server)
• Write a MySQL store function. You can start with http://gist.github.com/aramonc/6259563 and adjust if needed (need ability to create functions).
• Just paste your distance computation above directly into the query (ugly, but requires no special setup or privileges)

Your computation itself is OK even though it is two years old - nothing revolutionary has been discovered in the last two years as far as measuring the distance between two points on the earth is concerned as far as I know.

Your original method would work as well except it will be inefficient. The addition of contains clause allows us to reduce our search to a (hopefully) relatively small set that is guaranteed to be within the search radius very quickly. Then we take each candidate and filter out the ones that did not make the cut on earth_distance().

I must add a standard disclaimer that I inserted variables into SQL that potentially might not have been sanitized. Make sure to validate the resulting SQL queries for SQL injection attacks when writing the actual production code.

---

Related Topics