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

[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 19:14