Разбить кубическую кривую Безье в точке

Question

Этот вопрос и этот вопрос показывают, как разделить кубическую кривую Безье при конкретном параметризованном значении 0 ≤ t ≤ 1 вдоль кривой, составив исходную форму кривой из двух новых сегментов. Мне нужно разделить мою кривую Безье в точке вдоль кривой, координату которой я знаю, но не в параметризованном значении t для этой точки.

Например, рассмотрим Adobe Illustrator, где пользователь может щелкнуть по кривой, чтобы добавить точку в траекторию, не влияя на форму контура.

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

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

---

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

Answer 1

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

Одним из возможных и довольно простых способов является использование метода Ньютона таким образом, что:

t _n+1 = t_n - ( b_x(t_n) - c_x ) / b_x'(t_n)

Где b _x(t) относится к компоненте x некоторой кривой Безье в полиномиальной форме с контрольными точками x ₀ , x ₁ , x ₂ и x ₃ , b _x '(t) - первая производная, а c_x - точка на кривой так, что:

с Икс знак равно б _{Икс ( т} ) | 0 < т < 1

коэффициенты b _x(t) :

A = -x₀ + 3x₁ - 3x₂ + x₃
B = 3x₀ - 6x₁ + 3x₂
C = -3x₀ + 3x₁
D = x ₀

а также:

b _x (t) = At ^​​3 + Bt² + Ct + D,
b _x'(t) = 3At² + 2Bt + C

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

т _{п знак} равно ( c _Икс - Икс ₀ ) / ( Икс ₃ - Икс ₀ ) | х ₀ < х ₁ < х ₂ < х ₃

Теперь у вас уже есть:

б _х (т _п ) ≈ с _х

Таким образом, применение одной или нескольких итераций метода Ньютона даст лучшее приближение t для c_x .

Обратите внимание, что алгоритм Ньютона Рафсона имеет квадратичную сходимость. В большинстве случаев хорошее начальное значение приведет к незначительному улучшению после двух итераций, то есть менее чем на половину пикселя.

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