Алгоритм для вставки точек в кусочно-кубическом пути Bézier

Это называется «проблемой вставки узла». Для кривых Безье алгоритм де Кастельжау даст вам правильный ответ. Вот простой алгоритм для степени Безье 3.

Предположим, вы хотите вставить узел на части t пространства параметров внутри кривой Безье, определенной как P0, P1, P2, P3 . Вот что вы делаете:

P0_1 = (1-t)*P0 + t*P1
P1_2 = (1-t)*P1 + t*P2
P2_3 = (1-t)*P2 + t*P3

P01_12 = (1-t)*P0_1 + t*P1_2
P12_23 = (1-t)*P1_2 + t*P2_3

P0112_1223 = (1-t)*P01_12 + t*P12_23

Тогда ваш первый Безье будет определяться: P_0, P0_1, P01_12, P0112_1223 ; ваш второй Безье определяется: P0112_1223, P12_23, P2_3, P3 .

Геометрическая интерпретация проста: вы разделяете каждый сегмент многоугольника Безье на долю t , затем соединяете эти точки разделения в новый многоугольник и выполняете итерацию. Когда у вас остается 1 точка, эта точка лежит на кривой, а предыдущие / следующие точки разделения образуют предыдущий / следующий многоугольник Безье. Тот же алгоритм работает и для кривых Безье более высокой степени.

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