Найти точки пересечения параметрических кривых.

[e7z0x1]

Собтвенно нужен алгорим для реализации сабжа. Всё бы ничего, но времени мало, а ничего готового найти не могу, есть статьи по нахождения пересечения сплайнов, в простейшем случае 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)$ или чтобы в итоге давало что-то типа спирали Евклида, то есть могут быть загогулины со всякими противными петельками и прочим нехорошим, но непрерывные, по крайней мере там где от них этого ждут.

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

[alcoholist]

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} $

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

[e7z0x1]

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

[Esp_]

Алгоритм прост: находим все такие пары (t1,t2) (перебором), для которых х совпадают. Из них выбираем те, для которых y совпадают.

[Утундрий]

Esp_ в сообщении #625646 писал(а):

находим все такие пары (t1,t2) (перебором), для которых х совпадают

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

[Esp_]

Утундрий

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

[Утундрий]

Esp_
Даже если вид функций и известен, всё равно немножко черезчур долго перебирать по точкам весь континуум. Однако, можно заменить кривые хотя бы кусочно-линейными ломаными, и тогда...

[Esp_]

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

Цитата:

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

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

[ewert]

Перебором по сетке найти минимум суммы квадратов модулей тех двух векторов. Потом запустить метод Ньютона.