Линия задана двумя точками И в двумерном и трехмерном случаях мы можем использовать векторное произведение для вычисления дистанции от точки 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). В случае, когда угол другой, основание перпендикуляра лужит по одну или другую сторону точки, в зависимости от того, острый угол или тупой. Эти условия легко проверить, вычисляя скалярные произведения наших векторов и проверяя его знак: +, - или 0. Результат определит, как искать расстояние: как до одной из точек P0 или P1, или как расстояние до прямой L. Этот путь, работающий в любом n-мерном пространстве, показан на рисунке (obtuse - тупой, acute - острый): Далее заметим, что две проверки можно сделать, используя только два скалярных произведения: w0·v и v·v, которые являются числителем и знаменателем формулы для нахаждения параметризованного основания перпендикуляра от P до продолженной за отрезок S прямой L. Это позволяет упростить алгоритм: distance( Point P, Segment P0:P1 ) { v = P1 - P0 w = P - P0 if ( (c1 = w · v) <= 0 ) return d(P, P0) if ( (c2 = v · v) <= c1 ) return d(P, P1) b = c1 / c2 Pb = P0 + bv return d(P, Pb) } Если в двумерном случае нужно вычислить расстояние для большого числа точек и одного луча/отрезка, то все же более эффективным будет использовать нормализованное уравнение прямой для начального теста - какую дистанцию брать. Подобные детали, как правило, зависят от конкретной задачи. Вперед  >>>  1  2   8  Комментарии к статье  8 8  Обсудить в чате