|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 09 Jan 2002 19:29:55
To : Alexander Zeberg
Subject : Re: расстояние до отрезка
--------------------------------------------------------------------------------
> From: "Alexander Zeberg" <zaccer@altavista.net>
> Date: Tue, 8 Jan 2002 03:59:30 +0000 (UTC)
>
>дано:
>отрезок (x1,y1,z1)-(x2,y2,z2)
>точка x,y,z
>найти:
>L - расстояние от точки до отрезка
>
>Может кто уже решал подобное? Хотелось бы осуществить этот расчет с минимумом
>умножений/делений/корнеизвлечений и т.п.
Для начала найдём расстояние от точки до прямой. Обозначим концы отрезка
буквами A и B, а точку - буквой X. Модуль векторного произведения [AX * BX]
есть удвоенная площадь треугольника ABX. С другой стороны, эта же удвоенная
площадь есть произведение искомого расстояния на длину отрезка AB. Таким
образом, операция деления у нас только одна: надо поделить векторное
произведение на длину отрезка, буде последняя не равна нулю. Ежели длина
отрезка равна нулю, то ответ просто равен расстоянию от точки до любого
из концов.
Hайденное расстояние и является искомым L в том случае, когда углы XAB
и XBA оба острые, то есть когда одновременно выполняются два неравенства
|AX|^2 + |AB|^2 > |XB|^2 и |XB|^2 + |AB|^2 > |AX|^2. В противном же случае
одно из этих неравенств нарушено и L есть расстояние от точки до блжайшего
конца отрезка, то есть до того, который входит в правую часть выполненного
неравенства и в левую - нарушенного.
Как видно, при вычислениях удобно оперировать не с расстояниями, а с их
квадратами, а корень извлечь в самом конце, после выбора нужного расстояния.
В формулах для векторного произведения и длин отрезков много общих
подвыражений, при желании их можно пооптимизировать.
Вал. Дав.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
