Клуб API Карт

Вырезать часть точек линии.

onedreamW
14 июля 2011, 00:51

Привет всем снова.

Есть загружаемый на карту GPS (GPX) - трек. В нем много точек.
На карте его отрисовываю линией (да, мне так удобнее)
Народ попросил сделать возможность массового удаления точек.


Как я делаю сейчас:

Создаю "резиновый" прямоугольник (управляемый мышью), потом пробегаюсь по точкам линии, преобразуя их координаты в пиксельные и проверяю на попадание точки в этот прямоугольник. Если да, то удаляю.

На длинных треках, это понятно, каждое удаление точек занимает ощутимое время.

 

   for(i=0;i<this.obj.getPoints().length;i++){
        var toPx = map.converter.coordinatesToLocalPixels(this.obj.getPoints()[i])
        if (( toPx.y < boxbottom ) && ( toPx.y > boxtop ) && ( toPx.x > boxleft ) && ( toPx.x < boxright ))
           this.obj.removePoint(i)
    }
// obj - линия трека
// this - это класс, рисующий прямоугольник и удаляющий точки
 

 

Как правильно?  Ваш вариант?

13 комментариев
Подписаться на комментарии к посту

а если "резиновый" прямоугольник будет полигоном

и пробегаясь по точкам проверять их методом contains,

совсем исключив преобразование coords => pixels?

Да будет быстрее. Но, к сожалению не намного.

Кстати, каким образом работает contains? Т.е. что будет быстрее: contains или преобразовать границы прямоугольника в гео-координаты (один раз) и проверять на попаданиие в границы?

Попробую оба метода. Отпишусь.

Докладываю:

 

существующий метод:

 

14884ms

 

преобразование в geo координаты

14328ms

12571ms

12491ms

 

методом contains

14934ms

132799ms

17101ms

 

 

Браузер: FF5 (в хроме быстрее)

Трек: 1150 точек

Попробуйте не удалять точки, а, наоборот, формировать новый массив точек и строить новую полилинию.

Пробовал вообще ничего не делать в цикле, время практически не уменьшается. 
Т.е. основные затраты - обсчитать точки.

Хм. Как-то подозрительно долго, 1000 точек для FF - копейки.

Попробуйте профайлером посмотреть, что больше всего времени занимает.

Разница FF и Хрома в это задаче - поразительная.

Хром быстрее на порядок, а иногда и на два.

Королев Михаил
14 июля 2011, 12:54

а в чём сверхзадача? вам нужно именно править трек или уменьшить кол-во точек, дабы соптимизировать его?

Последнюю задачу я в GPS-Помощнике решал математическими методами выключая точки из прямолинейного движения (с некоторой погрешностью) на сервере.

Никакой "сверх" нету.
Просто люди хотят иметь возможность удалить части трека не по одной точке а кусками.


ЗЫ: В общем-то, мой функционал похож "помошника".

У вас какието не реальные значения.

За это время можно общитать несколько сотен тысяч точек, если не миллионы(в хроме уж точно)

Попробуйте последовать совету twirl и не удалать точки, а не включать их в некий новый массив, на основе которого потом создадите новый полигон.

тест номер 2:

 измените начало цикла на  for(var i=0, l=this.obj.getPoints().length;i

Сделал цикл как Вы сказали. Стало быстрее.

Да, приведенные выше цифры тестирования завышены. Очевидно не учел то, что Мозилла перед этим была включена сутки и в памяти занимала 800мег.

Ниже ссылка на скринкаст, как работает сегодня. 
http://www.youtube.com/watch?v=bunvYgEMN04

В консоль выводится лог о затраченном времени и количестве точек трека.

Собственно, вопрос по видео:
Как видно из видео, удаляются не все точки. Почему? (метод contains дает то же самое, т.е. пропускает точки )

Код: http://pastebin.com/McsWJPAB

 

Эх, не слушаете вы нас.

removePoint вызывает перестройку внутрених данных, и на место удаленной точки прийдет та которая была i+1, и которую вы уже не будете тестировать.

Также уменьшиться общая длиннах масива данных.

Также вызовется перестройка графики.

Итого: тормоза и баги. Стереть часть в 10 раз дольше чем открыть сам gpx трек :)

Поменяем цикл

 

  1. var newPoints = []; 
  2. for( i=0;i < pointscount;i++ ){
  3.                 toPx = this.obj.getPoint(i);
  4.         if (toPx) if (( toPx.getLng() < tlpoint.getLng() ) && ( toPx.getLng() > rbpoint.getLng() ) && ( toPx.getLat() < tlpoint.getLat() ) && ( toPx.getLat() > rbpoint.getLat() ))
  5.         {
  6.                 //do nothing
  7.                 } else {
  8.   newPoints.push(toPx);
  9. }
  10.     }
  11. this.obj.setPoints(newPoints);
А по всему остальному - зачот. Красиво и удобно.

 

time: 97points: 1149Спасибо!

removePoint вызывает перестройку внутрених данных, и на место удаленной точки прийдет та которая была i+1, и которую вы уже не будете тестировать.

Также уменьшиться общая длиннах масива данных.

Также вызовется перестройка графики.


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

Ну что ж, мне ( и, надеюсь, другим ) наука :)
Еще раз спасибо Вам и Клубу :)