Есть два луча Как найти на них две ближайшие друг к другу точки?

← →
MainRay (2007-02-08 05:26) [0]

Лучи заданы точкой и направлением.

Если кто нибудь знает алгоритм, как чего перемещать, чтобы их найти - напишите словами.

Погуглистам сразу идти нах.

← →
Rial © (2007-02-08 10:09) [1]

A1(x01, y01, z01) - точка, V1(x1, y1, z1) - направление.
Аналогично
A2, V2.

1)
Tmp:=A1;
A2:=A2 - Tmp;
A1:=A1 - Tmp;

2)
рассматриваем A1.
используется формула
X :=X * Cs - Y * Sn;
Y :=Y * Cs + X * Sn;
а) Ищем коэффициенты для уравнение такие, чтобы
после поворота V1 лежал в плоскости XY.
б) На полученный угол поворачиваем V2.
Итак, имеем V1 лежащий в XY и М2.
в) Операции а) и б) проделываем с целью,
чтобы V1 лежал на оси X.

3)Имеем уравнение луча L2 = A2 + V2""(x).
V2"" - дважды повернутый V2.
Теперь выражаем координаты Y и Z луча L2
через X.
Расстояние, очевидно, между лучами будет
Hypot(Y, Z);
Ищем точку X, в которой оно минимально.
Это уравнение от 1 переменной, решить которое
не составляет труда.

4)Точку получили.
Теперь вспоминаем, что вектор был 2 рааз повернут.
Выполняем обратный поворот - и результат готов.

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

← →
MainRay (2007-02-09 01:57) [2]

> Rial © (08.02.07 10:09) [1]
> 1)
> Tmp:=A1;
> A1:=A1 - Tmp;

Если вычесть самого себя, то будет ноль. Неужели ты таких простых вещей не знаешь?

← →
MainRay (2007-02-09 02:00) [3]

> Rial © (08.02.07 10:09) [1]
> 2)
> рассматриваем A1.
> используется формула
> X :=X * Cs - Y * Sn;
> Y :=Y * Cs + X * Sn;

Осталось только выяснить что в них что обозначает.

А про синусы и косинусы рекомендую забыть. Здесь вам не школа.

← →
Asteroid © (2007-02-09 04:44) [4]

http://www.realtimerendering.com/int/ ?

← →
Rial © (2007-02-09 05:26) [5]

> [2] MainRay (09.02.07 01:57)
> Если вычесть самого себя, то будет ноль. Неужели ты таких
> простых вещей не знаешь?

Странный народ пошел, я в шоке просто...
Мне твои колкости не нужны, ошибся адресом :)
Я, в отлиции от тебя, знаю, как решить твою задачу. Это объективный параметр.
От того, что ты нашел, к чему придраться, ты не стал ближе к цели.
Если что не понятно - так и спроси.

> [3] MainRay (09.02.07 02:00)
> Осталось только выяснить что в них что обозначает.

В данном случае это поворот вектора по оси Z.
Cs и Sn - это косинус и синус угла поворота.
X и Y - координаты вектора.
Чтобы повернуть в обратном направлении, нужно
посчитать координаты по формуле
X :=X * Cs + Y * Sn;
Y :=Y * Cs - X * Sn;

← →
MainRay (2007-02-09 06:31) [6]

> Asteroid © (09.02.07 04:44) [4]
>
> http://www.realtimerendering.com/int/ ?

"Ray/ray: Ronald Goldman, Intersection of Two Lines in Three-Space, Graphics Gems, p. 304.".
И что?

> Rial © (09.02.07 05:26) [5]
>
> > [2] MainRay (09.02.07 01:57)
> > Если вычесть самого себя, то будет ноль. Неужели ты таких
> > простых вещей не знаешь?
>
> Странный народ пошел, я в шоке просто...
> Мне твои колкости не нужны, ошибся адресом :)
> Я, в отлиции от тебя, знаю, как решить твою задачу.

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

← →
Думкин © (2007-02-09 08:39) [7]

Методика такая:
1. Задаем лучи параметрически с областью определения параметров - положительная полуось действительных чисел.
2. Строим функцию расстояния между произвольными точками лучей. Функция двух переменных. Ищем минмумум.
3. Если при минимуме оба параметра положительные - то нашли. Если хотя бы один отрицательный - то значит минимум реализуется на границе одного из лучей.
4. Ищем расстояния от концов лучей до соседа. Выбираем минимальное.

Кто не понял, может идти вслед за гуглистами. адьез.

← →
Думкин © (2007-02-09 08:41) [8]

Строгого минимума может не быть. Если не ясно, что с этим делать - можно присоединиться к погуглистам.

← →
Rial © (2007-02-09 09:01) [9]

> [6] MainRay (09.02.07 06:31)
> Ты знаешь как получить ноль, а не задачу решить.
> И это не колкость, а деликатность. Другой бы дураком обозвал,
> а я только вежливо указал на ошибку.

Спасибо, что повеселил с утра, дружище.
Заряд положительной энергии мне не помешает :)

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

P.S.
Ядом можешь больше не дышать, лично я в эту ветку
из прнципа не загляну %)

← →
oldman © (2007-02-09 16:55) [10]

Есть два варианта (для плоскости):
1. Лучи пересекаются
2. Лучи не пересекаются

В обоих случаях задача лишена смысла...

Для 3D другая какафония...

← →
Думкин © (2007-02-10 18:43) [11]

> oldman © (09.02.07 16:55) [10]
> Есть два варианта (для плоскости):
> 1. Лучи пересекаются
> 2. Лучи не пересекаются
>
> В обоих случаях задача лишена смысла...

Я столько не выпью... :(

← →
Asteroid © (2007-02-10 23:40) [12]

> И что? [6]
А ссылка ведет в конец той же страницы, где четко расписан алгоритм.

← →
MainRay (2007-02-11 02:13) [13]

> Asteroid © (10.02.07 23:40) [12]
>
> > И что? [6]
> А ссылка ведет в конец той же страницы, где четко расписан
> алгоритм.

The solution is:
t1 = Determinant{(o2-o1),d2,d1 X d2} / ||d1 X d2||^2

Можешь запрограммировать эту функцию - запрограммируй.
А если не можешь, то и нечего тогда.

← →
MainRay (2007-02-14 04:41) [14]

> Asteroid © (10.02.07 23:40) [12]

Правильно ли я понял, что ты спасовал перед трудностью?

← →
Asteroid © (2007-02-16 03:50) [15]

> MainRay (14.02.07 04:41) [14]
Неправильно, просто я редко сюда заглядываю. А вот то, что ты за три дня так и не нашел, как считается определитель матрицы 3x3.... =)

OriginDiff = VectorSub( o2, o1 );
DirCross = VectorCross( d1, d2 );
Det = OriginDiff.x * ( d2.y * DirCross.z - d2.z * DirCross.y ) - OriginDiff.y * ( d2.x * DirCross.z - d2.z * DirCross.x ) + OriginDiff.z * ( d2.x * DirCross.y - d2.y * DirCross.x );
SqLen = VectorDot( DirCross, DirCross );
if SqLen < eps then // nearly parallel or intersect behind
else t1 = Det / SqLen;

Надо расписывать функции вычитания и скалярного и векторного произведения векторов или сам напишешь?

← →
MainRay (2007-02-16 04:00) [16]

> Asteroid © (16.02.07 03:50) [15]
> Det = OriginDiff.x * ( d2.y * DirCross.z - d2.z * DirCross.
> y ) - OriginDiff.y * ( d2.x * DirCross.z - d2.z * DirCross.
> x ) + OriginDiff.z * ( d2.x * DirCross.y - d2.y * DirCross.
> x );
> if SqLen < eps then // nearly parallel or intersect behind

Вопрос был о том, чтоб написать словами.
А ты чем пишешь?
Просто передрал с какого то учебника, судя по английским написям, не понимая.
Вот и всё.

← →
MainRay (2007-02-16 04:04) [17]

← →
Думкин © (2007-02-16 05:55) [18]

> Asteroid © (16.02.07 03:50) [15]

Ответ ему дали. Не трать свое время. Пусть следует за погуглистами.

← →
Ketmar © (2007-02-17 12:11) [19]

оставьте придурка-тролля в покое. давайте лучше пофлудим просто так. например, о достоинствах портвейна "777" перед заграницным мочепивом.

← →
dimon999 (2007-02-17 15:36) [20]

bool GetLinesDistance( Vector p1, Vector p2, Vector p3, Vector p4, Vector * pa, Vector * pb )
{
Vector p13,p43,p21;
double d1343,d4321,d1321,d4343,d2121;
double numer,denom;
double mua, mub;

p13.x = p1.x - p3.x;
p13.y = p1.y - p3.y;
p13.z = p1.z - p3.z;
p43.x = p4.x - p3.x;
p43.y = p4.y - p3.y;
p43.z = p4.z - p3.z;
if (fabs(p43.x) < EPSILON && fabs(p43.y) < EPSILON && fabs(p43.z) < EPSILON) return 0;
p21.x = p2.x - p1.x;
p21.y = p2.y - p1.y;
p21.z = p2.z - p1.z;
if (fabs(p21.x) < EPSILON && fabs(p21.y) < EPSILON && fabs(p21.z) < EPSILON) return 0;

d1343 = p13.x * p43.x + p13.y * p43.y + p13.z * p43.z;
d4321 = p43.x * p21.x + p43.y * p21.y + p43.z * p21.z;
d1321 = p13.x * p21.x + p13.y * p21.y + p13.z * p21.z;
d4343 = p43.x * p43.x + p43.y * p43.y + p43.z * p43.z;
d2121 = p21.x * p21.x + p21.y * p21.y + p21.z * p21.z;

denom = d2121 * d4343 - d4321 * d4321;
if (fabs(denom) < EPSILON) return 0;
numer = d1343 * d4321 - d1321 * d4343;

mua = numer / denom;
mub = (d1343 + d4321 * (mua)) / d4343;

pa->x = float( p1.x + mua * p21.x );
pa->y = float( p1.y + mua * p21.y );
pa->z = float( p1.z + mua * p21.z );
pb->x = float( p3.x + mub * p43.x );
pb->y = float( p3.y + mub * p43.y );
pb->z = float( p3.z + mub * p43.z );

return 1;
}

> bool GetLinesDistance
Интересный тип возвращаемых двнных для нахождения растояния

← →
dimon999 (2007-02-17 17:05) [22]

> homm © (17.02.07 15:59) [21]
не придирайтесь,
вопрос был "Есть два луча Как найти на них две ближайшие друг к другу точки?"

← →
MainRay (2007-02-18 06:40) [23]

Нет. Вопрос был

"Если кто нибудь знает алгоритм, как чего перемещать, чтобы их найти - напишите словами."

К сожалению, можно констатировать, что всё, что присуствтующие могут - это утянуть откуда нибудь функцию. Но при этом они НЕ ПОНИМАЮТ, как они работают.

> dimon999 (17.02.07 17:05) [22]
>
> > homm © (17.02.07 15:59) [21]
> не придирайтесь,
> вопрос был "Есть два луча Как найти на них две ближайшие
> друг к другу точки?"

Так что же ты не для лучей, а для линий функцию пишешь?

← →
dimon999 (2007-02-19 17:40) [24]

> К сожалению, можно констатировать, что всё, что присуствтующие могут - это > утянуть откуда нибудь функцию. Но при этом они НЕ ПОНИМАЮТ, как они > работают.

эта функция действительно выдрана из чужого кода и
я правда не знаю, как она работает.

> Так что же ты не для лучей, а для линий функцию пишешь?

line - это прямая, например в пространстве
segment - это отрезок

> Думкин © (16.02.07 05:55) [18]
Да будет так :)
Автору ветки, похоже, лень штудировать справочники по линейной алгебре так же, как мне переписывать "откуда-то" код (в котором, кстати, смешались два языка =) ).

P.S. Возможно, моя ошибка была в том, что я погуглил, так что самоустраняюсь, чего желаю и автору ветки :)

← →
Аффтар (2007-02-28 04:18) [26]

> Asteroid © (19.02.07 18:57) [25]
>
> > Думкин © (16.02.07 05:55) [18]
> Да будет так :)
> Автору ветки, похоже, лень

Короче ты облажался, и пошёл искать виновных вокруг себя.
Поздравлю тебя с приёмом в компанию Думкиных.

> P.S. Возможно, моя ошибка была в том, что я погуглил, так
> что самоустраняюсь, чего желаю и автору ветки :)

Пусть твои желания обратятся на тебя самого.

http://lleo.aha.ru/na/

"Деликатному" предлагается возглавить погуглистов и быстрым шагом следовать по ссылке в [27].

А по дороге еще раз подумать о деликатности.

Есть два луча Как найти на них две ближайшие друг к другу точки? Найти похожие ветки