Алгоритм вставки точек в кусочно-кубический путь Безье - PullRequest
Новая
       71

Алгоритм вставки точек в кусочно-кубический путь Безье

14 голосов
/ 10 апреля 2010

Я ищу алгоритм для вставки новой контрольной точки на кривую Безье, без деформации.

Кто-нибудь знает библиотеку или справочник по алгоритмам Безье (вставка, оптимизация, де Кастельжау ...)?

Ответы [ 3 ]

22 голосов
/ 10 апреля 2010

Это называется "проблемой вставки узла". Для кривых Безье алгоритм де Кастельжау даст правильный ответ. Вот простой алгоритм для степени 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, которое близко к желаемой точке разделения ... Но если производительность критична, вы, вероятно, сможете найти более быстрое аналитическое решение.

2 голосов
/ 06 ноября 2014

Вы также можете использовать математический подход.

Квантовая кривая Безье с контрольными точками p_1,p_2,p_3,p_4 может быть записана как:

b(t)=(1-t)^3 p_1+3t(1-t)^2 p_2+3t^2 (1-t) p_3+t^3 p_4

его производная w.r.t. t это

\frac{\partial b}{\partial t} = 3(1-t)^2 (p_2-p_1 )+6t(1-t)(p_3-p_2 )+3t^2 (p_4-p_3 )

Чтобы ограничить кривую от t0 до t1, вы получаете новые контрольные точки q_1,q_2,q_3,q_4:

q_1=b(t_0),q_4=b(t_1)

q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}

q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}

Доказательство

Подставив

s=\frac{t-t_0}{t_1-t_0}

t=t_0+s(t_1-t_0 )

Получаем

\frac{\partial b}{\partial s} = \frac{\partial b}{\partial t} \frac{\partial t}{\partial s} = (t_1-t_0) \frac{\partial b}{\partial t}

Первая и последняя точки подкривой являются первой и последней новыми контрольными точками

q_1=b(t_0),q_4=b(t_1)

И касательная в этих точках равна

\frac{\partial{b}}{\partial{s}}_{(s=0)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}=3(q_2-q_1)

\frac{\partial{b}}{\partial{s}}_{(s=1)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}=3(q_4-q_3)

So

q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}

q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}

1 голос
/ 16 марта 2015

Добавление для полноты.

Реализацию с открытым исходным кодом многих операций пути Безье можно найти внутри GIMP исходного кода, в gimpbezierstroke.c. Чтобы узнать, как вставить новый якорь, выполните поиск gimp_bezier_stroke_anchor_insert.

.
...