Аппроксимирующая непараметрическая кубическая Безье

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

Просто решите кубик.

Если вы говорите о плоских кривых Безье, где x (t) и y (t) - кубические полиномы, тогда y (x) может быть неопределенным или иметь несколько значений. Крайним вырожденным случаем может быть линия x = 1.0, которую можно выразить как кубическую точку Безье (контрольная точка 2 совпадает с конечной точкой 1; контрольная точка 3 совпадает с конечной точкой 4). В этом случае y (x) не имеет решений для x! = 1.0 и бесконечных решений для x == 1.0.

Метод рекурсивного подразделения будет работать, но я ожидаю, что он будет намного медленнее, чем простое решение кубики. (Если вы не работаете с каким-либо встроенным процессором с необычно плохой емкостью с плавающей запятой.)

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

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

РЕДАКТИРОВАТЬ: отвечаю на ваш комментарий, но мне нужно больше 300 символов.

I'm only dealing with bezier curves where y(x) has only one (real) root. Regarding numerical stability, using the formula from http://en.wikipedia.org/wiki/Cubic_equation#Summary, it would appear that there might be problems if u is very small. – 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 могут значительно улучшить его точность.