Комментарии 6
Буквально на днях занимался кривыми Безье.
Использовал ту самую статью про результант.
Проверку подкривой пока не реализовал, но формулы вроде несложные выходят.
как найти опорные точки кривой, которая является частью исходной кривой в интервале t от t1 до t2?
Разделить исходную кривую методом де Кастельжо, в пропорции t2, а потом первую из полученных частей — в пропорции t1/t2. Вторая кривая после второго разделения — искомая.
Разделить исходную кривую методом де Кастельжо, в пропорции t2, а потом первую из полученных частей — в пропорции t1/t2. Вторая кривая после второго разделения — искомая.
Вы имеете ввиду частный случай квадратичной кривой? Да это так. Для кривых более высокого порядка так не работает. Описанный в заметке метод работает для кривых любого порядка.
но формулы вроде несложные выходят.
Для квадратичной кривой Безье действительно можно и аналитически найти решение. Для более высоких порядков степень результанта растёт как n2. И если всё же заморочиться с поиском корней, то даже для кривой первого порядка аналитического решения может не быть, а пересечение с точностью до R имеется.
Вообще, тут надо искать минимум расстояния между кривыми |B(c1,t1)-B(c2,t2)|2. но это уж точно будет задача не из простых.
Для более высоких порядков
У меня частный случай: все кривые кубические (даже если сводятся к прямой).
Получаются многочлены до 9 степени.
Аналитического решения, естественно, нет. Ищу корни методом Ньютона.
На счёт формул — я имел в виду, вопрос "является ли кривая B частью кривой A".
Исходя из гипотезы, что существуют такие a и b, что B((t-a)/(b-a)) = A(t).
Тупо подставив эту формулу в многочлен (кубический), я получаю четыре уравнения относительно a и b. Одно из этих уравнений — степенное, и решается извлечением корня (кубического или квадратного), другое — линейное, остальные — надо просто проверить, подставив корни.
Но это пока только выкладки, код ещё не писал. Что практика покажет — пока не знаю.
Ах, да, раздельно решаю для каждой проекции, а потом проверяю, совпали ли корни с приемлемой точностью.
Кривые Безье. Немного о пересечениях и как можно проще