Вычисление положения точки на ломаной кривой по пройденному точкой пути.

Кривая заданная точками - проинтерполировать. (построить интерполяционный полином, например Лагранжа)

Можно определить, находится ли точка на кривой в конкретный момент времени, подставив координаты точки в этот полином и проверив, выполняется ли равенство.

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

Можно определить, находится ли точка на кривой в конкретный момент времени, подставив координаты точки в этот полином и проверив, выполняется ли равенство.

Немного не так — кривая имеет нулевую толщину, очевидно что практически надо знать находится ли точка сейчас и все ее предыдущие места на расстоянии не больше заданного от кривой.

Очевидно, что если все «места» кроме одного удовлетворяют условиям, то надо полагать что точка, таки движется по кривой, а «выброс» - есть ошибка.

Будет ли в таком случае выигрыш от полинома перед вычислением расстояния до отрезков кривой надо проверить.

А если кривая именно ломаная, то всё ещё проще, ибо линейная интерполяция.

линейная интерполяция.

Зачем интерполяция?

Вычисление положения точки на ломаной кривой

Что Вы там курите по выходным? «нарисуйте семь ломанных кривых из которых три прямые а две круглые»

Тз курю, чернила видать из спор навозника.

Немного не так — кривая имеет нулевую толщину, очевидно что практически надо знать находится ли точка сейчас и все ее предыдущие места на расстоянии не больше заданного от кривой.

Какая разница какая толщина? (или я вас не понимаю)

y = 3x; очевидно, что точка (1,3) лежит на прямой, а (1,4) - нет.

Тз курю, чернила видать из спор навозника.

Заметно... не бывает ломанных кривых. Линия или кривая, или ломанная, Вы уж определитесь для начала.

И какая толщина у линий? Если нулевая, Выуверены что точка будет идти именно по линии а не чуть-чуть рядом?

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

y = 3x; очевидно, что точка (1,3) лежит на прямой, а (1,4) - нет.

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

Какая разница какая толщина? (или я вас не понимаю)

Большая, точка (1, 3.0009) лежит на прямой y=3x если та имеет ненулевую толщину, и не лежит в обратном случае.

это как-то связано с движением транспорта по маршрутам и отслеживанием по GPS? :)

1. проще всего считать расстояние от точки до кривой (или до сегмента ломаной) как функцию времени. Если оно сохраняется в пределах заданного tolerance — точка движется вдоль кривой.

2. проще всего считать скалярное произведение направляющего вектора кривой (прямой) и вектора скорости частицы. Если оно >0, то частица движется «вперед»*, в противном случае «назад»*

* — вперед и назад — относительно направления увеличения параметра кривой.

А, ну это да, конечно нужно задать некий интервал, типа if(3 * x - y < 1e-6)

и по модулю

Точек много?

Определить кривую, вычислить расстояние (например по C-норме) между этой кривой и траекторией точки, если достаточно мало - лежит. Направление - касательный вектор к траектории.

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

не бывает ломанных кривых. Линия или кривая, или ломанная, Вы уж определитесь для начала.

Вы смешны.

это как-то связано с движением транспорта по маршрутам и отслеживанием по GPS? :)

Если ломанные кривые, то это одназначно АПЛ ориентируются по подводной группировке ГЛОНАСС!

Вы смешны.

Вас так сильно торкнуло?

Да вроде нет, тамже географические координаты, т.е. расчеты ведутся на геоиде.

Это же белка, он упоротый на постоянной основе.

проще всего считать расстояние от точки до кривой (или до сегмента ломаной) как функцию времени. Если оно сохраняется в пределах заданного tolerance — точка движется вдоль кривой.

Это на словах проще, а алгоритмически...

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

вычислить расстояние (например по C-норме) между этой кривой и траекторией точки

Обе характеристики заданы не аналитически, как быть?

В локальных декартовых координатах (переведенных из географических) на земле можно с хорошей точностью сферикой пренебрегать.

Это видимо белка-экономист. Есть оказывается термин «ломанная кривая спроса». Ну с этих ребят взятки гладки, у них основное математическое достижение это вынос общего множителя в формуле прибыли.

В принципе да, согласен.

переведенных из географических

Очень локальных, в пределах нескольких градусов емнип, и для определенных проекций, этим кто-то занимается разве?

Например задать аналитически - интерполяция во все поля.

Если точек много, и толщина не мала, брать max min {|x_i -y_j|} например и сравнивать его.

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

Много точек имеено кривой или пути? Или они одного порядка?

Это на словах проще, а алгоритмически...

Ну очевидно же, для решения этой задачи необходима *глобальная* параметризация кривой. Если у тебя только отрезки ломаных, увы, строгое решение — только полный перебор.

Например задать аналитически - интерполяция во все поля.

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

В общем случае кривая имеет порядка 30-50 точек, а путь порядка 100точек.

строгое решение — только полный перебор.

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

А внедрение двумерных индексов,

не совсем понял идею.

на небольших расстояниях (например, в пределах одного города) можно считать Землю плоской :)

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

Ув. товарищ белка, если Вы тут хотите получить какой то ответ, для начала определитесь что у Вас за линия - ломаная (состоящая из отрезков), или кривая заданная набором точек (которую надо какими то сплайнами интерполировать).

И сами в вики найдите мне термин ломаная кривая: http://ru.wikipedia.org/wiki/%CB%EE%EC%E0%ED%E0%FF есть, http://ru.wikipedia.org/wiki/Кривая есть, а вот устоявшегося термина ломаная кривая че та нету. На кривых бывают изломы, но люди которые хотят что бы их понимали обычно такие кривые ломаными кривыми не называют.

Например: http://ru.wikipedia.org/wiki/R-дерево

Дело в том что для пути из 100 точек и кривой из 50 надо посчитать 100*49 расстояний, а индексы позволят не вычислять лишнее.

В общем случае кривая имеет порядка 30-50 точек, а путь порядка 100точек.

Сколько таких линий и какие требования к производительности (и на каком железе)?

устоявшегося термина ломаная кривая че та нету.

тогда найдите там устоявшийся термин «ломаная линия» выж его предложили?

На кривых бывают изломы, но люди которые хотят что бы их понимали обычно такие кривые ломаными кривыми не называют.

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

Осталось найти этих разработчиков и потребовать у них выдать секреты, наверняка это у них «секрет фирмы» 8(

Да, пойдет. В смысле, один раз вычислить расстояния, найти минимум, а потом пользоваться тем фактом, что положение минимума меняется локально, т.е. новое положение где-то «вблизи» старого. Вполне нормальное решение для несамопересекающихся кривых

В моем случае самопересекающихся.

тогда найдите там устоявшийся термин «ломаная линия» выж его предложили?

Для дислектиков ище раз: http://ru.wikipedia.org/wiki/Ломаная

«Ло́маная (ломаная линия) — геометрическая фигура, состоящая из отрезков, последовательно соединенных своими концами.» (c) любимая Вами википедия.

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

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

В моем случае самопересекающихся.

Это скверно :)

Хотя... может и нет, при сортировке «петли» все равно разомкнутся, но их наличие вызывает потерю свойства локальности во времени: отдельные участки петель могут быть очень близко друг от друга геометрически, но проходиться в очень разные времена.

Для дислектиков ище раз

Для заучивания чего-либо не обязательно это постить на лоре. Кроме того тамже «Линия (в математике) — то же, что кривая. » Так что, вы плохо учитесь.

Хотите что бы я Вам тут че та подсказал - отвечайте на вопросы

Уважаемый, от вас мне хочется чтобы вы не оффтопили, а занимались самообразованием в другом месте.