Query points within a given radius in MySQL

Question

I have created the following MySQL table to store latitude/longitude coordinates along with a name for each point:

CREATE TABLE `points` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(128) NOT NULL,
  `location` point NOT NULL,
  PRIMARY KEY (`id`),
  SPATIAL KEY `location` (`location`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1;

I am trying to query:

• all points within an n mile radius of a given point;
• the distance of each returned point from the given point

All of the examples I have found refer to using a minimum bounding rectangle (MBR) rather than a radius. The table contains approximately 1 million points, so this need needs to be as efficient as possible.

Ought

I eventually found the solution at movable-type.co.uk/scripts/latlong-db.html. – Ought

Answer 1

For MySQL 5.7+

Given we have the following simple table,

create table example (
  id bigint not null auto_increment primary key,
  lnglat point not null
);

create spatial index example_lnglat 
    on example (lnglat);

With the following simple data,

insert into example (lnglat) 
values
(point(-2.990435, 53.409246)),
(point(-2.990037, 53.409471)),
(point(-2.989736, 53.409676)),
(point(-2.989554, 53.409797)),
(point(-2.989350, 53.409906)),
(point(-2.989178, 53.410085)),
(point(-2.988739, 53.410309)),
(point(-2.985874, 53.412656)),
(point(-2.758019, 53.635928));

You would get the points within a given range of another point (note: we have to search inside a polygon) with the following combination of st functions:

set @px = -2.990497;
set @py = 53.410943;
set @range = 150; -- meters
set @rangeKm = @range / 1000;

set @search_area = st_makeEnvelope (
  point((@px + @rangeKm / 111), (@py + @rangeKm / 111)),
  point((@px - @rangeKm / 111), (@py - @rangeKm / 111))
);

select id, 
       st_x(lnglat) lng, 
       st_y(lnglat) lat,
       st_distance_sphere(point(@px, @py), lnglat) as distance
  from example
 where st_contains(@search_area, lnglat);

You should see something like this as a result:

3   -2.989736   53.409676   149.64084252776277
4   -2.989554   53.409797   141.93232714661812
5   -2.98935    53.409906   138.11516275402533
6   -2.989178   53.410085   129.40289289527473

For reference on distance, if we remove the constraint the result for the test point looks like this:

1   -2.990435   53.409246   188.7421181457556
2   -2.990037   53.409471   166.49406509160158
3   -2.989736   53.409676   149.64084252776277
4   -2.989554   53.409797   141.93232714661812
5   -2.98935    53.409906   138.11516275402533
6   -2.989178   53.410085   129.40289289527473
7   -2.988739   53.410309   136.1875540498202
8   -2.985874   53.412656   360.78532732013963
9   -2.758019   53.635928   29360.27797292756

---

Note 1: the field is called lnglat since that's the correct order if you think of points as (x, y) and is also the order most functions (like point) accept the parameter

Note 2: you can't actually take advantage of spatial indexes if you were to use circles; also note that the point field can be set to accept null but spatial indexes can't index it if it's nullable (all fields in the index are required to be non-null).

Note 3: st_buffer is considered (by the documentation) to be bad for this use case

Note 4: the functions above (in particular st_distance_sphere) are documented as fast but not necessarily super accurate; if your data is super sensitive to that add a bit of wiggle room to the search and do some fine tuning to the result set

Jeconiah

Perhaps I'm misunderstanding, but by using st_contains isn't this still going to be doing calculations within a cartesian plane? Not spherical earth as is desired? – Matelot

Hi, I am using your code above, I have one question, what does @rangeKm / 111 mean? What is the 111 for? – Postiche

@BenOsborne There are ~111km per 1 latitude degree. But that's not precise and I wouldn't do it that way. The value changes from equator to poles. So if you search within a very large radius like 2000km the results would be very inaccurate. – Hernadez

Answer 2

Radius is not efficiently indexable. You should use the bounding rectangle to quickly get the points you are probably looking for, and then filter points outside of the radius.

Lovable

Thanks for you answer. Is the radius index limitation just a problem in MySQL? I'm wondering whether PostgreSQL might be more workable? How would I eliminate points from the bounding rectangle that don't lie within the radius? – Ought

No, that's a general problem. PostgreSQL does make it easier for you, because you can explicitly ask whether the point is contained in a circle and this would use the index as well as it can, but I believe it would also use only a rectangular search first. I can't see any MySQL function to do that, but you can simple calculate the distance between the center and the point. – Ebro

Answer 3

I did that for one point inside the circle with radius

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

Cassareep