Алгоритм нахождения кривой с касательными на заданных расстояниях вдоль кривой

Question

Я хочу написать (или в идеале найти) алгоритм для расчета приближенной кривой с учетом:

• Начальная и конечная точки
• Касательные на заданных расстояниях вдоль кривой
• Исправлена ​​общая длина кривой

Так что-то вроде начальной точки (x_0, y_0), конечной точки (x_n, y_n) и списка расстояний и углов [(a_0, 0), (a_1, d_1) ... (a_n, d_n)] где a_i - касательная к кривой на расстоянии d_i (вдоль кривой) от (x_0, y_0), а d_n - общее расстояние вдоль кривой от (x_0, y_0) to (x_n, y_n).

Поскольку входные данные будут поступать из реальных данных, точного решения не будет, но подойдет какое-то итеративное приближение.

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

Больше информации о проблеме: На самом деле она в трех измерениях, но диапазон в направлении z намного меньше, чем в x и y, поэтому для простота, я думаю, можно игнорировать. Но для полноты значение z известно в начальной точке, конечной точке и в каждой известной точке касания.

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

В основном я работаю в python, так что, если есть импликация с тупой / неаккуратной привязкой, которая будь идеальным.

Answer 1

Я могу попытаться предложить подход, но есть детали, которые вам нужно выяснить, как это сделать.

Вы ищете кривую C(s) = [C_1(s), C_2(s)] такую, что s - это ее c параметр длины, т.е. length( C(s) ) = s. Вы хотите, чтобы ваш параметр ar c длины составлял от s до go через точки 0, d_1, d_2, ..., d_n и в каждой точке угол между касательной к кривой и горизонтальной осью х был a_0, a_1, a_2, ..., a_n.

В каждом интервале [d_(i-1), d_i] выбрать две точки u_i, v_i, чтобы d_(i-1) < u_i < v_i < d_i. Кроме того, выберите угол b_i.

Установите непрерывную кривую

T(s, u_i, v_i, b_i) = [ T_1(s, u_i, v_i, b_i), T_2(s, u_i, v_i, b_i) ]
                    when s in [d_(i-1), d_i]

, применив следующие формулы:

T_1(s) = cos( a_(i-1) + (b_i - a_(i-1)) * (s - d_(i-1))/(u_i - d_(i-1)) )
T_2(s) = sin( a_(i-1) + (b_i - a_(i-1)) * (s - d_(i-1))/(u_i - d_(i-1)) )
       when s in [d_(i-1), u_i]

T_1(s) = cos( b_i )
T_2(s) = sin( b_i )
       when s in [u_i, v_i]

T_1(s) = cos( b_i + (a_i - b_i) * (s - v_i)/(d_i - v_i)) )
T_2(s) = sin( b_i + (a_i - b_i) * (s - v_i)/(d_i - v_i)) )
       when s in [v_i, d_i]  

Соберите все эти кусочки кривые, дает вам глобальную кривую

T(s, u, v, b) = [ T_1(s, u, v, b),  T_2(s, u, v, b) ]  for s in [d_0, d_n]
              where u = [u_1, u_2,..., u_n], 
                    v = [v_1, v_2,..., v_n],
                    b = [b_1, b_2,..., b_n] 

Обратите внимание, что по определению, для каждого s

norm( T(s, u, v, b) ) = sqrt( T_1(s, u, v, b)^2 + T_2(s, u, v, b)^2 ) = 1
    (because T is defined simply as cos and sin of the same argument)

Это тождество точно соответствует интегральной кривой

D(s, u, v, b) = integral_from(0)_to(s)  T(t, u, v, b) dt

является параметризованной длиной c, то есть length( D(s, u, v, b) ) = s для всех s. Кривая D(s, u, v, b) непрерывно дифференцируема, потому что T(s) непрерывна.

Обратите внимание, что вы можете определить карту

[u, v, b] --> D(d_n, u, v, b)

, и у вас достаточно параметров u = [u_1,...,u_n], v = [v_1,...,v_n] и b = [b_1,...,b_n] чтобы попытаться настроить их так, чтобы

D(d_n, u, v, b) = P_n - P_0

, где P_0 = [x_0, y_0] и P_n = [x_n, y_n], которые даны, были начальной точкой и конечной точкой вашей кривой. Например, обратите внимание, что в каждом подинтервале [u_i, v_i] интегральная кривая равна

D(s) = D(u_i) + s*[cos(b_i), sin(b_i)]

, поэтому это прямая линия. И изогнутые (фактически круглые) части D(s) в интервале [d_(i-1), d_i] сосредоточены в [d_(i-1), u_i] union [v_i, d_i]. Таким образом, чем ближе точки u_i достигают d_(i-1) и v_i до d_i, тем более прямолинейно D(s) выглядит для большей части s. Это позволяет деформировать и манипулировать кривой D(s), чтобы она могла достичь точки P_n - P_0.

В результате, кривая, которая удовлетворяет вашим условиям:

C(s) = P_0 + D(s, u, v, b)

Одна попытка выбрать параметры, чтобы ваша кривая, которая начинается с P_0, также заканчивалась на P_n, могла быть следующее:

попытаться свернуть функцию E(u, v, b) = norm( D(d_n, u, v, b) + P_0 - P_n )^2 относительно параметров [u, v, b]. Вы можете попытаться использовать метод градиентного спуска в попытке достичь параметров, для которых E(u, v, b) = 0.