|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
В таблице хранятся точки проезда в формате Код: sql 1. 2. 3. 4. 5.
Как бы мне в этой таблице найти точку, ближайшую к заданной? Т.е. по сути нужно оптимизировать такую процедуру Код: 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.
Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км, искать координаты углов описанных вокруг этих окружностей прямоугольников, и тогда при наличии индекса (LAT, LON) можно будет довольно быстро отфильтровывать точки на принадлежность минимальному прямоугольнику. А потом уже из отфильтрованных искать ближайшую Может что пооптимальнее будет? С уважением, Vasilisk ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:01 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Это, фактически, ты щас пытаешься спросить как вычислить расстояние по геокординатам? Окстись, передохни чуток. :) Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:08 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км Обычно фильтруют по прямоугольнику разумных размеров: Код: sql 1.
Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:11 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Гаджимурадов Рустам Это, фактически, ты щас пытаешься спросить как вычислить расстояние по геокординатам? Мне нужно найти в массиве точек координаты ближайшей точки к заданной. Причем найти быстро. А массив большой ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:13 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Обычно фильтруют по прямоугольнику разумных размеров: ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:15 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_ найти в массиве точек координаты ближайшей точки к заданной. Причем найти быстро. А массив большой При заполнении массива точек строить пространственный индекс (см. "R-дерево"). CORE-659 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:28 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_> Мне нужно найти в массиве точек координаты ближайшей точки к заданной. Order by 2 ? _Vasilisk_> Причем найти быстро. А массив большой Если производительность будет не устраивать - можно будет сделать индекс по выражению или "секторирование". Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:38 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_У меня даже есть функция, которая вычисляет координаты прямоугольников Это пофиг. Цель приведённой конструкции - отфильтровать подмножество точек, используя индекс по r.lat/r.lon, чем и уменьшить перебор. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:44 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_ Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км, искать координаты углов описанных вокруг этих окружностей прямоугольников, и тогда при наличии индекса (LAT, LON) можно будет довольно быстро отфильтровывать точки на принадлежность минимальному прямоугольнику. А потом уже из отфильтрованных искать ближайшую ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:44 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
rdb_dev _Vasilisk_ Есть мысль создавать набор концентрических окружностей, скажем с радиусом 1 км, искать координаты углов описанных вокруг этих окружностей прямоугольников, и тогда при наличии индекса (LAT, LON) можно будет довольно быстро отфильтровывать точки на принадлежность минимальному прямоугольнику. А потом уже из отфильтрованных искать ближайшую Последовательным перебором? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:48 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
rdb_devШкольная теорема Пифагора больше не в чести? Она хреново работает в неэвклидовом пространстве. Да и с индексами тоже напряг. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:50 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
DS> Да и с индексами тоже напряг. Индекс же по dist-у можно сделать. Не к параметру, а константе, разумеется. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:55 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, к примеру, для логистики в пределах города формой земли можно пренебречь, представив секунды широты и долготы на плоскости. В итоге, всё упрощается до: c 2 = a 2 + b 2 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:55 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
rdb_dev Dimitry Sibiryakov, к примеру, для логистики в пределах города формой земли можно пренебречь, представив секунды широты и долготы на плоскости. В итоге, всё упрощается до: c 2 = a 2 + b 2 Так вопрос вовсе и не в натягиванием сегмента сферы на плоскость. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 18:59 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Гаджимурадов Рустам Order by 2 ? Гаджимурадов Рустам индекс по выражению Dimitry Sibiryakov Это пофиг. Цель приведённой конструкции - отфильтровать подмножество точек, используя индекс по r.lat/r.lon, чем и уменьшить перебор rdb_dev Школьная теорема Пифагора больше не в чести? Гаджимурадов Рустам Не к параметру, а константе, разумеется. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:05 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
ъъъъъ Так вопрос вовсе и не в натягиванием сегмента сферы на плоскость. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:06 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_, дождаться FB 5.0 :) ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:07 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
rdb_dev ъъъъъ Так вопрос вовсе и не в натягиванием сегмента сферы на плоскость. Ну и дальше что - перебирать все точки? В том и задача, чтобы избежать сложности О(n). ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:08 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_> Тогда какой в нем смысл? Отфильтровать ближайшие и уже по ним сделать dist к параметру. Хотя теоретически, это ненадёжно, конечно. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:11 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Гаджимурадов Рустам Отфильтровать ближайшие ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:15 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Гаджимурадов Рустам Отфильтровать ближайшие и уже по ним сделать dist к параметру. На основе отсортированных по расстоянию до Ленинграда сделать вывод о ближайших к Москве? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:15 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
_Vasilisk_> Ближайшие к чему? Ближайших к расстоянию от искомой точки до условного центра координат. > Целевых точек порядка тысячи. Точек в массиве, в худшем случае 500 000 - 600 000 Именно из-за большого количества надёжность будет относительно высокая (но не 100%ная). Что за задача такая, что 1000 точек проверять - ХЗ, странно. Возможно, дешевле будет один раз по таблице пройтись и 1000 точек проверять, а не наоборот. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.05.2020, 19:19 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Сделал так Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2020, 13:52 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Так это же простой ордербай, который я и предлагал. Или нет? Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2020, 14:05 |
|
Поиск ближайшей точки
|
|||
---|---|---|---|
#18+
Даже если деревья, Вороного, хешинг и пр. сложности использовать не хочется, то всё равно секторирование или простой dist до центра дал бы существенное ускорение, если это действительно важно, конечно. https://habr.com/en/post/228023/ Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
15.05.2020, 14:14 |
|
|
start [/forum/topic.php?fid=40&msg=39957671&tid=1560351]: |
0ms |
get settings: |
6ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
55ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
54ms |
get tp. blocked users: |
1ms |
others: | 248ms |
total: | 394ms |
0 / 0 |