Просто решите куб.
Если вы говорите о плоских кривых Безье, где x (t) и y (t) являются кубическими полиномами, то y (x) может быть неопределенным или иметь несколько значений. Экстремальным вырожденным случаем будет линия x = 1.0, которая может быть выражена в виде кубического Безье (контрольная точка 2 совпадает с конечной точкой 1; контрольная точка 3 совпадает с конечной точкой 4). В этом случае y (x) не имеет решений для x! = 1.0, а бесконечные решения для x == 1.0.
Метод рекурсивного деления будет работать, но я ожидаю, что он будет намного медленнее, чем просто решение кубического. (Если вы не работаете с каким-то встроенным процессором с необычно низкой пропускной способностью с плавающей запятой.)
У вас не должно возникнуть проблем с поиском кода, который решает куб, который уже был тщательно протестирован и отлажен. Если вы реализуете свое собственное решение с использованием рекурсивного подразделения, у вас не будет этого преимущества.
Наконец, да, могут быть проблемы со стабильностью чисел, например, когда нужная точка находится вблизи касательной, но метод деления не заставит их исчезнуть. Это просто сделает их менее очевидными.
РЕДАКТИРОВАТЬ : отвечая на ваш комментарий, но мне нужно более 300 символов.
Я имею дело только с кривыми Безье, где у (х) есть только один (реальный) корень. Что касается численной устойчивости, используя формулу из http://en.wikipedia.org/wiki/Cubic_equation#Summary,, может показаться, что могут быть проблемы, если u очень мало. - jtxx000
Статья Wackypedia - математика без кода. Я подозреваю, что вы можете найти код кулинарной книги, который более готов к использованию где-нибудь. Может быть, числовые рецепты или собранные 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, глядя на то, сколько ошибок вносится для каких величин. Конечно, только вы знаете, сколько точности вам нужно.
В статье приведены 3 формулы для u для 3 корней кубики. Учитывая три значения u, вы можете получить 3 соответствующих значения x. Все 3 значения для u и x являются комплексными числами с мнимым компонентом. Если вы уверены , что должно быть только одно реальное решение, то вы ожидаете, что один из корней будет иметь нулевую мнимую компоненту, а два других будут комплексными сопряженными. Похоже, вы должны вычислить все три, а затем выбрать реальный. (Обратите внимание, что комплекс u может соответствовать действительному x!) Однако есть еще одна проблема численной устойчивости: арифметика с плавающей точкой, какой она есть, мнимая составляющая реального решения не будет точно равна нулю, а мнимая составляющая нереальные корни могут быть сколь угодно близко к нулю. Таким образом, округление чисел может привести к неправильному корню. Было бы полезно, если бы в вашем приложении была какая-то проверка работоспособности, которую вы могли бы применить там.
Если вы выберете правильный корень, одна или несколько итераций Ньютона-Рафсона могут значительно повысить его точность.