Как лучше всего аппроксимировать кубическую кривую Безье? В идеале мне нужна функция y (x), которая давала бы точное значение y для любого заданного x, но это потребовало бы решения кубического уравнения для каждого значения x, что слишком медленно для моих нужд, и могут возникнуть проблемы с численной стабильностью также с этим подходом.
Будет ли это хорошим решением?
Просто решите кубический.
Если вы говорите о плоских кривых Безье, где x (t) и y (t) - кубические многочлены, тогда y (x) может быть неопределенным или иметь несколько значений. Крайним вырожденным случаем может быть линия x = 1.0, которую можно выразить как кубическую точку Безье (контрольная точка 2 такая же, как конечная точка 1; контрольная точка 3 такая же, как конечная точка 4). В этом случае y (x) не имеет решений для x! = 1.0 и бесконечных решений для x == 1.0.
Метод рекурсивного подразделения будет работать, но я ожидаю, что он будет намного медленнее, чем простое решение кубики. (Если вы не работаете с каким-то встроенным процессором с необычно плохой емкостью с плавающей запятой.)
У вас не должно возникнуть проблем с поиском кода, который решает кубик, который уже был тщательно протестирован и отлажен. Если вы реализуете собственное решение с использованием рекурсивного подразделения, у вас не будет этого преимущества.
Наконец, да, могут возникнуть проблемы с числовой стабильностью, например, когда нужная точка находится рядом с касательной, но метод подразделения не устранит их. Это просто сделает их менее очевидными.
РЕДАКТИРОВАТЬ: отвечаю на ваш комментарий, но мне нужно более 300 символов.
Я имею дело только с кривыми Безье, где y (x) имеет только один (реальный) корень. Что касается числовой стабильности, используя формулу из http://en.wikipedia.org/wiki/Cubic_equation#Summary, похоже, могут возникнуть проблемы, если u очень мало. - jtxx000
Статья в Вакипедии - это математика без кода. Я подозреваю, что вы можете найти где-нибудь код из поваренной книги, более готовый к использованию. Возможно, числовые рецепты или алгоритмы, собранные ACM, текст ссылки.
На ваш конкретный вопрос и с использованием тех же обозначений, что и в статье, u равно нулю или около нуля, когда p также равно нулю или около нуля. Они связаны уравнением: u^^6 + q u^^3 == p^^3 /27
Около нуля, вы можете использовать приближение: q u^^3 == p^^3 /27
или p / 3u == кубический корень из q
Итак, вычисление x из u должно содержать что-то как:
(fabs(u) >= somesmallvalue) ? (p / u / 3.0) : cuberoot (q)
Насколько «близок» ноль? Зависит от того, какая точность вам нужна. Вы могли бы потратить некоторое время на Maple или Matlab, глядя на то, сколько ошибок вносится для каких величин u. Конечно, только вы знаете, какая точность вам нужна.
В статье приведены 3 формулы для трех корней кубики. Учитывая три значения u, вы можете получить 3 соответствующих значения x. Все 3 значения для u и x - комплексные числа с мнимой составляющей. Если вы уверены, что должно быть только одно реальное решение, то вы ожидаете, что один из корней будет иметь нулевую мнимую составляющую, а два других - комплексно-сопряженные. Похоже, вам нужно вычислить все три, а затем выбрать реальный. (Обратите внимание, что комплексный u может соответствовать действительному x!) Однако здесь есть еще одна проблема численной стабильности: арифметика с плавающей запятой является тем, чем она является, мнимая составляющая реального решения не будет точно равна нулю, а мнимые компоненты невещественные корни могут быть сколь угодно близкими к нулю. Таким образом, округление чисел может привести к неправильному выбору корня. Было бы полезно, если бы в вашем приложении была некоторая проверка работоспособности, которую вы могли бы применить там.
Если вы выберете правильный корень, одна или несколько итераций Newton-Raphson могут значительно улучшить его точность.
Да, алгоритм де Кастельжау подойдет вам. Однако я не знаю, будет ли это быстрее, чем решение кубического уравнения методом Кардано.
t-значений.
- person Hbf; 28.02.2013
