Увы, я не знаю ни одного уравнения в замкнутой форме, дающего вам точку (точки), которую вы хотите.Пожалуй, самый простой метод для аппроксимации этой точки - это рекурсивно разрезать кривую Безье на 2 меньшие кривые Безье, используя алгоритм де Кастельжау .Рекурсия заканчивается, когда либо (а) все ограничивающие точки кривой находятся либо слишком близко, либо слишком далеко от заданной точки, либо (б) все ограничивающие точки кривой находятся "достаточно близко", чтобы быть равнымижелаемое расстояние (возможно, они все вписываются в один и тот же пиксель).
Я почти уверен, что максимальное количество точек на данной кривой Безье, которые являются заданным линейным расстоянием от некоторой данной точки, составляет 4 точки.(Это может произойти, когда данная кривая Безье имеет самопересечение).
РЕДАКТИРОВАТЬ:
Возможно, мне следует прочитать весь вопрос, прежде чем перейти с ответом, да?Стандартный «четырехточечный» сегмент кривой Безье можно рассматривать как один кусок бесконечно длинной кубической кривой.В одном месте может быть изгиб, петля или излом, но достаточно далеко от этой крутой кривой путь выравнивается, чтобы приблизиться к 2 прямым лучам, каждый из которых указывает в каком-то произвольном направлении.Увы, вышеприведенное решение находит только точки, которые находятся на коротком отрезке кривой Безье.Я предполагаю, что вам нужны точки (точки) вдоль этой бесконечно длинной кубической кривой, которые находятся на заданном расстоянии от заданной точки, даже если они не находятся на коротком отрезке кривой Безье.
== de Casteljauв обратном направлении ==
Вы можете запустить (рекурсивную среднюю точку) алгоритм де Кастельжау в обратном порядке, генерируя новую четырехточечную кривую Безье, «удваивая» размер последней на каждой итерации, пока не получите достаточно большуювключите желаемый пункт (ы).(Когда все 4 начальные точки находятся «слишком близко» к заданной точке, то гарантируется, что удвоение в конечном итоге приведет к получению сегмента кривой с начальной точкой «слишком близко», конечной точкой «слишком далеко», и тогда вы можете использовать вышеалгоритм сходится в точке, которая является желаемым расстоянием от заданной точки).Этот подход основан только на сложении, вычитании, умножении на два и усреднении, поэтому в принципе он должен быть относительно численно устойчивым.(Он никогда не вычисляет кубическую формулу в любом месте t).
== поиск нуля ==
Вы можете преобразовать четырехточечное представление в кубическое полиномиальное представление и использоватьлюбой алгоритм поиска корня сходится на одной из желаемых точек.Метод Ньютона должен работать довольно хорошо, поскольку короткие отрезки кривой Безье почти прямые.Можем ли мы адаптировать уравнения метода Ньютона из Нахождение минимального расстояния между точкой и кубическим сплайном к этой задаче?Я буду использовать алгоритм деления пополам для простоты описания, хотя он работает медленнее, чем метод Ньютона.
Как всегда, сегмент кубической кривой Безье можно описать как
B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3.
(К сожалению,это уравнение не всегда численно устойчиво - поэтому многие люди используют рекурсивное деление пополам с использованием алгоритма де Кастельжау).
Я предполагаю, что у вас есть (или вы можете найти) значение t_given для вашей заданной точки,
x_given = B(t_given).x
y_given = B(t_given).y
Расстояние между вашей заданной точкой и некоторой другой точкой вдоль кривой определяется какТеорема Пифагора,
distance2(t) = ( x_given - B(t).x )^2 + ( y_given - B(t).y )^2.
distance(t) = sqrt(distance2(t)).
Точки, которые вы ищете, находятся в нулях функции
given_distance2 = given_distance^2.
f(t) = distance2(t) - given_distance2.
Предполагая, что данное расстояние не равно нулю, и данная точкаимеет t_given <1, алгоритм деления пополам будет выглядеть примерно так: </p>
left = t_given
right = 1 // the endpoint of the given Bezier curve segment
while( distance2(right) < given_distance2 ){
right = right*2
}
В этой точке t_left находится ближе к заданной точке, чем желаемое расстояние, а t_right дальше, чем желаемое расстояние (иливозможно, ровно)Поскольку одна точка находится слишком близко, а другая - слишком далеко, алгоритм деления пополам должен работать.
while( (abs(f(right) is too big) AND (abs(left - right) is too big) ){
// find midpoint
midpoint = (t_left + t_right)/2
Далее мы проверяем: содержит ли первый отрезок слева ... средняя точка содержит ноль или среднюю точку .... верно?
if( f(left)*f(midpoint) < 0 ) then
// throw away right half
right = midpoint
else
// throw away left half
left = midpoint
}
return( right )
В этой точке «правильное» значение - это значение t, а B (справа) - соответствующая точка, так что расстояние от этой точки до исходной заданной точки (приблизительно) равно данному расстоянию.