2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Найти точки пересечения параметрических кривых.
Сообщение26.09.2012, 19:26 
Собтвенно нужен алгорим для реализации сабжа. Всё бы ничего, но времени мало, а ничего готового найти не могу, есть статьи по нахождения пересечения сплайнов, в простейшем случае b-деревья для b-splines, но это немного не то что надо, потому что кривые заданы в виде

$
\begin{cases} x=x_1(t_1) \\y=y_2(t_1) \\\end{cases}
\begin{cases} x=y_1(t_2) \\y=y_2(t_2) \\\end{cases}
$

То есть там всё делается в виде нахождения $f(x)=g(x)$, что немного другое, потому что характер кривых такой который сразу приходит в голову при упоминании слова "функция", а не такой как здесь.

Где $x$ и $y$ это обычные аргументы, а функции это не пойми что. Скорее всего будет задаваться, конечно, через таблицу значений, но пока сойдут и какие-нибудь произвольные выражения похожие на правду типа $cos(x)$ или чтобы в итоге давало что-то типа спирали Евклида, то есть могут быть загогулины со всякими противными петельками и прочим нехорошим, но непрерывные, по крайней мере там где от них этого ждут.

Желательно что-нибудь готовое типа либы, но без интеграции всяких кадов и тп, видел в интернете примеры для аутолиспа, но для использования это не годится, потому что в автокад и так всё встроено.

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение26.09.2012, 23:47 
Аватара пользователя
e7z0x1 в сообщении #623702 писал(а):

$ \begin{cases} x=x_1(t_1) \\y=y_2(t_1) \\\end{cases} \begin{cases} x=y_1(t_2) \\y=y_2(t_2) \\\end{cases} $


опечаток нет?

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение27.09.2012, 14:28 
Не знаю, мне как дали так и пишу. В целом идея такая: Даны две разные функции, которые описываются системами от двух координат, каждая кордината описывается отдельной функцией от $t_1$ и $t_2$ соответственно.

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение01.10.2012, 16:59 
Алгоритм прост: находим все такие пары (t1,t2) (перебором), для которых х совпадают. Из них выбираем те, для которых y совпадают.

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение08.10.2012, 12:35 
Аватара пользователя
Esp_ в сообщении #625646 писал(а):
находим все такие пары (t1,t2) (перебором), для которых х совпадают

Допустим таких пар не найдено ни одной. Какой отсюда будет следовать вывод?

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение08.10.2012, 19:21 
Утундрий

Отсюда можно сделать простой вывод: что решения на сетках с выбранным шагом не существует. :D
Вид функций не известен, тут больше ничего и не сделать.

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение08.10.2012, 21:58 
Аватара пользователя
Esp_
Даже если вид функций и известен, всё равно немножко черезчур долго перебирать по точкам весь континуум. Однако, можно заменить кривые хотя бы кусочно-линейными ломаными, и тогда...

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение08.10.2012, 22:54 
Утундрий
Ну нет, какой "весь континуум" Обычно такие кривые имеют область определения от нуля до 1. :) Ну уж точно не от 1 до стотыщмиллионов.

Цитата:
Однако, можно заменить кривые хотя бы кусочно-линейными ломаными, и тогда..


Мне такое решение нравится, но это может быть не на много быстрее на практике и уж точно не настолько точно.
Почему это не намного быстрее: потому что мы и в переборном методе можем выбрать достаточно большой эпсилон, который нас устроит, а вот удастся ли здесь избавиться от делений так. чтобы выиграть время, - это надо думать.

 
 
 
 Re: Найти точки пересечения параметрических кривых.
Сообщение09.10.2012, 15:11 
Перебором по сетке найти минимум суммы квадратов модулей тех двух векторов. Потом запустить метод Ньютона.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group