Есть справочник точки, у которых есть широта, долгота, радиус
Есть регистр сведений, в который постоянно попадают данные где есть ссылка на справочник машины и широта, долгота.
Т.е. 2 таблицы с колонками:
Точка, Широта, Долгота, Радиус и Машина, Широта, Долгота.
Мне нужно обработать каждую строку таблицы с машинами, что бы понять, попала ли она в нужную точку.
Теоретически я могу сделать так

Для Каждого Машина из Машины Цикл
  ТекТочка = Неопределено;
  Для Каждого Точка из Точки Цикл
     Если ТочкаВходитВРадиус(Машина.Широта1, Машина.Долгота1, Точка.Широта2, Точка.Долгота2, Точка.Радиус) Тогда
        ТекТочка = Точка.Ссылка;
        Прервать;
     КонецЕсли;
  КонецЦикла;
  Если ТекТочка <> Неопределено Тогда
     ЗарегистрироватьПрибытиеВТочку(Машина.Ссылка, ТекТочка);
  КонецЕсли;
КонецЦикла;

Допустим , код примерно выглядет так. Хотелось бы его оптимизировать, что бы работало все быстрее. Количество строк в таблице точек = 10000, количество строчек в таблице машин - 10000

(0) у тебя все 10000 машин на выезде постоянно?

(1) у меня у каждой машины по 500 координат

Не совсем понял... А запрос с соединением не пойдет?

(3) на сколько я понимаю - запросом ты не вычислишь это:

ТочкаВходитВРадиус(Машина.Широта1, Машина.Долгота1, Точка.Широта2, Точка.Долгота2, Точка.Радиус)

В запросе я не могу понять, что "ТочкаВходитВРадиус"

(4) но обойти машины и ИХ конкретные точки - это да, запросом! Так меньше обходов будет

(0) Может логику поменять?
При записи в регистр проверять ТочкаВходитВРадиус
ну и соответственно чо-то писать.

(6) у меня таблица очищается постоянно, когда точка обрабатывается. Т.е. 10000 строк - они постоянно с каждой секундой растут. GPS шлет данные.

(5) ты можешь запросом сразу сделать связку Машина-ТОЧКИ...т.е.  во втором цикле  " Для Каждого Точка из Точки Цикл" ты будешь перебирать не АБСОЛЮТНО ВСЕ ТОЧКИ, а толко точки конкретно этой машины. А дальше как ты написал.

(9) я не могу сделать так, такой связки нет. Машина может прибыть не в свою точку :)

(10) и что при этом будет? Приехала машина не в свою точку...что дальше?

(11) нужно оповестить диспетчера, что машина прибыла не в ту точку :)

(11) там дальше жесть вообще, на самом деле. Всяческие событие, пересчет маршрута, оповещения и т.д.

можно условно принять точку доставки не кругом, а квадратом, тогда будет намного проще проверку делать

в том числе и в запросе

(5) Почему?
Можно показать функцию ТочкаВходитВРадиус?

изменить формат хранения точки - добавить долгота_начало, долгота_конец, широта_начало, широта_конец
Получаем запросом точки (проверка на квадрат), далее уточняем на вхождение в круг

(12) в таком случае ты никак не оптимизируешь...в любом случае выбирать все-ко всем.

(15) я делал не квадратом, прямоугольником... но в таком случае у меня очень сильно теряется точно. Это по геокоординатам, обрезая знаки, составлял соответствие и далее по нему искал - работает быстро, но не точно. Вот ищу метод лучше.

(16) там тригонометрические функции используются (косинус угла)...такое в запросе не посчитать!

(19) точность теряется. Прямоугольник, т.к. изменение на сотую часть широты и долготы разные. т.е. смещение 59.50 - до 59-51 по широте отличается от 59.50 до 59.51 по долготе. Расстояние разное.

(20) а таки покажи... я так понимаю что нужно просто определить что точка попадает в круг... куда там косинус и угол...

(22) не круг, земля же не круглая :Р

   Пи          = 3.14159;
   РадиусЗемли = 6372795;
   Расстояние  = РадиусЗемли*ATAN(Sqrt(Pow(COS(Пи*Широта2/180)*SIN(ABS(Пи*Долгота2/180-Пи*Долгота1/180)),2)+Pow(COS(Пи*Широта1/180)*SIN(Пи*Широта2/180)-SIN(Пи*Широта1/180)*COS(Пи*Широта2/180)*COS(ABS(Пи*Долгота2/180-Пи*Долгота1/180)),2))/(SIN(Пи*Широта1/180)*SIN(Пи*Широта2/180)+COS(Пи*Широта1/180)*COS(Пи*Широта2/180)*COS(ABS(Пи*Долгота2/180-Пи*Долгота1/180))));
   Возврат Расстояние <= Радиус;

(0) СКД с выводом результат в коллекцию значений. Правда функцию придется пихать в общий модуль.

тут математика и физика нужна, т.е. на формум морской навигации шагом марш

(24) связь по функции???

для упрощения бери не круглый радиус а квадратный

(22) :) наивный :) Там учитывается широта, на которой находится точка!

(23) Разложи гармонические функции и корень в ряд, выбери адекватное  для себя количество членов ряда и замени функцию на выражение в запросе

(26) вычисляемое поле и отбор по нему.

(22) хотел x*x + y*y >= r*r? :)

+(29) выражение получится огромным...

(23) я вот так считал:

//расчет вхождения
               Если Выборка.ШиротаКонтра<>0 и Выборка.ДолготаКонтра<>0 тогда
                   
                   //расстояние в секундах
                   РасчШирота= ? (  (Выборка.ШиротаКонтра - Выборка.ШиротаДока) >=0,(Выборка.ШиротаКонтра - Выборка.ШиротаДока), -(Выборка.ШиротаКонтра - Выборка.ШиротаДока) ) *60;  
                   РасчДолгота= ? (  (Выборка.ДолготаКонтра - Выборка.ДолготаДока) >=0,(Выборка.ДолготаКонтра - Выборка.ДолготаДока), -(Выборка.ДолготаКонтра - Выборка.ДолготаДока) ) *60;
                   
                   //расстояние в метрах
                   РасчШирота=РасчШирота*30.86;
                   РасчДолгота=РасчДолгота*30.86* cos(  Цел(Выборка.ШиротаДока/100)  );
                   
                   //рассчитываем удаленность точки
                   Удаленность=Sqrt( РасчШирота*РасчШирота + РасчДолгота*РасчДолгота);
                   
                   Если Удаленность<=100 тогда
                       КменЗачет=КменЗачет+1;                        
                       КДеньЗачет=КДеньЗачет+1;
                       Нстрока.Попадание="ДА";    
                   Иначе
                       КменНеЗачет=КменНеЗачет+1;
                       КДеньНеЗачет=КДеньНеЗачет+1;
                       Нстрока.Попадание="Нет";
                       КонецЕсли;
               Иначе
                   КменНовые=КменНовые+1;
                   КДеньНовые=КДеньНовые+1;
                   Нстрока.Попадание="Нет контрольной точки";
               КонецЕсли;

(32) с чего бы? Выражение в общей функции. В поле только имя функции с параметрами.

а млин соррь - мазнул. В (32) все верно сказано.

Еще вариант. В запросе отбирать с 4 ближайшие точки для каждой машины по неточной формуле, а потом для этих 4-х точек считать точно.

(33) так а чем это связано с оптимизацией, что-то не понимаю. Не трогаем функцию ТочкаВходитВРадиус :)
Тут больше интересно, может быть какие-то объекты можно использовать, которые работают быстрее чем ТЗ. Допустим ранее я использовал соответствие.
Было как-то так, но тут погрешность большая:

   Запрос = Новый Запрос(
   "ВЫБРАТЬ
   |    ТР_Точки.Ссылка КАК ТекущаяТочка,
   |    ТР_Точки.Широта,
   |    ТР_Точки.Долгота,
   |    ТР_Точки.Округление
   |ИЗ
   |    Справочник.тр_Точки КАК ТР_Точки
   |ГДЕ
   |    НЕ ТР_Точки.ПометкаУдаления");
   Выборка = Запрос.Выполнить().Выбрать();
   Соответствие = Новый Соответствие;
   Пока Выборка.Следующий() Цикл
       Если Не ЗначениеЗаполнено(Выборка.Широта) ИЛИ Не ЗначениеЗаполнено(Выборка.Долгота) или Выборка.Округление = 0 Тогда
           Продолжить;
       КонецЕсли;
       Коэффициент = 1/Число("1"+Формат(0,"ЧЦ="+Выборка.Округление+"; ЧН=; ЧВН=; ЧГ="));
       Широта1        = Окр(Выборка.Широта, Выборка.Округление);
       Широта2    = Широта1 + Коэффициент;
       Широта3    = Широта1 - Коэффициент;
       Долгота1    = Окр(Выборка.Долгота, Выборка.Округление);
       Долгота2    = Долгота1 + Коэффициент;
       Долгота3    = Долгота1 - Коэффициент;
       Соответствие.Вставить(Лев(Строка(Широта1), Выборка.Округление + СтрДлина(Цел(Широта1))) + ":"+ Лев(Строка(Долгота1), Выборка.Округление + СтрДлина(Цел(Долгота1))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта1), Выборка.Округление + СтрДлина(Цел(Широта1))) + ":"+ Лев(Строка(Долгота2), Выборка.Округление + СтрДлина(Цел(Долгота2))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта1), Выборка.Округление + СтрДлина(Цел(Широта1))) + ":"+ Лев(Строка(Долгота3), Выборка.Округление + СтрДлина(Цел(Долгота3))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта2), Выборка.Округление + СтрДлина(Цел(Широта2))) + ":"+ Лев(Строка(Долгота1), Выборка.Округление + СтрДлина(Цел(Долгота1))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта2), Выборка.Округление + СтрДлина(Цел(Широта2))) + ":"+ Лев(Строка(Долгота2), Выборка.Округление + СтрДлина(Цел(Долгота2))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта2), Выборка.Округление + СтрДлина(Цел(Широта2))) + ":"+ Лев(Строка(Долгота3), Выборка.Округление + СтрДлина(Цел(Долгота3))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта3), Выборка.Округление + СтрДлина(Цел(Широта3))) + ":"+ Лев(Строка(Долгота1), Выборка.Округление + СтрДлина(Цел(Долгота1))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта3), Выборка.Округление + СтрДлина(Цел(Широта3))) + ":"+ Лев(Строка(Долгота2), Выборка.Округление + СтрДлина(Цел(Долгота2))), Выборка.ТекущаяТочка);
       Соответствие.Вставить(Лев(Строка(Широта3), Выборка.Округление + СтрДлина(Цел(Широта3))) + ":"+ Лев(Строка(Долгота3), Выборка.Округление + СтрДлина(Цел(Долгота3))), Выборка.ТекущаяТочка);
   КонецЦикла;

Но работает супер быстро :)

+(36) не точная формула - х1<=х<=x2 y1<=y<=y2, тогда 4 точки: (x1,y1),(x1,y2),(x2,y1),(x2,y2)

(37) так в вызове "ТочкаВходитВРадиус()" то и тратится все время. Нужно запросом, иначе не ускорить.

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

(28) Есть немного
(37) так посмотреть в отладчике, на чем основная нагрузка. но скорее всего все будет на вызове функции ТочкаВходитВРадиус.
А преобразовывать в удобные для условий значений в момент записи в регистр не предлагать?

(0) попробуй вот это:

Для Каждого Точка из Точки Цикл
     Если ТочкаВходитВРадиус(Машина.Широта1, Машина.Долгота1, Точка.Широта2, Точка.Долгота2, Точка.Радиус) Тогда
        ТекТочка = Точка.Ссылка;
        Прервать;
     КонецЕсли;
  КонецЦикла;

написать в одну строку.

(42) что-то слышал про одну строку - это реально ускоряет? :)

Что из себя представляют точки? Может машина находясь в точке А попасть в точку С минуя точку Б, которая находится между А и С. Может стоит перебирать не все точки? Если мы знаем, что машина находилась в точке А, то ее следует ожидать в точке Б, остальные точки выкинуть из перебора?

(43) попробуй :) просто это будет заметно только на очень длинных циклах - как раз твой случай!

(44) а что мешает машине объехать точку Б..двигаясь от А к С??? Ну скажем по другой дороге?

попробовал бы все же ряды Маклорена :)
математика наше все!

(42) и (43)... не... вы это типа серьезно? то что идет перебор 100000000 строк, это так... мелочи... главное код в одну строку сделать
однозначно нужно выборку сокращать...

(48) ты реально ОЧЕНЬ наивный чувак :) читай по-больше литературы :)

(46) Значит машина появится в точке Г, которая рядом с А.

http://en.wikipedia.org/wiki/Geohash

(49) да и так читаю... вот колобка заканчиваю, за что дальше браться не подскажешь?

(52) берись за винипуха - многое подчеркнешь для себя :)

(46) блин, ребят .. я не хочу рассказывать про бизнеспроцессы.. об этом в любом случае должен быть уведомлен диспетчер. Т.к. маршрут прокладывается по точкам.
(52) не проверишь, пока не поверишь ;)

(23) а формулу упростить не пробовали? во-первых, мне не понравилось, что  используются Ш1, Д1, Ш2, Д2, а не разницы между ними. это раз. во-вторых, для твоего случая формулу вычисления расстояний можно и нужно линеаризовывать.

самый скучный вариант, обойти все ПочтиПриехали(37) СовсемПриехали(0), будет самым быстрым
(37) можно еще оптимизировать сортировкой

А вот интересно, такое подойдет условие
иксы - это широта, игреки - это долгота.
(x-x1)квадрат + (y-y1)квадрат <= Радиус в квадрате?

(57) читай внимательно (33) :)

(57) это же тэйбл скан

Ну сам же писал, что это отбрасывание кривизны планеты.

(57) нет. для того, чтобы использовать данное условие, тебе нужно ШД перевести в х-у, причем, заранее условиться о точке отсчета.

(58) это что за хрень в (33)

Тогда вопрос, как первести геокоординаты в координаты х, у

(63) чисто математически - это будет зависеть от того, что ты подразумеваешь под х и у.

(67) а ты как думаешь?!

(64) проблема в том, что разные системы исчисления. Я не знаю как метры в геокоординаты переделать, а геокоординаты в метры.

(66) метры из радиуса Земли возьмутся )

(66) блин, чувак....в очереднйо раз - (33)!!!

там 2 точки с координатам. Широта и долгота это значения в "градусы, минуты, секунды" (как в GPS-приемниках)...а далее идет расчет растояния между двумы точками в МЕТРАХ!

Читай (51) считай координатам хэш, для быстрого поиска входят ли точки в радиус 600 метров ищешь по первым 6 символам, потом по 7 - а дальше уже можешь и кривизну луны или земли или приливы учитывать для определения точно ли машина возле торговой точки.

(62) а для тебя, недолекий человек, наводящий вопрос - сколько метров в одной секунде (подсказка - секунде вращения земли)?

(70) а меня в (33) вот эта штука насторожила:
РасчДолгота=РасчДолгота*30.86* cos(  Цел(Выборка.ШиротаДока/100)  );

эт чО такое?

+(71) точнее, cos(  Цел(Выборка.ШиротаДока/100)  )

(66) еще вот эту ветку посмотри: Калькулятор расстояния (гео. координаты А и Б)

(71) рассказываю - как раз таки 1 секунда вращения земли НА ЭКВАТОРЕ равна 30.86 метров. Но т.к. земля не круг, а элипс - делается поправка на косинус угола широты точки (это для северного полушария). В результате мы получаем сколько метров в одной секунде на вашей широте. У меня, в Краснодаре, это примерно 21 метр!

И ты не поверишь .сколько времени я убил на то ,чтобы решить эту, как казалось бы, элементарнейщую задачку!

(74) ну тут вообще эту задачу не решить, если учитывать горы ...

(75) Какие горы? Тут нужно просто определить - попаает одна точка в другую с определенной погрешность (радиусом) или нет. Если радиус маленький (у меня в 33 это 100 метров), то ни о каких горах собственно речь не идет.

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

(77)ну извиняйте, это почти как рыбку съесть и ... ну, вы поняли.
вот здесь: http://xpoint.ru/forums/misc/thread/14553.xhtml кстати, очень похожая проблема.

+(78) *с большой точностью
это кто сказал? математически эта формула абсолютно точна. для поверхности шара. а Земля, как известно, не шар. И даже не эллипсоид.

(77) тебе же уже сказали - при твоих условиях ты там особо ничего не оптимизируешь, т.к. в любом случае нужно обходить ВСЕ для ВСЕХ!

Ты же сам говоришь ,что это ОБЯЗАТЕЛЬНОЕ УСЛОВИЕ...Функцию поиска вхождения ты тоже не хочешь трогать ,т.к. она у тебя правильная и точная - так что ты хочешь оптимизировать?! Больше ничего не остается!

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

таким образом в запросе будут получены "точки, подозрительные на регистрацию прибытия" :)

их проверяешь точной формулой

(79) ну я об этом и писал в (75)
(80) можно попробовать оптимизировать используя SQL Запрос :Р Там можно синусы, косинусы использовать ... ужс.. чет не хочу я так оптимизировать )))

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

(77) запросом ограничь выборку разбив местность по "квадратам" с запасом на радиус... и ты получишь, что точка машины находится в квадрате с 10 точками. В результате твой цикл будет в разы короче.

(82) не, тебе просто нужно от точной формулы перейти к ее аппроксимации для малых значений дельт между Ш и Д.

+(85) и тогда уже с чистой совестью в условие для левого джойна запихивать. в принципе то, что в (84) предлагают

(82) сомневаюсь что скульный оптимизатор хорошо проглотит синусы и косинусы. и скорее всего он будет так же тупо для каждой записи одной таблицы перебирать записи другой таблицы. Но да, будет быстрее чем через 1С

(87) впендюрить врем. табличку со значениями син и кос для углов в диапазоне от 0 до пи с определенным шагом и делать в запросе с помощью этой таблички сплайн-аппроксимации ))