Разбиение ломаной

 
0
 
Алгоритмы
ava
Dementor | 08.02.2013, 19:34
Всем доброго времени суток!

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

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


for Interval:=1 to CatenaryArray[CatenaryNumber].VertNumber-1 do //цикл от второй до последней точки ломаной
    begin
      XApp1:=CatenaryArray[CatenaryNumber].X[Interval-1]; //координата X первой точки отрезка "1-2"
      YApp1:=CatenaryArray[CatenaryNumber].Y[Interval-1]; //координата Y первой точки отрезка "1-2"
      ZApp1:=CatenaryArray[CatenaryNumber].Z[Interval-1]; //координата Z первой точки отрезка "1-2"
      XApp2:=CatenaryArray[CatenaryNumber].X[Interval]; //координата X второй точки отрезка "1-2"
      YApp2:=CatenaryArray[CatenaryNumber].Y[Interval]; //координата Y второй точки отрезка "1-2"
      ZApp2:=CatenaryArray[CatenaryNumber].Z[Interval]; //координата Z второй точки отрезка "1-2"
      LOtr:=LOtr+sqrt(sqr(XApp2-XApp1)+sqr(YApp2-YApp1)+sqr(ZApp2-ZApp1)); //Считаем длину новой ломаной

      if LOtr<=dLA then //если длина новой ломаной меньше требуемой (переменная dLA), то проводим операции для данного отрезка новой ломаной
        begin
        //проводим операции для этого отрезка
        end
      else //если же сумма длин предыдущих отрезков и текущего превышает требуемую, то разбиваем отрезок "1-2" на отрезок "1-3" и "3-2", где 3-это точка, лежащая на отрезке "1-2"
        begin
          prirost:=dLA-(LOtr-sqrt(sqr(XApp2-XApp1)+sqr(YApp2-YApp1)+sqr(ZApp2-ZApp1))); // высчитываем какую часть нам надо взять из текущего отрезка для достижения требуемой длины ломаной

          XApp3:= XApp1+prirost*(XApp2-XApp1)/sqrt(sqr(XApp2-XApp1)+sqr(YApp2-YApp1)+sqr(ZApp2-ZApp1)); //координата X для нужной части отрезка
          YApp3:= YApp1+prirost*(YApp2-YApp1)/sqrt(sqr(XApp2-XApp1)+sqr(YApp2-YApp1)+sqr(ZApp2-ZApp1)); //координата Y для нужной части отрезка
          ZApp3:= ZApp1+prirost*(ZApp2-ZApp1)/sqrt(sqr(XApp2-XApp1)+sqr(YApp2-YApp1)+sqr(ZApp2-ZApp1)); //координата Z для нужной части отрезка

         //проводим нужные операции с новым отрезком "1-3", суммируем все, что получили в предыдущих, считаем что новая ломаная обработана и обнуляем все ненужные переменные

        //отрезок "3-2" зачисляем в следующую ломаную
          LOtr:=sqrt(sqr(XApp3-XApp2)+sqr(YApp3-YApp2)+sqr(ZApp3-ZApp2)); //считаем длину второй части нового отрезка, которая не вошла в предыдущую часть ломаной
         //проводим операции для этого отрезка
        end;
    end;


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

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

Очень прошу помощи!!!
Ответы (3)
ava
_Y_ | 08.02.2013, 23:35 #
Как я понял, ломаная состоит из отрезков разной длины, т.е. из цепочки векторов 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.

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

Ну, вроде ничего не напутал smile 
ava
Dementor | 10.02.2013, 12:16 #
_Y_, огромное спасибо!!! Как сам до этого не дошел до сих пор не понимаю.

Единственное, что изменил в вашем алгоритме - это "если V==P, тогда к пункту 5" - в моей задаче практически невозможно достичь равенства по причине изначального округления координат(в рабочем файле координаты даны с одной точностью, в исходном с другой, в обсчитываемых данных с третьей), поэтому сделал двойное условие - V==P или  P-V<0.00001.
ava
_Y_ | 10.02.2013, 20:06 #
Dementor, извиняюсь - не написал сразу. Учет ошибок измерения или машинной ошибки вроде сам-собой разумеется. Если работать с непрерывными величинами, естественно (с целочисленными, понятное дело, он не нужен). Единственно, двойное условие ни к чему. Если ошибки измерения у Вас не какому-то особому закону соответствуют, то просто считается модуль:
|P-V|<0.00001
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
  Dementor   _Y_
advanced
Отправить