powered by simpleCommunicator - 2.0.50     © 2025 Programmizd 02
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / Поиск ближайшей точки
25 сообщений из 27, страница 1 из 2
Поиск ближайшей точки
    #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
Поиск ближайшей точки
    #39957642
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это, фактически, ты щас пытаешься спросить
как вычислить расстояние по геокординатам?

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

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

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

Order by 2 ?

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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

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

Именно из-за большого количества надёжность будет относительно высокая
(но не 100%ная). Что за задача такая, что 1000 точек проверять - ХЗ, странно.
Возможно, дешевле будет один раз по таблице пройтись и 1000 точек проверять,
а не наоборот.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск ближайшей точки
    #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
Поиск ближайшей точки
    #39957993
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так это же простой ордербай, который я и предлагал. Или нет?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Поиск ближайшей точки
    #39958000
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Даже если деревья, Вороного, хешинг и пр.
сложности использовать не хочется, то всё
равно секторирование или простой dist до
центра дал бы существенное ускорение, если
это действительно важно, конечно.

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


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