Получить ближайшие точки точки из БД

Question

Я использую базу данных MariaDB, где я храню огромное количество точек (широты и долготы) с использованием типа Hibernate jts.geom.Point. В базе данных хранится тип geometry.

Я хочу знать, как я могу получить 10 ближайших точек с учетом определенной точки. Как я мог сделать это с помощью запроса SQL? Или, может быть, запрос и почтовый индекс в бэкэнде.

Спасибо!

Answer 1

Вот 5 алгоритмов разной сложности и производительности. Плюс код Гаверсина.

http://mysql.rjweb.org/doc.php/find_nearest_in_mysql

Answer 2

Например, вы можете сделать:

create table t (loc point);

insert into t (loc) values
  (POINT(10, 0)), 
  (POINT(15, 20)),
  (POINT(50, 50));

Затем вы можете найти две ближайшие точки к (49, 49):

select *,
  st_distance_sphere(loc, POINT(49, 49)) as dist
from t
order by st_distance_sphere(loc, POINT(49, 49)) 
limit 2 -- only the closest two points

Результат:

loc              dist
---------------  -----------------
{"x":50,"y":50}  132584.0664606239
{"x":15,"y":20}  4416195.256674154
    

См. Пример выполнения на DB Fiddle .

Теперь это работает, но с миллионами строк это не будет очень эффективно. Вам нужно будет выполнить предварительную фильтрацию, используя «прямоугольники» или «области», чтобы можно было использовать индекс.

EDIT для MariaDB

Синтаксис MariaDB немного отличается. См. Ниже:

select ST_AsText(t.loc) as point, 
  ST_Distance(loc, POINT(49, 49)) as dist
from t
order by ST_Distance(loc, POINT(49, 49))
limit 2;

Результат:

point         dist
------------  ------------------
POINT(50 50)  1.4142135623730951
POINT(15 20)  44.68780594300866

См. Рабочий пример на db <> fiddle .