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

Линия задана двумя точками

И в двумерном и трехмерном случаях мы можем использовать векторное произведение для вычисления дистанции от точки P до прямой L, заданной точками P1 и P2.

Двумерный случай сводится к трехмерному подстановкой z=0.

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

Однако эта площадь также равна произведению основания на высоту параллелограмма, а длина высоты - искомая дистанция d(P,L). Пусть vL=P0P1=(P1-P0) и w=P0P=(P-P0) как показано на рисунке:

Тогда |vLЧ w| = Area( parallelogram(vL,w) ) = |vL| d(P,L) что дает простую формулу:

где uL = vL / |vL|

единичный вектор направления L. Если мы хотим вычислить расстояние от большого числа точек точек до фиксированной прямой, то наиболее рациональным будет предварительно вычислить uL.

Для 2D случая при P=(x,y,0), векторное произведение будет:

и формула для расстояния:

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

Прямая, заданная уравнением

В двумерном пространстве часто встречаются ситуации, когда прямую L задана уравнением f(x,y) = ax+by+c = 0. Для любой точки P=(x,y) расстояние d(P,L) может быть получено прямо из уравнения.

Я дам просто формулу, доказательство ее можно найти в любом учебнике

(ax+by+c)
d(P,L) = -------------------------
КОРЕНЬ ( a2+b2 )

Если же мы предварительно нормализуем уравнение: разделим его коэффициенты на КОРЕНЬ ( a2+b2 ), тогда знаменатель будет равен 1, и получится очень эффективная формула

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

Параметризованная прямая

Для вычисления расстояния d(P,L) (в любом n-мерном пространстве) от произвольной точки P до прямой L, заданной параметрическим уравнением, положим P(b) - основание перпендикуляра, опущенного из P на L. Пусть параметрическое уравнение прямойs: P(t)=P0 + t (P1-P0). Тогда вектор P0P(b) является проекцией вектора P0P на отрезок P0P1, как показано на рисунке:

Применив vL=(P1-P0) и w=(P-P0), мы получаем

таким образом:

где uL - единичный вектор направления L.

Такой путь вычисления имеет то преимущество, что он работает в n-мерном пространстве и, кроме того, дает нам основание перпендикуляра P(b). В трехмерном пространстве он также эффективен, как и векторное произведение. Но в двумерном, где P(b) не нужна, особенно при большом количестве точек и одной линии, более удобен предыдущий способ, использующий другое уравнение прямой.

Расстояние до луча/отрезка

Луч (Ray) можно задать параметрически как P(t) для всех t>=0 и P(0)=P0 - для начальной точки. Отрезок (Segment) между точками P0 и P1 может быть задан в виду параметрического уравнения с P(0)=P0 и P(1)=P1 при 0<=t<=1.

Вычисление расстояния в этих случаях отличается от вышеописанного, так как основание перпендикуляра P(b) из P на продолженную прямую L может не лежать на луче/отрезке. В этом случае кратчайшим расстоянием будет дистанция от P до начальной точки луча или одной из начальных точек отрезка.

Для луча есть лишь один вариант, в то время как для отрезка следует решить, какой конец ближе к P. Можно вычислить оба расстояния и сравнить, однако это малоэффективно. Кроме того, нужно определить, лежит ли основание перпендикуляра вне отрезка. Простой путь решения заключается в том, чтобы рассмотреть углы между отрезком P0P1 и векторами P0P и P1P. Если один из них равен 90 градусам, то соответствующая точка - основание перпендикуляра P(b). В случае, когда угол другой, осн