Вписание ломаной линии в дугу кривой.

[Марбол]

Здравствуйте!

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

[Тайльнемер]

Чё-то я не понял: а кривая как задана?

[Квас]

В принципе, получается, что если кривая задана уравнением x=φ(t), t ∈[0,1], то надо решить систему

где

и надо найти неизвестные . Нелинейная система пугает.

Теоретически, если длина звена известна, можно по точке t_i построить t_i+1. Тогда, если есть оценка длины звена сверху, можно воспользоваться, например, методом деления пополам, чтобы подобрать нужную длину.

[Alone Coder]

Что понимается под "вписанием"? Только то, что вершины лежат на кривой?

[Hellerick]

По-моему, гиблое дело.
Только тупым (и не очень) подбором значений.

Задача теоретическая или имеет практическое применение?

[Квас]

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

[Hellerick]

Иногда можно вписать несколькими способами при разной суммарной длине.

[Марбол]

Здравствуйте!

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

   А для четного числа принцип можно изложить так. Допустим, у нас в координатах XOY есть дуга ABC (B - одна из ее точек) и ломаная AC (вписана в дугу, но имеет одно звено). Надо найти абсциссу точки D, лежащей на дуге и такой, что AD = DC. Как только найдется такая точка D, мы получим искомую ломаную ADC с 2¹ звеньями. Далее можно удваивать число звеньев, повторно применяя этот алгоритм отдельно к каждому звену и получая равнобочную 2^N-звенную ломаную, вписанную в данную дугу.
   Лично я искал точку D таким образом, путем последовательных приближений.
1) Задается произвольная точка D₀, лежащая на дуге. Получаем отправную двузвенную неравнобочную ломаную.
2) Вычисляются длины звеньев L₁ и L₂, а также углы ф₁ и ф₂ их наклона к оси абсцисс. Затем находится полусумма длин L₁₂ = 1/2(L₁ + L₂) (т. е. средняя длина звена), затем - разность между L₁ и L₁₂, т. е. "дефект" между отправной и искомой ломаными:

C₁ = L₁ - L₁₂.

Но искомая ломаная может иметь другую суммарную длину, чем отправная ломаная, поэтому "дефект" найден сейчас в первом приближении и его надо уточнять при каждой последующей итерации.
3) Если C₁ = 0, то уточнения не нужны, решение готово.
Если C₁ < 0, то левое звено короче среднего, а правое - длиннее; лучше укоротить правое звено. Селаем это, сдвинув абсциссу средней точки D₀ вправо на величину C₁ cos ф₂.
А если C₁ > 0, то длиннее оказалось левое звено; сокращаем его, сдвинув абсциссу точки D₀ влево на величину C₁ cos ф₁.
4) Сдвинув абсциссу точки D₀, мы получили новую точку D₁, тоже лежащую на дуге. При этом получили и новую неравнобочную ломаную.
Теперь можно повторять все операции пунктов 2 и 3 до тех пор, пока дефект C не станет меньше заданного предела.

[Квас]

Не пойдёт. Например, вы построите ADC с AD=DC. Потом вы построите AEDFC с AE=ED, DF=FC. Но вообще говоря ED ≠ DF.

[Марбол]

Верно... Тем более, что в итоге получается не просто четное число звеньев, а равное степени двойки. С другой стороны, мою схему вполне можно видоизменить: отправная ломаная может содержать не два звена, а произвольное количество; тогда на каждом шаге будут вычисляться дефекты во всех внутренних вершинах ломаной, и корректироваться звенья будут с учетом друг друга.
Я сегодня испытаю этот алгоритм и посмотрю, насколько он хорош.

А с другой стороны, требование равенства всех звеньев - слишком сильное; для моих целей вполне достаточно будет, если длины звеньев мало отличаются от среднего значения, а равны только по два соседних звена: 1-ое = 2-ому, 3-ье = 4-ому и т. д.

[Марбол]

Здравствуйте!

Вчера, к сожалению, не нашлось возможности провести расчеты.

[Марбол]

Здравствуйте!

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

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

Теперь я, наконец, обобщил этот алгоритм на случай произвольного числа звеньев, написал программу на VBA (Visual Basic for Applications) и провел поверочные расчеты для нескольких кривых, гладких, кусочно-гладких и кусочно-непрерывных. В целом, всё считается хорошо: с задаваемой точностью, в задаваемом диапазоне изменения аргумента, при задаваемом числе звеньев ломаной, в кратчайшее время и со сравнительно малым числом итераций (<10000).

[Марбол]

Здравствуйте!

Коротко говоря, решил нелинейную задачу "методом хорд".