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

любопытные подробности всплывают в процессе

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

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

К слову - в школе еще недоучился акад. Виноградов, гл. ред. Маетматической энциклопедии. У него в предметном указателе много всяких кривых есть, и ломаные есть, тока вот ломаной кривой нету. Я непротив такой компании;-)

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

Печалька... задача любопытная, но Вы батенька упороты вноль, общаться с Вами невозможно. Трудовых успехов!

но Вы батенька упороты вноль

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

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

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

Упороты обычно не споосбные признавать своих ошибок ботаны

Так вот кто Вы есть на самом деле! Я конечно подозревал... ;-)

молящиеся на различие между синонимами: кривыми и линиями, и на авторитеты.

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

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

А она нуждается в оптимизации? Ответа про требования к производительности от Вас так и не было.

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

Огурец, объясни мне ты что имел ввиду ТС, я правда не догоняю. У него таки ломаная, или все таки кривая к-ю надо сплайнить?

и как её дешево оптимизировать.

Какой процент области занят этими ломаными-кривыми (если считать что они имеют ненулевую толщину)?

Два множества точек, одно - «кривая», другое - «толстая линия». Задача узнать «лежит» ли «кривая» в «толстой линии».

Это то я понял...

Ладно, ТС похоже настока упорот что сам не знает что там у него, то ли кривая, то ли ломаная. Вот по крайней мере 7 решений для нахождения расстояния от точки до набора ЛОМАНЫХ (обобщить до сплайнов он сам сможет, в школе же видать хорошо учился, не то что нынешняя моложеЖь, треть которой на ЕГЭ элементарную задачу решить не смогла).

1) перебор - проверка точки с каждым отрезком. Тривиально, и для озвученных им цифер наверное самое то. Да, для проверки принадлежности R отрезку (A_i,B_i) проверяем |R_x*a+R_y*b+c|<epsilon_1, если да то проверяем (A_i-R)*(B_i-R)<epsilon_2. Никаких корней считать не надо, корень операция дорогая.

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

3) как п2. но вместо 2D массива используем std::map с ключом вида pair<int,int> (номер ячеки сетки по х и у). Дает профит, если массив из п.2. сильно разрежен.

4) То же что п3, но для хранения отрезков используем квадро-дерево.

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

6) тоже что п.5, но для хранения пикселей юзаем std::map

7) .тоже что п.5., но для хранения пискселей юзаем квадро-дерево.

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

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

Можно еще хранить координаты в целых, с плавающей точкой и децимальных числах, тогда способов будет 21! Больше способов - выглядишь умнее.

Мдя... вопросов к Вам больше не имею. Мало того что у Вас логика хромает, так еще Вас в школе до сих пор не научили себя вести. Идите ка в игнор.

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

Если интерполировать кусочно-гладкими кривыми (сплайнами), то как ни странно объём вычислений может вырасти и будут проблемы в интерпретации узлов.

http://ru.wikipedia.org/wiki/Среднеквадратическое_отклонение