Здачка такая -- есть таблица координат -- трек движения автомобиля с сайтика Виалон. Есть координаты фиксированной точки. Требуется понять в какое время машина была в этой точке. Проблема в том, что ТОЧНО в этой точке она скорее всего никогда не была, а была скажем на 30 метров левее или правее. Значит поиск по точному совпадению координат не подходит. Надо найти в таблице точку, МИНИМАЛЬНО отличающуюся от фиксированной. Вопрос -- как?

Простым перебором строк таблицы не предлагать -- в таблице полторы-две тысячи строк, а точек 5-10 и всю эту лабуду надо повторить около ста раз (т.е. для каждой машины из парка). Есть какие-нить идеи? Буду очень благодарен...

Запрос?

Ну скорее всего да. А идею запроса можете предложить?

Соединение таблицы точек с таблицей треков. Вычисляешь расстояние как сумму квадратов разностей координат. Выкидываешь больше некой минимальной дельты. Получившаяся таблица - время и дата пребывания машины в искомых точках. Делов то.

Вопрос про 1С?

Современный процессор делает миллиарды операций в секунду, и твоя задача выполнится за доли секунды. Ну на 1С это будут секунды.

(3) Спасибо, сейчас попробую
(4) если бы секунды... На практике прямой перебор для 96 машин и 470 фиксированных точек проработал около сорока минут

(0) ты в школе информатику прогуливал?

https://acmp.ru/article.asp?id_text=159

(6) ага, и эту операцию придется повторить
2000 строк таблицы * 5 точек * 100 машин = ОДИН МИЛЛИОН раз...

Мне что-нить побыстрее надо

Метрику можешь брать другую, не обязательно сумму квадратов. Сумма модулей разности будет быстрее скорее всего. А точность тебе нафиг не нужна.

Да и вообще у тебя там система координат хз какая ) Сам придумывай попроще метрику.

(0)

Значит поиск по точному совпадению координат не подходит.

А как ты думаешь - если у координат последние цифры заменить нулями - во что превратится "точка"?

ябы построил (подобрал) систему координат. в этом случае на поиск точки потребуется 1-4 выбора точек , тк попадаем сразу в нужный "квадрат". естественно при добавлении новой точки   придется пересчитывать.

смотрите в сторону реализации пространственных индексов.

(10) точка и будет, только сместится хз куда

(7) "ОДИН МИЛЛИОН" арифметических операций это даже для 1С смешная нагрузка. А вот если ты в этом цикле данные из БД будешь тянуть, тогда да... кранты. Запрос должен быть один.

(0) ТС кури про индексы и метод половинного деления на отсортированных данных

(14) индексы в смысле обычное деревья

https://ru.wikipedia.org/wiki/Задача_поиска_ближайшего_соседа

Можно сделать в два прохода, сначала ограничить точки входящими в квадрат +/- 50 м, потом найти ближайшую. Одним пакетником, конечно.

Только сообразил что задачка действительно в 2 приема решается ))

1. Сначала добавляем колонку расстояние до фикс точки (формула расстояния между точками на плоскости).
2. Затем берем запись с этим минимальным расстоянием.

задать два условия:
( < x < ) и ( < y < )

(19) Да это 0 этап сокращения выборки для уже более точного нахождения искомой "ближайшей точки" к фиксированной.
Если точность не нужна полная (именно ближайшую точку траектории отыскать) то вполне его хватит чтобы понять.

Но лучше все же найти точную иначе если машина долго стояла рядом с точкой то время будет не верное

Расстояние между точками на плоскости не прокатит. Для gps координат формула сложнее. Я такое тупым перебором считал. Когда точек стало много заюзал ком объект куда вынес многопоточных расчёт. Код был на шарпе на 1 потоке скорость расчёта примерно в 100-200 раз выше чем в 1с, при распаралеливании ещё выше.

(18) Прямо в запросе можно выбрать точку с минимальным расстоянием. Не знаю, будет ли это значительно быстрее.

(22) Как? там нужно тригонометрические функции использовать дял расчета. Теорема пифагора не катит

(0) бери не все точки, а например каждую 100-ю. ищи ближайшие среди них.
потом бери все точки, которые расположены рядом с этими ближайшими в в треке - и ищи среди ник

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

(5) >На практике прямой перебор для 96 машин и 470 >фиксированных точек проработал около сорока минут
а ты для каждой точки заново все трэки перебирал? и заново их из базы вычитывал?

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

т.е. в первую очередь нужно минимизировать количество запросов к БД, миллион операций с оперативной памятью - плевое дело

(25) как-то так да.
но правильно решение зависит от того, как хранятся данные и насколько дорого их вычитывать в память

Да просто автору можно сделать предрасчет и записать уже подготовленные данные в регистр. 40 минут это фигня, на сервере может и быстрее будет. Можно запустить по 1 фоновому заданию на машину

(23) Не обижайте Пифагора: для небольших расстояний (надеюсь, ближайшая точка не в сотне километров от точки) поверхность Земли можно считать плоскостью. Да и сама метрика не важна: ищется же не точное расстояние, а ближайшая точка: для любой разумной метрики у "ближайшей" точки и расстояние будет минимальным.

(29) ваша область будет не круглой а овальной. Получится с 1 стороны можно на 200 метров нужно подъехать, а с другой на 100. Посмотрите на карту на соотношение долготы

вроде бы есть специальные БД, типа Postgis... там одним запросом такие операции делаются

типа в массиве отправляешь список координат и координату точке, и оно возвращает минимальное расстояние...

точнее не подскажу, давно шашку в руки не брал

очень быстро работает

Теория : поиск в неупорядоченном массиве это перебор всех значений.
Вывод задача с указанными условиями - не разрешима.
А вообще исследование трекинга - необязательно с расчетом расстояния, достаточно найти "попадание", например с условиями (X-Xo)<30 и (Xo-X)<30 и (Y-Yo)<30 и (Yo-Y)<30
Уже по ним вычислить реальное рассточние и выбрать минимум
Ускорение для множества точек и автомобилей - как уже было сказано ранее - это отбор необходимых данных за один проход. Но в любом случае, пофакту это полный перебор всех строк.

(21) Считать расстояние в градусах и всё прокатит.
(0) Соединение по условию. Рекомендую индексы.