|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anton Vdovichenko 2:5025/3.8 02 Dec 2002 00:36:57
To : Georgy Udov
Subject : Параметрическая кривая
--------------------------------------------------------------------------------
01 Dec 30 16:22, Georgy Udov wrote to Anton Vdovichenko:
GU> Спасибо большое за информацию. Только ещё несколько вопросов:
GU> 1) Так как на каждом узловом интервале полиномы А(t) и B(t) разные, то
GU> уравнение нужно решать для каждого интервала, а потом, если получим t,
GU> выходящее за границы данного интервала, - это решение отсекать? Или
GU> можно сначала как-нибудь прикинуть, на каком узловом интервале
GU> находится заданная точка?
Вообще то количество интервалов у подавляющего числа кривых, с которыми я
работал - 1, 2. Hо, конечно, встречаются кривые и с большим числом интервалов,
например - спираль с 10 витками ( у нее интервалов >100), для нее у меня точки
искались достаточно долго ( 900 точек за ~5 сек, на Duron 650 ). Для этого
случая у меня была идея построить для кусков кривой из каждого интервала свой
ограничивающий параллепипед и сначала проверять принадлежит ли точка ему, но о
реальности реализации сказать ничего не могу - руки не дошли...
AV>> Для третьей можно тоже аналитическое решение написать. А так, для
AV>> общего случая, решается методом дихотомии, концы интервала ведь
GU> По-моему, аналитически можно решить и для четвёртой степени. То есть,
GU> дихотомия годится только до пятой. Дальше дифференцированное уравнение
GU> станет решать сложно - надо будет и его дифференцировать... Конечно,
GU> можно написать рекурсивную функцию, решающую уравнение дихотомией,
GU> только тогда возникнет другой вопрос - а не будет ли это менее
GU> эффективно, чем какой-нибудь итерационный метод...
Hасколько я знаю, реально используются только кубические сплайны, да и то,
случаи когда степень равна 3 достаточно редки, в основном 2-я. По крайней мере
это верно для той геометрии которая импортируется из большинства CAD систем (в
основном работал с геометрией из SolidWorks ). Hо в принципе у меня есть опыт и
по решению уравнений большей степени. Hапример когда ищешь расстояние от точки
до кривой, то там степень вырастала до 9. Я реализовывал именно рекурсивный
алгоритм - работает достаточно шустро.
В принципе можно приблизительно оценить затраты дихотомии и прямого поиска для
степени k: если длина интервала d, а шаг с которым ты будешь искать e, то при
прямом поиске число вычислений функции будет n=d/e, а для дихотомии <
(k^2)*log2(n). Т.ч. выбирай сам :) Возможно есть какой-нибудь лучший метод, но я
его не знаю. Для меня, при реализации решающим фактором было то, что дихотомия
гарантированно находит все корни с заданой точностью.
Anton
--- GoldED 2.50+
* Origin: ... (2:5025/3.8)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
