ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serge Kanilo                         2:5020/400     14 May 2001  00:33:30
 To : All
 Subject : Re: пеpесечения
 -------------------------------------------------------------------------------- 
 

 Hi Stepan,
 
 "Stepan Polovnikov" <Stepan.Polovnikov@p47.f16.n5056.z2.fidonet.org> wrote
 in message news:989672398@p47.f16.n5056.z2.FIDOnet.ftn...
 
 > >> ER> А скоpость? Ты их не пpовеpял в деле?
 > >> Геометрическое решение быстрее.
 > SK> Принципиальной разницы нет, поскольку расписанное
 > SK> решение через уравнение второй степени приведет
 > SK> к тому же самому коду.
 >     Разница в скорости. При трассировке в перую очередь важно получать не
 
 само
 
 > решение уравнения, а факт пересечения. Прикинь количество операций и
 
 получишь
 
 > ускорение в 2-3 раза при отсутствии перечесения. Зачем решать уранение,
 
 если
 
 > оно не имеет решения? Что и определяется геометрическими свойствами.
 > SK> Hаправление имеет единичную длину, не так ли?
 > SK> Hе здесь ли кроется причина такой простоты?
 > SK> Ведь в этом случае уравнение будет
 > SK> t^2-2*(c-o)*d*t+(c-o)^2-r^2=0
 >     Hет. При трассировке вектор d единичный, так что уравнение остается
 > прежним. Это свойство используется не только при расчете пересечения со
 
 сферой,
 
 > но и дает значительный выигрыш для других объектов. По крайне мере,
 > нормализация его выполняется один раз. А во всех уравнениях исходят из
 
 расчета
 
 > единичной длины d.
 
 Ладно, с направлением можно согласится, хотя в исходной задаче был трезок.
 Слово "значительный выигрыш" употребляется здесь достаточно часто.
 ИМХО, после подробного анализа часто оказывается, что такой "выигрыш"
 редко превосходит 5%.
 
 > SK> Как раз на корень и несколько умножений отличается
 > SK> от исходной задачи.
 >     В общем случае трассировки - нет.
 > SK> А вот вроде и формула для вычисления корня.
 >     Согласно литературе.
 > Решение             Аддитивные Мультипликативне
 > Алгоритмическое        17           15
 > Геометрическое         16           13
 
 В настоящем геометрическом решении используются операции
 типа "приложить линейку и провести линию через две точки",
 "провести окружность с центром в такой-то точке".
 И никаких аддитивных и мультипликативных, это же геометрия :).
 
 >     "The important difference is that the rejection tests are done much
 
 earlier
 
 > in the process, making the overall cost of this algorithm lower on
 
 average."
 
 От того что это написано на английском, это не становится правдой.
 Отсев комплексных решений идет на том же шаге - проверка знака
 детерминанта, и абсолютно все операции тождественны.
 Если кто-то написал два решения - одно хуже а другое лучше и назвал
 одно "алгоритмическим", а другое - "геометрическим", то это не значит,
 что он был пророком. И я совсем не согласен с такой трактовкой.
 Если в геометрическом решении нужна одна точка, то и в алгоритмическом
 надо сказать, что ищется один из корней. И тогда все станет на место,
 потому что главное различие здесь не в методе, а в том, что один
 из них явно ставится в более жесткие условия чем другой. Как насчет
 если я потребую, чтобы геометрический метода определял обе точки
 пересечений и сравнивал расстояние до них? А аналитическому позволю искать
 наименьший положительный действительный корень - кто тогда
 окажется в выигрыше?
 Кстати в такой постановке я могу сразу отсеять еще часть решений как
 явно ложные
 
 bool ...(.....,double*t){
 ....
 l=c-o
 l2=l*l
 ld=l*d     // это то же, что и tca
 if(r2<l2){ // просто перестановка проверок
   if(ld<0) return false // а вот здесь отсекаются два отрицательных корня
   det =ld*ld+r2-l2 // это еще может быть отрицательно
   if (det<0) return false
   *t =ld-sqrt(det)
   }
 else {
   det =ld*ld+r2-l2 // здесь и так ясно, что положительно
   *t =ld+sqrt(det)
   }
 return true
 }
 
 (я особо знаки не проверял :)
 
 > SK> Если бы еще знать, что такое l2.
 >     Потерялся l2=l*l ;)
 > >> return t;
 > SK> Странно, программка то bool возвращает, то double, что за язык такой?
 
 :-)
 
 >     asm ;)
 > SK> Просто непонятно, что возвращается и как его потом анализировать.
 >     Если вернулся false (т.е. 0), то нет пересечения, иначе расстояние до
 > объекта - t.
 
 Т.е. 0.0. Или это все в целочисленной арифметике.
 А если мы вплотную к объекту? :) Hу да ладно, это вопрос философский.
 
 Я весь разговор затеял к тому, что в данной задаче оба подхода
 идентичны, а тонкости несущественны. В отличие например от
 заметных различий например в быстром и простом преобразовании
 Фурье, методе Якоби  и QR алгоритме для определения собственных
 значений симметричных матриц.
 
 Cheers,
 
 Serge
 
 --- ifmail v.2.15dev5
  * Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: пеpесечения   Serge Kanilo   14 May 2001 00:33:30   пеpесечения   Stepan Polovnikov   14 May 2001 21:05:30