|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Georgy Udov 2:5030/49.1 28 Nov 2002 20:53:59
To : All
Subject : Параметрическая кривая
--------------------------------------------------------------------------------
Здравствуй, All!
Вот задачка одна попалась, не подскажите ли, можно ли придумать лучшее
решение, чем я придумал?
Задачка:
Есть пространственная параметрическая непрерывная кривая. Известен интервал,
значения из которого может принимать параметр("область задания"). Для
каждого значения параметра можно легко найти значение функции(точку кривой).
Функциональная зависимость имеет достаточно сложный характер(для тех, кому
это что-нибудь скажет - неоднородный рациональный Б-сплайн).
Требуется придумать алгоритм, принимающий на входе пространственную точку,
лежащую на этой кривой, и возвращающий значение параметра, соответствующее
данной точке.
Придуманное мной решение:
1) Выбираем некоторую постоянную, на порядок-два меньше характерных размеров
кривой(которые известны)
2) Приближаем кривую несколькими звеньями ломаной. Полученный набор значений
параметра и точек(вершин ломаной) сохраняем в массив.
3) Выбираем несколько ближайших точек из массива.
4) Для каждой точки рассматриваем отрезки [предыдущая точка, данная точка]
[данная точка, следующая точка] Собираем эти отрезки в массив, исключая
повторения.
5) Для каждого отрезка из массива - делаем дихотомию. То есть, берём среднее
значение по параметру, смотрим, в каком из двух подотрезков скорее всего
лежит искомая точка, рассматриваем его, и т. д. Результатом для каждого
отрезка является - точка и её значение параметра.
6) Из полученного набора точек выбираем ближайшую к данной, и возвращаем
соответствующее ей значение параметра.
Vale, Georgy Udov. E-mail: udovgeorgy#SPAMOFFchat.ru
--- ifmail v.2.15
* Origin: http://news.kaa.ru (2:5030/49.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
