|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vadim Meshkov 2:5020/400 08 Jan 2002 19:26:10
To : Andrew Simontsev
Subject : Re: расстояние до отрезка
--------------------------------------------------------------------------------
Alexander Zeberg <zaccer@altavista.net> спрашивает:
AZ> дано: отрезок (x1,y1,z1)-(x2,y2,z2)
AZ> точка x,y,z
AZ> найти: L - расстояние от точки до отрезка
Вот алгоритм, не претендующий на оптимальность (написан
только что, поэтому нуждается в проверке). Обозначения:
(X1,Y1,Z1),(X2,Y2,Z2) --- концы отрезка, (x,y,z) ---
точка, L --- искомое расстояние.
DX=X2-X1; DY=Y2-Y1; DZ=Z2-Z1;
dx1=x-X1; dy1=y-Y1; dz1=z-Z1;
dx2=X2-x; dy2=Y2-y; dz2=Z2-z;
P=dx*DX+dy*DY+dz*DZ;
D=DX*DX+DY*DY+DZ*DZ;
if P <= 0, L=dx1*dx1+dy1*dy1+dz1*dz1;
elseif P >= sqrt(D), L=dx2*dx2+dy2*dy2+dz2*dz2;
else L=((dx1*DY-dy1*DX)^2+(dy1*DZ-dz1*DY)^2+(dz1*DX-
dx1*DZ)^2)/D;
end
L=sqrt(L);
Основная идея: если проекция точки на прямую, содержащую
отрезок, лежит вне отрезка, то кратчайшим является
расстояние до одного из концов. В алгоритме сначала
вычисляется расстояние (P) от точки 1 до проекции. Если
оно <= 0, то точка 1 --- ближайшая, если расстояние
больше длины отрезка (sqrt(D)), то проекция лежит за
точкой 2, и ближайшая точка --- 2. В противном случае
проекция попала внутрь отрезка, и используется
стандартная формула для расстояния до прямой.
Есть хорошие книги по геометрическим алгоритмам,
например такая:
Препарата (фамилия такая),Шеймос "Вычислительная
геометрия".
С уважением к собравшимся, В.М.
--
Отправлено через сервер Talk.Ru - http://www.talk.ru
--- ifmail v.2.15dev5
* Origin: Talk.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
