:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Расстояние между... » Точкой и прямой/лучом/отрезком
  Вычисление расстояния между точкой и прямой/лучом/отрезком




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



И в двумерном и трехмерном случаях мы можем использовать векторное произведение для вычисления дистанции от точки 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)
      }

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


  Исходник



// Copyright 2001, softSurfer (www.softsurfer.com)
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.

// Assume that classes are already given for the objects:
//    Point and Vector with
//        coordinates {float x, y, z;} (z=0 for 2D)
//        appropriate operators for:
//            Point  = Point +- Vector
//            Vector = Point - Point
//            Vector = Scalar * Vector
//    Line with defining endpoints {Point P0, P1;}
//    Segment with defining endpoints {Point P0, P1;}
//===================================================================
// dot product (3D) which allows vector operations in arguments
#define dot(u,v)   ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)
#define norm(v)    sqrt(dot(v,v))  // norm = length of vector
#define d(u,v)     norm(u-v)
// distance = norm of difference

//closest2D_Point_to_Line(): finds the closest 2D Point to a Line
//    Input:  an array P[] of n points, and a Line L
//    Return: the index i of the Point P[i] closest to L
int closest2D_Point_to_Line( Point P[], int n, Line L)
{
    // Get coefficients of the implicit line equation.
    // Do NOT normalize since scaling by a constant
    // is irrelevant for just comparing distances.
    float a = L.P0.y - L.P1.y;
    float b = L.P1.x - L.P0.x;
    float c = L.P0.x * L.P1.y - L.P1.x * L.P0.y;

    // initialize min index and distance to P[0]
    int mi = 0;
    float min = a * P[0].x + b * P[0].y + c;
    if (min < 0) min = -min;    // absolute value

    // loop through Point array testing for min distance to L
    for (i=1; i<n; i++) {
        float dist = a * P[i].x + b * P[i].y + c;
        if (dist < 0) dist = -dist;   
// absolute value
        if (dist < min) {    
// this point is closer
            mi = i;          
// so have a new minimum
            min = dist;
        }
    }
    return mi;    // the index of the closest 
Point P[mi]
}
//===================================================================
//   distance_Point_to_Segment():
//    Input:  a Point P and a Segment S (in any dimension)
//    Return: the shortest distance from P to S
float
distance_Point_to_Segment( Point P, Segment S)
{
    Vector v = S.P1 - S.P0;
    Vector w = P - S.P0;

    double c1 = dot(w,v);
    if ( c1 <= 0 )
        return d(P, S.P0);

    double c2 = dot(v,v);
    if ( c2 <= c1 )
        return d(P, S.P1);

    double b = c1 / c2;
    Point Pb = P0 + b * v;
    return d(P, Pb);
}