|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 17 Jan 2002 06:07:53
To : "Nick Gorev"
Subject : Re: Пересечение тора с отрезком
--------------------------------------------------------------------------------
До меня дошли слухи, что *16.01.02* *18:24:07* пролетало сообщение
от Nick к *All* про *"Пересечение тора с отрезком"*. И я решил вмешаться.
[...]
U> Я пытаюсь решить эту задачу так: Параметрическое уравнение отрезка
U> подставляю в уравнение тора. Получаю алгебраическое уравнение 4-й степени.
U> Теперь надо узнать, имеет ли это уравнение решение на заданном отрезке
U> изменения параметра (отрезок [0..1]). Если кто-нибудь знает быстрый
U> алгоритм для этого - поделитесь. Для этого есть способ - построение
U> системы Штурма - но он слишком громоздкий. Может кто-нибудь посоветует
U> что-нибудь попроще. А может быть вообще эту задачу следует решать другим
U> способом?
Вообще корни любого многочлена можно отыскать тупым численным методом.
1. Корни многочелена находятся между корнями производной(но не обратно), при
этом кратные корни совпадают с корнями производной.
2. Таким образом если мы занем корни производной наш отрезок [0,1] разбивается
на
кучу отрезков, на каждом из которых либо один, либо ноль корней. А корни
производной
можно найти рекурсивно, спустившись до полинома второй, или если хочешь первой
степени.
3. Теперь о поиске корня на отрезке [a,b], если P(a)*P(b)>0, то корней на этом
отрезке
нет, если же P(a)*P(b)=0, то либо a, либо b - корень. Теперь если P(a)*P(b)<0.
То
рассмотрим точку c=(a+b)/2, если P(a)*(c)>0, то корень отрезке [c,b], в
противном случае
на отрезке [a,c]. Теперь проделаем то же самое для нового осрезка, и так до тех
пока
расстояние от a до b, не станет меньше фиксированого эпсилон, которое
выбирается в
зависимости от того с какой точностью тебе нужен корень. Так вот как только
b-a<eps, то
объявляем a корнем.
Способ простой, достаточно точный, и бытрый, тем более для полинома 4 степени,
тебе достатточно найти корни полинома 3.
Вообще вроде есть формулы для корней полиномов 3,4 степеней, можешь их
попробовать.
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Металл сила - всем рэперам могила. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Пересечение тора с отрезком 
