Всем доброго времени суток!

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

Как делаю сейчас (приведу код на Delphi):



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

Но вот в чем вопрос - все это будет работать, если длина требуемой ломаной больше чем длина любого из отрезков исходной ломаной (например, длина всей ломаной 170 метров, разбить надо на 10 частей по 17 метров, длина каждого отрезка в ломаной примерно 6-6.5 метров) . А как написать универсальный алгоритм, который будет работать независимо от требуемой длины новой ломаной? Например, если мне надо будет разбить ломаную на 1000 отрезков, хотя сама она состоит из 50, хотя для моей задачи это не совсем нужно, но в тоже время в моей задаче может возникнуть необходимость разбить ломаную из 10 отрезков на 20 частей, а это тоже самое...

Очень прошу помощи!!!

Как я понял, ломаная состоит из отрезков разной длины, т.е. из цепочки векторов v(1), v(2)... и т.д., а вот части будут одинаковой длины. Самое простое, что приходит в голову - проходить вдоль ломаной:

1. Делим длину ломаной на число требуемых частей и получаем длину одной части P0.
Вектор  V будет описывать отрезки или их куски. Статическая переменная P буде описывать части или их куски.
Вектору V присваиваем значение первого отрезка V=v(1)  (вектор направлен от любой крайней точки ломаной, естественно).  Переменной P присваиваем длину одной части P=P0.
2. Сравниваем длину вектора V и величину P. Если V>P продолжаем (пункт 3); если V<P, идем к пункту 4; если V==P, тогда к пункту 5.
3. Отмеряем P от начала V это будет окончание части. Присваиваем V=V-P. Присваиваем P=P0. Возвращаемся к пункту 2.
4. P=P-V и V=v(i), где i - номер следующего отрезка-вектора. Возвращаемся к пункту 2.
5. Очевидно, что в случае равенства (см выше), окончание вектора и будет точкой окончания очередной части. Если это была последняя часть, рассчет окончен. Если остались еще части - продолжаем (к пункту 6).
6. Присваиваем P=P0 и V=v(i), где i - номер следующего отрезка-вектора. Возвращаемся к пункту 2.

ЗЫ: Векторы нужны только если надо найти точки окончания частей в какой-то системе координат. Если нужно просто расстояние от начала ломаной - отрезки можно представлять статическими величинами.

Ну, вроде ничего не напутал  

Это сообщение отредактировал(а) _Y_ - 8.2.2013, 23:42

_Y_, огромное спасибо!!! Как сам до этого не дошел до сих пор не понимаю.

Единственное, что изменил в вашем алгоритме - это "если V==P, тогда к пункту 5" - в моей задаче практически невозможно достичь равенства по причине изначального округления координат(в рабочем файле координаты даны с одной точностью, в исходном с другой, в обсчитываемых данных с третьей), поэтому сделал двойное условие - V==P или  P-V<0.00001.

Dementor, извиняюсь - не написал сразу. Учет ошибок измерения или машинной ошибки вроде сам-собой разумеется. Если работать с непрерывными величинами, естественно (с целочисленными, понятное дело, он не нужен). Единственно, двойное условие ни к чему. Если ошибки измерения у Вас не какому-то особому закону соответствуют, то просто считается модуль:
|P-V|<0.00001