Гость
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Поиск ближайшей точки / 25 сообщений из 27, страница 1 из 2
14.05.2020, 18:01
    #39957638
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
В таблице хранятся точки проезда в формате
Код: sql
1.
2.
3.
4.
5.
CREATE TABLE ROUTES (
    ID           BIGINT NOT NULL,
    LAT     DOUBLE PRECISION,
    LON    DOUBLE PRECISION
);

Как бы мне в этой таблице найти точку, ближайшую к заданной?

Т.е. по сути нужно оптимизировать такую процедуру
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
CREATE PROCEDURE SP_FIND_NEAR(
  in_lat DOUBLE PRECISION,
  in_lon DOUBLE PRECISION
) RETURN (
  out_id BIGINT)
AS
  DECLARE VARIABLE var_min_dist DOUBLE PRECISION;
  DECLARE VARIABLE var_dist DOUBLE PRECISION;
  DECLARE VARIABLE var_id BIGINT;
BEGIN
  FOR
    SELECT
      r.id,
      sf_dist(r.lat, r.lon, :in_lat, :in_lon)
    FROM
      routes r
    INTO
      :var_id,
      :var_dist
  DO BEGIN
    IF (:var_min_dist IS NULL OR :var_dist < :var_min_dist) THEN BEGIN
      var_min_dist = :var_dist;
      out_id = :var_id;
    END
  END
END



Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км, искать координаты углов описанных вокруг этих окружностей прямоугольников, и тогда при наличии индекса (LAT, LON) можно будет довольно быстро отфильтровывать точки на принадлежность минимальному прямоугольнику. А потом уже из отфильтрованных искать ближайшую

Может что пооптимальнее будет?

С уважением, Vasilisk
...
Рейтинг: 0 / 0
14.05.2020, 18:08
    #39957642
Гаджимурадов Рустам
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Это, фактически, ты щас пытаешься спросить
как вычислить расстояние по геокординатам?

Окстись, передохни чуток. :)
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
14.05.2020, 18:11
    #39957650
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км

Обычно фильтруют по прямоугольнику разумных размеров:
Код: sql
1.
...where r.lat between :in_lat-10 and :in_lat+10...


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
14.05.2020, 18:13
    #39957652
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Гаджимурадов Рустам
Это, фактически, ты щас пытаешься спросить
как вычислить расстояние по геокординатам?
Нет. Это просто. Функция dist() уже написана в различных ипостасях.

Мне нужно найти в массиве точек координаты ближайшей точки к заданной. Причем найти быстро. А массив большой
...
Рейтинг: 0 / 0
14.05.2020, 18:15
    #39957653
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Dimitry Sibiryakov
Обычно фильтруют по прямоугольнику разумных размеров:
У меня даже есть функция, которая вычисляет координаты прямоугольников
...
Рейтинг: 0 / 0
14.05.2020, 18:28
    #39957660
ъъъъъ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_
найти в массиве точек координаты ближайшей точки к заданной. Причем найти быстро. А массив большой

При заполнении массива точек строить пространственный индекс (см. "R-дерево").
CORE-659
...
Рейтинг: 0 / 0
14.05.2020, 18:38
    #39957668
Гаджимурадов Рустам
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_> Мне нужно найти в массиве точек координаты ближайшей точки к заданной.

Order by 2 ?

_Vasilisk_> Причем найти быстро. А массив большой

Если производительность будет не устраивать - можно
будет сделать индекс по выражению или "секторирование".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
14.05.2020, 18:44
    #39957671
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_У меня даже есть функция, которая вычисляет координаты прямоугольников

Это пофиг. Цель приведённой конструкции - отфильтровать подмножество точек, используя
индекс по r.lat/r.lon, чем и уменьшить перебор.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
14.05.2020, 18:44
    #39957672
rdb_dev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_
Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км, искать координаты углов описанных вокруг этих окружностей прямоугольников, и тогда при наличии индекса (LAT, LON) можно будет довольно быстро отфильтровывать точки на принадлежность минимальному прямоугольнику. А потом уже из отфильтрованных искать ближайшую
Школьная теорема Пифагора больше не в чести?
...
Рейтинг: 0 / 0
14.05.2020, 18:48
    #39957676
ъъъъъ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
rdb_dev
_Vasilisk_
Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км, искать координаты углов описанных вокруг этих окружностей прямоугольников, и тогда при наличии индекса (LAT, LON) можно будет довольно быстро отфильтровывать точки на принадлежность минимальному прямоугольнику. А потом уже из отфильтрованных искать ближайшую
Школьная теорема Пифагора больше не в чести?

Последовательным перебором?
...
Рейтинг: 0 / 0
14.05.2020, 18:50
    #39957678
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
rdb_devШкольная теорема Пифагора больше не в чести?

Она хреново работает в неэвклидовом пространстве. Да и с индексами тоже напряг.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
14.05.2020, 18:55
    #39957681
Гаджимурадов Рустам
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
DS> Да и с индексами тоже напряг.

Индекс же по dist-у можно сделать.
Не к параметру, а константе, разумеется.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
14.05.2020, 18:55
    #39957682
rdb_dev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Dimitry Sibiryakov, к примеру, для логистики в пределах города формой земли можно пренебречь, представив секунды широты и долготы на плоскости. В итоге, всё упрощается до: c 2 = a 2 + b 2
...
Рейтинг: 0 / 0
14.05.2020, 18:59
    #39957686
ъъъъъ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
rdb_dev
Dimitry Sibiryakov, к примеру, для логистики в пределах города формой земли можно пренебречь, представив секунды широты и долготы на плоскости. В итоге, всё упрощается до: c 2 = a 2 + b 2


Так вопрос вовсе и не в натягиванием сегмента сферы на плоскость.
...
Рейтинг: 0 / 0
14.05.2020, 19:05
    #39957694
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Гаджимурадов Рустам
Order by 2 ?
И полный перебор по всем точкам
Гаджимурадов Рустам
индекс по выражению
У меня целевые точки различные

Dimitry Sibiryakov
Это пофиг. Цель приведённой конструкции - отфильтровать подмножество точек, используя индекс по r.lat/r.lon, чем и уменьшить перебор
Ясно. До этого я и сам дошел. Думал, что-то лучше посоветуют

rdb_dev
Школьная теорема Пифагора больше не в чести?
Для поверхности шара изобразите? А даже если и на плоскости - вопрос был как БЫСТРО найти точку, а не запрограммировать метрику

Гаджимурадов Рустам
Не к параметру, а константе, разумеется.
Тогда какой в нем смысл?
...
Рейтинг: 0 / 0
14.05.2020, 19:06
    #39957697
rdb_dev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
ъъъъъ
Так вопрос вовсе и не в натягиванием сегмента сферы на плоскость.
Так я и не предлагаю натягивать сегмент сферы на плоскость, а напротив - предлагаю пренебречь сферической формой и просто рассчитывать кратчайшее расстояние (LAT1 - LAT2) 2 + (LON1-LON2) 2 .
...
Рейтинг: 0 / 0
14.05.2020, 19:07
    #39957699
ъъъъъ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_,

дождаться FB 5.0 :)
...
Рейтинг: 0 / 0
14.05.2020, 19:08
    #39957700
ъъъъъ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
rdb_dev
ъъъъъ
Так вопрос вовсе и не в натягиванием сегмента сферы на плоскость.
Так я и не предлагаю натягивать сегмент сферы на плоскость, а напротив - предлагаю пренебречь сферической формой и просто рассчитывать кратчайшее расстояние (LAT1 - LAT2) 2 + (LON1-LON2) 2 .


Ну и дальше что - перебирать все точки? В том и задача, чтобы избежать сложности О(n).
...
Рейтинг: 0 / 0
14.05.2020, 19:11
    #39957704
Гаджимурадов Рустам
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_> Тогда какой в нем смысл?

Отфильтровать ближайшие и уже по ним сделать dist к параметру.
Хотя теоретически, это ненадёжно, конечно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
14.05.2020, 19:15
    #39957709
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Гаджимурадов Рустам
Отфильтровать ближайшие
Ближайшие к чему? Целевых точек порядка тысячи. Точек в массиве, в худшем случае 500 000 - 600 000
...
Рейтинг: 0 / 0
14.05.2020, 19:15
    #39957711
ъъъъъ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Гаджимурадов Рустам
Отфильтровать ближайшие и уже по ним сделать dist к параметру.

На основе отсортированных по расстоянию до Ленинграда сделать вывод о ближайших к Москве?
...
Рейтинг: 0 / 0
14.05.2020, 19:19
    #39957714
Гаджимурадов Рустам
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
_Vasilisk_> Ближайшие к чему?

Ближайших к расстоянию от искомой точки до условного центра координат.

> Целевых точек порядка тысячи. Точек в массиве, в худшем случае 500 000 - 600 000

Именно из-за большого количества надёжность будет относительно высокая
(но не 100%ная). Что за задача такая, что 1000 точек проверять - ХЗ, странно.
Возможно, дешевле будет один раз по таблице пройтись и 1000 точек проверять,
а не наоборот.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
15.05.2020, 13:52
    #39957982
_Vasilisk_
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Сделал так
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
CREATE INDEX IDX_ROUTES_COORD ON ROUTES (LAT, LON);

CREATE OR ALTER PROCEDURE sp_i_routes_find_near (
  in_lat dm_latitude,
  in_lon dm_longitude,
  in_radius_from dm_km,
  in_radius_to dm_km,
  in_radius_step dm_km)
RETURNS (
  out_pnt_id TYPE OF COLUMN routes.id)
AS
  DECLARE VARIABLE var_lb_lat dm_latitude;
  DECLARE VARIABLE var_lb_lon dm_longitude;
  DECLARE VARIABLE var_rt_lat dm_latitude;
  DECLARE VARIABLE var_rt_lon dm_longitude;
BEGIN
  out_pnt_id = NULL;
  WHILE (:in_radius_from <= :in_radius_to) DO BEGIN
    EXECUTE PROCEDURE pkg_geo.circum_rect (
      :in_lat,
      :in_lon,
      :in_radius_from
    ) RETURNING_VALUES (
      :var_lb_lat,
      :var_lb_lon,
      :var_rt_lat,
      :var_rt_lon
    );
    FOR
      SELECT
        rt."ID"
      FROM
        routes rt
      WHERE
        rt.lat BETWEEN :var_lb_lat AND :var_rt_lat AND
        rt.lon BETWEEN :var_lb_lon AND :var_rt_lon
      ORDER BY
        pkg_geo.distance(
          rt.lat,
          rt.lon,
          :in_lat,
          :in_lon
        )
      ROWS 1
      INTO
        :out_pnt_id
    DO
      EXIT;
    in_radius_from = :in_radius_from + :in_radius_step;
  END
END

...
Рейтинг: 0 / 0
15.05.2020, 14:05
    #39957993
Гаджимурадов Рустам
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Так это же простой ордербай, который я и предлагал. Или нет?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
15.05.2020, 14:14
    #39958000
Гаджимурадов Рустам
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск ближайшей точки
Даже если деревья, Вороного, хешинг и пр.
сложности использовать не хочется, то всё
равно секторирование или простой dist до
центра дал бы существенное ускорение, если
это действительно важно, конечно.

https://habr.com/en/post/228023/
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Поиск ближайшей точки / 25 сообщений из 27, страница 1 из 2
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]