Как нарисовать цепную линию

Когда мне понадобилось рисовать нити между воздушными шарами в Balloon Platform Defense, пришлось разобраться, как нарисовать нить, висящую между двумя точками, — форму, известную как цепная линия. Все примеры, которые я нашёл в интернете, либо упрощали задачу, например помещая обе точки на одну высоту, либо предполагали знание того, что здесь неизвестно, например угла, под которым начинается нить. Известны только начальная и конечная точки нити и её длина. В Википедии много сведений об уравнениях цепной линии, и с них я начал. Уравнение цепной линии:
Здесь предполагается, что самая низкая точка нити лежит там, где она пересекает ось y. На практике к x и y добавляются константы, которые тоже нужно найти, ведь мы не знаем, где окажется самая низкая точка, — это одна из причин, почему задача сложнее любых примеров из учебника. (Вы замечали, что математические задачи из реальной жизни всегда гораздо сложнее примеров из учебника? Я всё ещё жду реальной задачи с интегралом, который берётся аналитически.) Но это подождёт, потому что сначала нужно найти значение a — константы в уравнении, которая, по сути, определяет, насколько узкой или широкой будет кривая. Осторожно: если точки находятся в одном и том же месте оси x, то a бесконечно. Этот случай нужно обработать до того, как вы дойдёте до этого места, — как и случай, когда точки так близки, что a становится невычислимо большим. (Помните, что «невычислимо большое» здесь — это любое число, которое в качестве аргумента показательной функции при используемой точности чисел с плавающей запятой дало бы NaN или бесконечность.) И конечно, ваш код вообще не должен доходить до этого места, если точки находятся дальше друг от друга, чем длина нити, — результат был бы бессмысленным.

Вычисление масштабного множителя

Для вычисления a Википедия даёт следующее уравнение (оно основано на свойстве цепной линии: если cosh задаёт положение кривой, то sinh задаёт её длину):
Здесь s — длина нити, а h и v — горизонтальное и вертикальное расстояния (по модулю) между начальной и конечной точками. Всё это известные величины, так что неизвестная остаётся одна, но найти её можно только численно. Сначала я пробовал делать это, не заботясь о начальном приближении, и сходился ли метод, было делом случая. К счастью, хорошее начальное приближение найти несложно. Ряд Тейлора для гиперболического синуса:
После подстановок u = \frac{1}{4a^{2}} и c = \sqrt{s^{2}-v^{2}} решаемое уравнение принимает вид:
Если взять первые три члена ряда Тейлора для sinh и упростить, получим:



Это простое квадратное уравнение относительно u, и если подставить его коэффициенты в знакомую со школы формулу корней квадратного уравнения , получится хорошее начальное приближение для u, а значит, и для a. Это приближение достаточно близко, чтобы найти решение методом Ньютона. В форме имеем и Поскольку , Сейчас я проверяю, отличается ли очередной член последовательности от предыдущего меньше чем на 0,001. Обычно это происходит через 2–4 итерации, но иногда, когда x-координаты ближе друг к другу, требуется больше десяти. Методы Хаусхолдера более высокого порядка, вероятно, можно было бы применить без особых дополнительных затрат, потому что основная часть вычислений приходится на гиперболические функции, а дальнейшие производные функции должны давать лишь новые кратные этих же величин. Теперь, когда масштаб известен, можно вычислить смещение.

Вычисление смещения

Стандартное уравнение предполагает, что цепная линия симметрична относительно оси y и её самая низкая точка находится в (0,a), тогда как та, которую мы рисуем, может оказаться где угодно на экране. Значит, нужно найти смещение (p,q), которое поставит её на нужное место. Наше уравнение становится таким: (Напомню: a к этому моменту известно, x и y — переменные, так что неизвестными остаются только p и q.) Сначала я хотел подставить в уравнение известные значения x и y, то есть две конечные точки нити. Теоретически это работает, но получающиеся уравнения, несмотря на все попытки их упростить по ходу дела, часто давали промежуточные значения, с которыми не справлялись числа двойной точности. В итоге пришлось найти другой путь, который к тому же оказался эффективнее. Вспомним: если в уравнении цепной линии заменить cosh на sinh, получится длина кривой. Подставив в эту форму x-координаты левой и правой конечных точек вместе с известной нужной длиной нити (s), получаем уравнение: Одно из тождеств гиперболических функций гласит: Следовательно: В аргументе cosh правая и левая x-координаты складываются и делятся на 2, что даёт координату середины, так что их можно сразу ею заменить. Разность в аргументе sinh — та самая величина, которую мы раньше назвали h, поэтому и это значение sinh вычисляется как известная величина. Тогда исходное уравнение можно переписать так: Теперь можно найти p с помощью обратного гиперболического косинуса, но здесь нужна осторожность. Поскольку cosh — чётная функция, мы всегда получаем положительное решение, но есть и отрицательное, то есть у p два возможных значения. Какое из них нужно, подскажут y-координаты конечных точек. Опыт с куском верёвки показывает: при той же длине нити и тех же x-координатах самая низкая точка кривой (если она вообще лежит между x-координатами) находится правее середины — то есть соответствует положительному значению обратного гиперболического косинуса, — когда правая y-координата ниже левой, и наоборот. Ещё одна проблема может возникнуть, когда y-координаты равны: тогда самая низкая точка кривой должна быть ровно посередине, аргумент cosh должен быть равен нулю, а значение, от которого берётся обратный гиперболический косинус, — единице. Из-за неточностей вычислений с плавающей запятой часто получается чуть меньше единицы, и обратный гиперболический косинус не вычисляется. Поэтому разумно перед этим вычислением проверить, равны ли (или почти равны) y-координаты, — это экономит время и позволяет избежать ошибки, — и в таком случае просто считать, что p находится ровно посередине между конечными точками. Теперь, когда a и p известны, можно вычислить q, подставив значения x и y одной из конечных точек в уравнение и переписав его так: Вычислите отсюда q — и у вас есть окончательное уравнение, по которому можно нарисовать кривую. Нарисовать кривую теперь просто. На большинстве шагов вычисления параметров я вычислял гиперболические функции как можно точнее, потому что трудно было предсказать, как будут распространяться погрешности. Но на этом последнем шаге, на который приходится большая часть вычислений, вы знаете, насколько велик используемый аргумент и какую погрешность можете себе позволить, и можете предсказать, будет ли ряд Тейлора до определённой степени достаточно точным, — и, по моему опыту, обычно он того стоит.