Алгоритм получения квадрата по координатам?

Question

[Alexey Gus]

Суть вопроса в чем , у нас есть массив точек координат(маршрут пользователя в формате Point(lat, lng)), и нужно забрать из бд сохраненные точки которые лежат недалеко от нашего маршрута (условно 100м).

в бд точки имеют поля (lat,lng, name...).

Забрать точки недалеко от одной не проблема делал так(

"SELECT
                   *,
                    (
                    6371 *
                    acos(cos(radians($lat)) *
                    cos(radians(dots.lat)) *
                    cos(radians(dots.lng) -
                    radians($lng)) +
                    sin(radians($lat)) *
                    sin(radians(dots.lat)))
                    ) AS distance,
                    FROM dots
                    HAVING distance < 0.1
                    ORDER BY distance LIMIT 0, 20

;"

)

но в стал вопрос как забрать много точек сразу одним запросом?

единственное что пришло пока что в голову , это делать выборку по квадрату

кр точки - точки нашего маршрута
зел точки - нужные из бд
прямоугольник собственно область выборки

условно как здесь. искать верхние и нижние точки , и делать выборку точек которые подходят.

только вопрос как определить углы квадрата для выборки и как написать саму выборку?
или может есть какой-то способ эффективнее и точнее ?
буду благодарен любой помощи

Answer 1

[Alexey Gus]

Сергей Соколов, короче , вроде сделал))

SET @home = ST_GeomFromText('LINESTRING(
//Список наших точек через которые идет маршрут 
53.862263 27.483486,
53.871521 27.493636,
53.875594 27.496447,
53.880938 27.500744,
53.882699 27.505121,
53.884246 27.504435,
53.891446 27.500293,
53.896630 27.497375,
53.905348 27.496302,
53.912531 27.495487,
53.918726 27.496882)');
SELECT *, ST_AsText(geo) as Coord,
    // Дистанция считается странно получается вроде правильно , но не уверен насчет точности . 
   // В оригинале в доках написано умножать ее на .001 для км и .00067... для миль
   // но у меня так не работало и показывало до объекта 0,003км хотя по факту до него 300м вот я решил 
         умножать ее на 100 (хотя хз может оно там сантиметрах считает) 
    ST_DISTANCE(@home, geo) * 100 AS dist
    FROM dots
   // дистанция от маршрута в радиусе которой нам нужны точки (в км ) 
    HAVING dist < 1
    ORDER BY dist
    LIMIT 30

и в итоге будет примерно так


вернет зеленые точки , а красные нет .

вроде так )

Comments

[Сергей Соколов]

круть! Рад, что помог.

Answer 2

[Vindicar]

Я бы обрабатывал отрезки (пары точек), и использовал формулу расстояния от точки до прямой плюс проекцию точки на прямую, чтобы понять, где точка находится - рядом с серединой отрезка или рядом с концами.

Comments

[Alexey Gus]

можешь подробнее описать как ты делал ?)

[Vindicar]

Нам нужно найти проекцию анализируемой точки (x0; y0) на отрезок (x1;y1)-(x2;y2) маршрута. Тогда мы сможем понять, лежит ли эта проекция на отрезке. Если лежит, то расстояние от точки до проекции - это расстояние от точки до отрезка. Если не лежит, то расстояние от точки до отрезка - это расстояние от точки до ближайшего конца отрезка. В целом алгоритм примерно таков:
1. Выбираешь две соседние точки из маршрута.
2. Составляешь уравнение прямой. проходящей через эти точки. Обычно оно имеет вид (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1), где две точки - (x1;y1) и (x2;y2).
Но лучше, если переведёшь его в каноническую форму вида Ax+By+C=0.
3. Из канонического уравнения можно узнать нормальный (перпендикулярный) вектор к прямой. Он будет иметь вид N = (A;B), где A и B - коэффициенты из уравнения выше.
4. У тебя получается уравнение прямой, перпендикулярной к нашему отрезку. Оно будет иметь вид (x - x0) / A = (y - y0) / B, где (x0;y0) - это точка, расстояние до которой мы хотим найти.
5. У нас два уравнения прямых. Точка пересечения (точка проекции) будет удовлетворять им обоим, так что надо решить систему.
Bx - Ay - B*x0 + A*y0 = 0
Ax + By + C=0
Система должна иметь одно решение (x;y).
6. Находишь t = (x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) Какое из двух выбрать - зависит от направления прямой. Если прямая вертикальна (x2 - x1) ~= 0, то лучше взять y, и наоборот. t покажет, где на отрезке находится проекция искомой точки.
t = [0...1] - проекция на отрезке. Расстояние от точки до отрезка - это расстояние от (x0;y0) до (x;y).
t < 0 - проекция лежит до начала отрезка. Расстояние от точки до отрезка - это расстояние от (x0;y0) до (x1;y1).
t > 1 - проекция лежит за концом отрезка. Расстояние от точки до отрезка - это расстояние от (x0;y0) до (x2;y2).

Это полное описание, думаю, алгоритм можно упростить.
Кроме того, если длина отрезка (x1;y1)-(x2;y2) мала в сравнении с максимальным допустимым расстоянием до точки (x0;y0), то можно вообще ей пренебречь, и считать расстояние от точки до любого конца отрезка.

Answer 3

[Сергей Соколов]

Не хотите использовать возможности MySQL по работе с пространственными данными? См. список функций.

Comments

[Alexey Gus]

почитал , про них ... в принципе можно , бд реструктурирую под точки, только есть вопрос ...
можно ли создать multilinestring (насколько я понял это самый подходящий формат данных) из массива точек пришедшего с фронта , и на основе их сделать подобие маршрута , и вывести точки котрые лежат от него на расстоянии условно 100м?
условно вот запрос на вывод 3х точек около 1точки что мы передали ,

SET @home = ST_GeomFromText('POINT(-118.2819136 34.0261177)');
SELECT place_name, ST_AsText(coordinates) as Coord,
    ST_DISTANCE(@home, coordinates) AS dist
    FROM geo
    ORDER BY dist
    LIMIT 3

а я хочу чтобы бд приняла массив точек и соединила их , и уже из того что получилось вурнула ближайшие точки к этой линии из таблицы ...

можно это как-то реализовать ?
если да можете пожалуйста пример кода ))
спасибо

[Сергей Соколов]

Alexey Gus, я и сам пока не пользовался этими возможностями, только пролистывал пару раз документацию. Для одной линии маршрута из набора точек, вроде, подходит LineString.
Из набора точек отфильтровать те, что ближе D от этой ломаной.
Получить кратчайшее расстояние от линии до точки:

SET @g1 = ST_GeomFromText('LINESTRING(1 1, 3 1)');
SET @g2 = ST_GeomFromText('POINT(2 2)');
SELECT ST_Distance(@g1, @g2);
--- вернёт 1