Параметрическая кривая

From

Anton Vdovichenko (2:5025/3.8)

To

Georgy Udov

Date

2002-12-01T23:36:57Z

Area

RU.ALGORITHMS

Hello Georgy.

01 Dec 30 16:22, Georgy Udov wrote to Anton Vdovichenko:


 GU> Спасибо большое за информацию. Только ещё несколько вопросов:
 GU> 1) Так как на каждом узловом интервале полиномы А(t) и B(t) разные, то
 GU> уравнение нужно решать для каждого интервала, а потом, если получим t,
 GU> выходящее за границы данного интервала, - это решение отсекать? Или
 GU> можно сначала как-нибудь прикинуть, на каком узловом интервале
 GU> находится заданная точка?

 Вообще то количество интервалов у подавляющего числа кривых, с которыми я работал - 1, 2. Но, конечно, встречаются кривые и с большим числом интервалов, например - спираль с 10 витками ( у нее интервалов >100), для нее у меня точки искались достаточно долго ( 900 точек за ~5 сек, на Duron 650 ). Для этого случая у меня была идея построить для кусков кривой из каждого интервала свой ограничивающий параллепипед и сначала проверять принадлежит ли точка ему, но о реальности реализации сказать ничего не могу - руки не дошли...

 AV>> Для третьей можно тоже аналитическое решение написать. А так, для
 AV>> общего случая, решается методом дихотомии, концы интервала ведь

 GU> По-моему, аналитически можно решить и для четвёртой степени. То есть,
 GU> дихотомия годится только до пятой. Дальше дифференцированное уравнение
 GU> станет решать сложно - надо будет и его дифференцировать... Конечно,
 GU> можно написать рекурсивную функцию, решающую уравнение дихотомией,
 GU> только тогда возникнет другой вопрос - а не будет ли это менее
 GU> эффективно, чем какой-нибудь итерационный метод...

 Насколько я знаю, реально используются только кубические сплайны, да и то, случаи когда степень равна 3 достаточно редки, в основном 2-я. По крайней мере это верно для той геометрии которая импортируется из большинства CAD систем (в основном работал с геометрией из SolidWorks ). Но в принципе у меня есть опыт и по решению уравнений большей степени. Например когда ищешь расстояние от точки до кривой, то там степень вырастала до 9. Я реализовывал именно рекурсивный алгоритм - работает достаточно шустро.
  В принципе можно приблизительно оценить затраты дихотомии и прямого поиска для степени k: если длина интервала d, а шаг с которым ты будешь искать e, то при прямом поиске число вычислений функции будет n=d/e, а для дихотомии < (k^2)*log2(n). Т.ч. выбирай сам :) Возможно есть какой-нибудь лучший метод, но я его не знаю. Для меня, при реализации решающим фактором было то, что дихотомия гарантированно находит все корни с заданой точностью.


Anton

--- GoldED 2.50+
 * Origin: ... (2:5025/3.8)