Добрый день, друзья. Передо мой встала нетривиальная задача реализации "разбиения маршрута на отрезки".

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

Необходимо найти 3 точки, которые, с какой-то долей вероятности, характерезуют переломы траектории. Не знаю, как подробнее объянить, в приложенном изображении все понятнее.
Т.е. с минимальной погрешностью нужно разложить маршрут на 3 прямые. Разложить маршрут с помошью функции кусочно-линейной аппроксимации.



В какую сторону копать? Ну да, все это нужно будет реализовать, после математического решения.

Свои соображения -
найти полином 3-его порядка, который будет характеризовать 2 точки перегиба
Применить преобразования Хафа - идентифицировать является ли данный отрезок прямой и с каким приближением. http://ru.wikipedia.org/wiki/Преобразование_Хафа

White OwlА вообще, я бы подошел к этой задаче проще. Если у нас исходная линия уже задана отрезками (массив точек), то можно сделать что-то в духе последовательного загрубления:
Берем три последовательных точки (это два отрезка), измеряем угол между этими двумя отрезками. Если угол отличается от 180 на величину меньше чем X. То выкидываем среднюю точку. Проходим таким образом по всему пути. Получаем новый массив точек который представляет загрубленный путь с перегибами больше чем начальный X. Если этих перегибов больше требуемых трех - увеличиваем X и повторяем загрубление.
Интересная идея, спасибо.
White Owl Мне в этом изображении не нравятся одна вещь. Я верю в две первые точки перелома (если смотреть слева направо), но не понимаю как ты выбрал третью? Там на картинке как минимум еще две потенциальные точки перелома есть, и на первом и на втором отрезках.

Да, третья точка выбрана не совсем корректно. Это просто для наглядности.
softwarer Попробуйте описать реальную решаемую задачу. Почему именно три точки, зачем они нужны... Иначе решение может оказаться очень странным... например, по некоторым соображениям напрашивается фрагмент правильного N-угольника, вписанный в траекторию ))))
Есть алгоритм оповещения о подъезде к заданной токе, путем добавления 3-х дополнительных (подъезжаем именно по этой дороге, с этой стороны). 3 точки долдны максимально близко характерезовать путь подъезда. Алгоритм уже оттестирован и работает кореектно. Сейчас эти 3 точки выбираются вручную. Ну, дальше вы сами понимаете..=)

miksoftА как строится маршрут? Если по Яндекс.Картам (с которых взята иллюстрация), то, имхо, проще периодически перезапрашивать маршрут. Если оставшийся путь уменьшается, значит "подъезд" осуществляется.

Нет. Карт в алгоритме нет, в теме они просто для нагрядности. Маршрут не стрится - это gps-трек, точки gps координат, снятые с некоторым интервалом.

miksoftТогда "подъезжаем именно по этой дороге" не взлетит. Достаточно сдвига на несколько метров, который GPS не почувствует из ограниченной точности, и все - другая дорога, например, во встречном направлении.
Все это "пройдено". Прекрасно понимаю, что без некой пограшности не обойтись. Но желательно ее минимизировать.

miksoftИли я не понял задачу, или вы загоняетесь. Чем не годится просто расстояние до цели? Если оно достаточно долго сокращается и уже достаточно малО - значит подъезжаем.
Как я понимаю, точек из будущего все равно нет, т.е. проедет машина нужный поворот мимо или не проедет - не угадаешь.

Можем подъезжать с другой стороны. Можем по паралельной дороге, находящейся в 500 метрах от заданной (в этом случае точности gps более чем достаточно). Можем подъезжать по перпедикулярной дороге, а точка будет раполагаться на перекрестке, пересечении 2 дорог (нас интересует подъезд именно по заданнной дороге). Важно движемся ли мы именно по заданной дороге в заданном направлении или нет, а не просто приближаемся или удаляемся.

miksoft,

Положение исходной точки и 3 дополнительные точки, т.е. 4 точки, соединенные прямыми назовем маршрутом подъезда. Наглядно видно на изображении.
Маршрута нет изначально. Маршрут подъезда (3 точки перелома) мы должны как раз найти.

И, повторно двигаясь в этом месте, имель возможность определить, повторяем ли мы траекторию движения, движемся ли мы по той же дороге в том же направлении, по которому двигались ранее(собрали статистику, нашли путь подъезда, ранее)

softwarerДа, забыл упомянуть - возможно, в роли характерных точек надо будет брать не повороты, а как раз наоборот, середины "прямых". А может - и то, и другое. Это уже надо реализовать варианты и сравнить на практических данных, что лучше.Алгоритм уже написан, работает хорошо. Основан на точках перегиба. Только устанавливаются они пока вручную.