Название: Вписание ломаной линии в дугу кривой.
Отправлено: Марбол от марта 21, 2012, 10:11
Отправлено: Марбол от марта 21, 2012, 10:11
Здравствуйте!
Передо мной встала задача вписания равносторонней ломаной линии (т. е. со звеньями равной длины) в дугу кривой линии, аналитическое выражение которой известно. При этом число звеньев ломаной линии задано в условиях задачи. Может ли это быть выполнено точно? А если требуется применить рекурсивный алгоритм, то в условия можно добавить допустимый предел погрешности координат точек ломаной линии.
Передо мной встала задача вписания равносторонней ломаной линии (т. е. со звеньями равной длины) в дугу кривой линии, аналитическое выражение которой известно. При этом число звеньев ломаной линии задано в условиях задачи. Может ли это быть выполнено точно? А если требуется применить рекурсивный алгоритм, то в условия можно добавить допустимый предел погрешности координат точек ломаной линии.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Тайльнемер от марта 21, 2012, 12:14
Отправлено: Тайльнемер от марта 21, 2012, 12:14
Чё-то я не понял: а кривая как задана?
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Квас от марта 21, 2012, 13:31
Отправлено: Квас от марта 21, 2012, 13:31
В принципе, получается, что если кривая задана уравнением x=φ(t), t ∈[0,1], то надо решить систему
![[tex] |\varphi(t_{i-1}) - \varphi(t_i) |= | \varphi(t_{i}) - \varphi(t_{i+1})| \quad (i=1,\ldots,n-1)[/tex]](https://latex.codecogs.com/png.latex? |\varphi(t_{i-1}) - \varphi(t_i) |= | \varphi(t_{i}) - \varphi(t_{i+1})| \quad (i=1,\ldots,n-1) "|\varphi(t_{i-1}) - \varphi(t_i) |= | \varphi(t_{i}) - \varphi(t_{i+1})| \quad (i=1,\ldots,n-1)")
где
![[tex] 0 = t_0 < t_1 < \ldots < t_{n-1} < t_n = 1,[/tex]](https://latex.codecogs.com/png.latex? 0 = t_0 < t_1 < \ldots < t_{n-1} < t_n = 1, "0 = t_0 < t_1 < \ldots < t_{n-1} < t_n = 1,")
и надо найти неизвестные![[tex]t_i[/tex]](https://latex.codecogs.com/png.latex?t_i "t_i")
. Нелинейная система пугает.
Теоретически, если длина звена известна, можно по точке ti построить ti+1. Тогда, если есть оценка длины звена сверху, можно воспользоваться, например, методом деления пополам, чтобы подобрать нужную длину.
где
и надо найти неизвестные
Теоретически, если длина звена известна, можно по точке ti построить ti+1. Тогда, если есть оценка длины звена сверху, можно воспользоваться, например, методом деления пополам, чтобы подобрать нужную длину.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Alone Coder от марта 21, 2012, 13:43
Отправлено: Alone Coder от марта 21, 2012, 13:43
Что понимается под "вписанием"? Только то, что вершины лежат на кривой?
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Hellerick от марта 21, 2012, 13:47
Отправлено: Hellerick от марта 21, 2012, 13:47
По-моему, гиблое дело.
Только тупым (и не очень) подбором значений.
Задача теоретическая или имеет практическое применение?
Только тупым (и не очень) подбором значений.
Задача теоретическая или имеет практическое применение?
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Квас от марта 21, 2012, 13:54
Отправлено: Квас от марта 21, 2012, 13:54
Вписать всегда можно. Надо только чтобы вершины лежали на кривой. Неважно, есть ли другие общие точки и т. д.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Hellerick от марта 21, 2012, 13:55
Отправлено: Hellerick от марта 21, 2012, 13:55
Иногда можно вписать несколькими способами при разной суммарной длине.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Марбол от марта 21, 2012, 21:42
Отправлено: Марбол от марта 21, 2012, 21:42
Здравствуйте!
В моем случае, дуга кривой выпуклая, то есть все её точки лежат по одну сторону от хорды, стягивающей концы дуги. Впрочем, это не принципиальное ограничение.
Для меня эта задача - промежуточная; при этом она имеет практическое значение.
В принципе, я уже разработал и апробировал рекурсивный алгоритм, по которому абсциссы (и отсюда - ординаты) вершин ломаной находятся сравнительно быстро и с заданной точностью; это оказалось просто. Но этот алгоритм подразумевает, что ломаная имеет четное число звеньев; немного подкорректировав, можно будет работать и с нечетным числом.
А для четного числа принцип можно изложить так. Допустим, у нас в координатах XOY есть дуга ABC (B - одна из ее точек) и ломаная AC (вписана в дугу, но имеет одно звено). Надо найти абсциссу точки D, лежащей на дуге и такой, что AD = DC. Как только найдется такая точка D, мы получим искомую ломаную ADC с 21 звеньями. Далее можно удваивать число звеньев, повторно применяя этот алгоритм отдельно к каждому звену и получая равнобочную 2N-звенную ломаную, вписанную в данную дугу.
Лично я искал точку D таким образом, путем последовательных приближений.
1) Задается произвольная точка D0, лежащая на дуге. Получаем отправную двузвенную неравнобочную ломаную.
2) Вычисляются длины звеньев L1 и L2, а также углы ф1 и ф2 их наклона к оси абсцисс. Затем находится полусумма длин L12 = 1/2(L1 + L2) (т. е. средняя длина звена), затем - разность между L1 и L12, т. е. "дефект" между отправной и искомой ломаными:
C1 = L1 - L12.
Но искомая ломаная может иметь другую суммарную длину, чем отправная ломаная, поэтому "дефект" найден сейчас в первом приближении и его надо уточнять при каждой последующей итерации.
3) Если C1 = 0, то уточнения не нужны, решение готово.
Если C1 < 0, то левое звено короче среднего, а правое - длиннее; лучше укоротить правое звено. Селаем это, сдвинув абсциссу средней точки D0 вправо на величину C1 cos ф2.
А если C1 > 0, то длиннее оказалось левое звено; сокращаем его, сдвинув абсциссу точки D0 влево на величину C1 cos ф1.
4) Сдвинув абсциссу точки D0, мы получили новую точку D1, тоже лежащую на дуге. При этом получили и новую неравнобочную ломаную.
Теперь можно повторять все операции пунктов 2 и 3 до тех пор, пока дефект C не станет меньше заданного предела.
В моем случае, дуга кривой выпуклая, то есть все её точки лежат по одну сторону от хорды, стягивающей концы дуги. Впрочем, это не принципиальное ограничение.
Для меня эта задача - промежуточная; при этом она имеет практическое значение.
В принципе, я уже разработал и апробировал рекурсивный алгоритм, по которому абсциссы (и отсюда - ординаты) вершин ломаной находятся сравнительно быстро и с заданной точностью; это оказалось просто. Но этот алгоритм подразумевает, что ломаная имеет четное число звеньев; немного подкорректировав, можно будет работать и с нечетным числом.
А для четного числа принцип можно изложить так. Допустим, у нас в координатах XOY есть дуга ABC (B - одна из ее точек) и ломаная AC (вписана в дугу, но имеет одно звено). Надо найти абсциссу точки D, лежащей на дуге и такой, что AD = DC. Как только найдется такая точка D, мы получим искомую ломаную ADC с 21 звеньями. Далее можно удваивать число звеньев, повторно применяя этот алгоритм отдельно к каждому звену и получая равнобочную 2N-звенную ломаную, вписанную в данную дугу.
Лично я искал точку D таким образом, путем последовательных приближений.
1) Задается произвольная точка D0, лежащая на дуге. Получаем отправную двузвенную неравнобочную ломаную.
2) Вычисляются длины звеньев L1 и L2, а также углы ф1 и ф2 их наклона к оси абсцисс. Затем находится полусумма длин L12 = 1/2(L1 + L2) (т. е. средняя длина звена), затем - разность между L1 и L12, т. е. "дефект" между отправной и искомой ломаными:
C1 = L1 - L12.
Но искомая ломаная может иметь другую суммарную длину, чем отправная ломаная, поэтому "дефект" найден сейчас в первом приближении и его надо уточнять при каждой последующей итерации.
3) Если C1 = 0, то уточнения не нужны, решение готово.
Если C1 < 0, то левое звено короче среднего, а правое - длиннее; лучше укоротить правое звено. Селаем это, сдвинув абсциссу средней точки D0 вправо на величину C1 cos ф2.
А если C1 > 0, то длиннее оказалось левое звено; сокращаем его, сдвинув абсциссу точки D0 влево на величину C1 cos ф1.
4) Сдвинув абсциссу точки D0, мы получили новую точку D1, тоже лежащую на дуге. При этом получили и новую неравнобочную ломаную.
Теперь можно повторять все операции пунктов 2 и 3 до тех пор, пока дефект C не станет меньше заданного предела.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Квас от марта 21, 2012, 22:06
Отправлено: Квас от марта 21, 2012, 22:06
Не пойдёт. Например, вы построите ADC с AD=DC. Потом вы построите AEDFC с AE=ED, DF=FC. Но вообще говоря ED ≠ DF.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Марбол от марта 22, 2012, 05:16
Отправлено: Марбол от марта 22, 2012, 05:16
Верно... Тем более, что в итоге получается не просто четное число звеньев, а равное степени двойки. С другой стороны, мою схему вполне можно видоизменить: отправная ломаная может содержать не два звена, а произвольное количество; тогда на каждом шаге будут вычисляться дефекты во всех внутренних вершинах ломаной, и корректироваться звенья будут с учетом друг друга.
Я сегодня испытаю этот алгоритм и посмотрю, насколько он хорош.
А с другой стороны, требование равенства всех звеньев - слишком сильное; для моих целей вполне достаточно будет, если длины звеньев мало отличаются от среднего значения, а равны только по два соседних звена: 1-ое = 2-ому, 3-ье = 4-ому и т. д.
Я сегодня испытаю этот алгоритм и посмотрю, насколько он хорош.
А с другой стороны, требование равенства всех звеньев - слишком сильное; для моих целей вполне достаточно будет, если длины звеньев мало отличаются от среднего значения, а равны только по два соседних звена: 1-ое = 2-ому, 3-ье = 4-ому и т. д.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Марбол от марта 23, 2012, 05:50
Отправлено: Марбол от марта 23, 2012, 05:50
Здравствуйте!
Вчера, к сожалению, не нашлось возможности провести расчеты.
Вчера, к сожалению, не нашлось возможности провести расчеты.
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Марбол от апреля 19, 2012, 21:11
Отправлено: Марбол от апреля 19, 2012, 21:11
Здравствуйте!
В начале я описывал способ вписания двузвенной ломаной в участок кривой:
Теперь я, наконец, обобщил этот алгоритм на случай произвольного числа звеньев, написал программу на VBA (Visual Basic for Applications) и провел поверочные расчеты для нескольких кривых, гладких, кусочно-гладких и кусочно-непрерывных. В целом, всё считается хорошо: с задаваемой точностью, в задаваемом диапазоне изменения аргумента, при задаваемом числе звеньев ломаной, в кратчайшее время и со сравнительно малым числом итераций (<10000).
В начале я описывал способ вписания двузвенной ломаной в участок кривой:
Цитата: Марбол от марта 22, 2012, 05:16
С другой стороны, мою схему вполне можно видоизменить: отправная ломаная может содержать не два звена, а произвольное количество; тогда на каждом шаге будут вычисляться дефекты во всех внутренних вершинах ломаной, и корректироваться звенья будут с учетом друг друга.
Теперь я, наконец, обобщил этот алгоритм на случай произвольного числа звеньев, написал программу на VBA (Visual Basic for Applications) и провел поверочные расчеты для нескольких кривых, гладких, кусочно-гладких и кусочно-непрерывных. В целом, всё считается хорошо: с задаваемой точностью, в задаваемом диапазоне изменения аргумента, при задаваемом числе звеньев ломаной, в кратчайшее время и со сравнительно малым числом итераций (<10000).
Название: Вписание ломаной линии в дугу кривой.
Отправлено: Марбол от мая 16, 2012, 22:05
Отправлено: Марбол от мая 16, 2012, 22:05
Здравствуйте!
Коротко говоря, решил нелинейную задачу "методом хорд".
Коротко говоря, решил нелинейную задачу "методом хорд".