Кратчайшее растояние, м/д сторонами двух треугольников Опции

[killer on the road]

В плоскости, даны два треугольника. Требуется определить кратчайшее растояние между их сторонами.
Пока у меня есть только идея тупого перебора. Находим формулы описывающие каждую сторону, проходим циклом по всем Х, попутно генерируя У, и сравниваем с таким же циклом для второго треугольника. Получается очень много сравнений. Может есть какая нибудь хитрая идея?

[klem4]

а точно надо определить кратчайшее расстояние между сторонами а не вершинами ?

[Altair]

Какая разница между чем? у нас всена плоскости происхдит.
Клем - нарисуй 2 треугольника и посмотри кратчайшее растояние между сторонами... такое растояние всегда будет проходить через вершины треугольника....
так что важны нам только координаты вершин.
палочка выручалочка дял нас фраза:

В плоскости, даны

[klem4]

такое растояние всегда будет проходить через вершины треугольника....

:no: неправда.

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

Сообщение отредактировано: klem4 - 26.06.2005 22:41

[volvo]

klem4, опровержение - в студию...

Oleg_Z имел в виду, что кратчайшее расстояние обязательно пройдет через вершину одного из треугольников...

[Altair]

klem4, если ты не прав, ты покупаешь мне 2 пива!

Сообщение отредактировано: Oleg_Z - 26.06.2005 22:50

[klem4]

Volvo, написано

через вершины

Но я как раз имел в виду вариант, который высказал ты :
зы : Олег, с тебя пиво ?)

Сообщение отредактировано: klem4 - 26.06.2005 22:48

[Altair]

через вершины

....треугольника!

все равно я прав! :P
пиво ты покупаешь!

Сообщение отредактировано: Oleg_Z - 26.06.2005 22:50

[killer on the road]

Господа, всё это конечно интересно, но может кто нить по сути выразится (просьба не обижаться)
А вы не подумали, что если треугольники пересекаются, то кратчайшее растояние в точке пересечения, а она может находится далеко не в вершинах....

[Altair]

Алгоритм. (если треугольники не пересекаются)
i=1
1. берем i точку и находим координаты точек пересечения высот проведенных от i точки до каждой из сторон другого треугольника.
(*) Выбираем минимум из 3 длин.
2. i=i+1, перейти на 1.


Как найти точку пересечения высоты проведенной из точки i-M(x0,y0) до стороны l ?

Для этого надо найти коэффициенты уравнения стороны l (A, B,C)
L: Ax+By+C
и найти координаты точки пересечения p по формуле:

x= x0+at
y= y0+Bt

где параметр
t = - (Ax0+By0+C)/(A^2 +B^2);

Как найти уравнение стороны, зная координаты 2 точек?
пусть дана точка M1(x1,y1) и точка M2(x2,y2), принадлежащие L, тогда :
L: (x-x1)/(x2-x1) = (y-y1)/(y2-y1)


P.S. здесь (*) надопроверить лежат ли точки пересечения на сторне иди выходят за пределы отрезка.

Сообщение отредактировано: Oleg_Z - 26.06.2005 23:14

[Altair]

что если треугольники пересекаются, то кратчайшее растояние в точке пересечения, а она может находится далеко не в вершинах....

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

p.s. но если стороны пересекаются то смысла в расстоянии между пересекающимися сторонами нет!

[killer on the road]

p.s. но если стороны пересекаются то смысла в расстоянии между пересекающимися сторонами нет!

Смысла-то, оно конечно нет. Просто, по условию задачи, координаты вершин рэндомны. Так что, пересечений не избежать.
За алгоритм спасибо, попробую реализовать. Только вот я недопонял как это перебрать стороны на предмет пересечения? Если тупым перебором всех точек, то ни проще ли сразу вычислять кратчайшее растояние?

[Altair]

как это перебрать стороны на предмет пересечения?

Как проверить пересекаются ли 2 отрезка?
пересечение отрезков

Пересечение: Прямая(отрезок) и прямая (отрезок)

[killer on the road]

Люди, ай нид хелп!
Пытался сделать по материалам этой ссылки - http://ixbt.wallst.ru/egm.html
Но что-то незаладилось... Кто нибудь помогите плиз!
А ещё оказалось, что кратчайшее растояние может находится между двумя вершинами, но этот случай я уже перебором обработал. А вот вершина-перпендикуляр - не выходит...

[Malice]

Люди, ай нид хелп!

Короче, так. У тебя 3 вариана самого короткого расстояния:
1. пересечение граней - уже обсуждалось, сделаешь
2. вершина - вершина - рассояние между всеми проверишь
3. вершина - грань - надо найти перпендикуляр на грань
В 3-ем случае делаешь так:

{
 грань -    (x1,x2) и (x3,y3)
 вершина -(x2,y2)
}

a:=arctan((y3-y1)/(x3-x1));
xx:=(x2-x1)*cos(a)+(y2-y1)*sin(a)+x1;
yy:=y1; 
if (xx<x1) or (xx>x3) then
{ перпендикуляр  не на отрезке -> возьмешь 
минимум из вариантов 1 или 2}
else begin
x4:=(xx-x1)*cos(-a)+(yy-y1)*sin(-a)+x1;
y4:=(yy-y1)*cos(-a)-(xx-x1)*sin(-a)+y1;

в x4 и y4 точка пересечения. ну и (x2,y2)-(x4,y4) - мин. расстояние. :yes:

[killer on the road]

очень извиняюсь за тупость, а можно полный текст программы... всё вместе никак соеденить не могу. Ну не программер я, не программер.

[Malice]

очень извиняюсь за тупость, а можно полный текст программы... всё вместе никак соеденить не могу. Ну не программер я, не программер.

Ну лови, 2 варианта вершина-вершина и вершина-грань. Рисуются оба варианта, минимум из них выберешь. На пересечения граней не делал, это вроде просто добавить Выход по пробелу, любая другая- еще раз.

uses crt,graph;
type pt=record
x:extended;
y:extended;
end;
var t: array [0..1,1..3] of pt;
i1,j1,i2,i3:byte;
ii,i,j,n,nn,n1:integer;
a,xx2,xx,yy,x4,y4,x4_, y4_, rm,r, rg:extended;
begin
randomize;
i:=detect; initgraph(i,i,'');
repeat
cleardevice;
for n:=0 to 1 do for i:=1 to 3 do begin
t[n][i].x:=random(640); t[n][i].y:=random(480);
end;
i1:=0; j1:=0; rm:=0; rg:=0;
for n:=0 to 1 do begin
for i:=1 to 3 do for j:=1 to 3 do begin
nn:=n xor 1;
r:=sqrt(sqr(t[n][i].x-t[nn][j].x)+sqr(t[n][i].y-t[nn][j].y));
if (r<rm) or (rm=0) and (n=0) then begin rm:=r; i1:=i; j1:=j; end;
if t[nn][(j mod 3)+1].x=t[nn][j].x then a:=0 else
a:=arctan((t[nn][(j mod 3)+1].y-t[nn][j].y)/ (t[nn][(j mod 3)+1].x-t[nn][j].x));
xx:=(t[n][i].x-t[nn][j].x)*cos(a)+
      (t[n][i].y-t[nn][j].y)*sin(a)+t[nn][j].x;
yy:=t[nn][j].y;
xx2:=(t[nn][(j mod 3)+1].x-t[nn][j].x)*cos(a)+
     (t[nn][(j mod 3)+1].y-t[nn][j].y)*sin(a)+t[nn][j].x;
if ((t[nn][j].x<xx2) and ((xx<t[nn][j].x) or (xx>xx2))) or
   ((t[nn][j].x>xx2) and ((xx>t[nn][j].x) or (xx<xx2))) then
begin x4:=999; y4:=999; end else begin
  x4:=(xx-t[nn][j].x)*cos(-a)+(yy-t[nn][j].y)*sin(-a)+t[nn][j].x;
  y4:=(yy-t[nn][j].y)*cos(-a)-(xx-t[nn][j].x)*sin(-a)+t[nn][j].y;
end;
r:=sqrt(sqr(t[n][i].x-x4)+sqr(t[n][i].y-y4));
if (r<rg) or (rg=0) then begin
n1:=n; x4_:=x4; y4_:=y4;  rg:=r; i3:=i;
end; end; end;
setcolor(7);
for n:=0 to 1 do for i:=1 to 3 do
line(round(t[n][i].x),round(t[n][i].y),
 round(t[n][(i mod 3)+1].x),round(t[n][(i mod 3)+1].y));
setcolor(4);
line(round(t[0][i1].x),round(t[0][i1].y),  round(t[1][j1].x),round(t[1][j1].y));
setcolor(5);
line(round(t[n1][i3].x),round(t[n1][i3].y),  round(x4_),round(y4_));
until readkey=' ';
end.