Получить ближайшую точку к линии

Я хотел бы иметь прямолинейную функцию С#, чтобы получить ближайшую точку (от точки P) до линейного сегмента AB. Абстрактная функция может выглядеть так. Я искал SO, но не нашел полезного (по мне) решения.

public Point getClosestPointFromLine(Point A, Point B, Point P);

Ответы

Ответ 1

Здесь Ruby замаскирован под псевдокодом, если Point объекты имеют поле x и y.

def GetClosestPoint(A, B, P)

  a_to_p = [P.x - A.x, P.y - A.y]     # Storing vector A->P
  a_to_b = [B.x - A.x, B.y - A.y]     # Storing vector A->B

  atb2 = a_to_b[0]**2 + a_to_b[1]**2  # **2 means "squared"
                                      #   Basically finding the squared magnitude
                                      #   of a_to_b

  atp_dot_atb = a_to_p[0]*a_to_b[0] + a_to_p[1]*a_to_b[1]
                                      # The dot product of a_to_p and a_to_b

  t = atp_dot_atb / atb2              # The normalized "distance" from a to
                                      #   your closest point

  return Point.new( :x => A.x + a_to_b[0]*t,
                    :y => A.y + a_to_b[1]*t )
                                      # Add the distance to A, moving
                                      #   towards B

end

В качестве альтернативы:

От Пересечение линии в Википедии. Во-первых, найдите Q, что является второй точкой, которая должна быть сделана от шага от P в "правильном направлении". Это дает нам четыре момента.

def getClosestPointFromLine(A, B, P)

  a_to_b = [B.x - A.x, B.y - A.y]   # Finding the vector from A to B
                                        This step can be combined with the next
  perpendicular = [ -a_to_b[1], a_to_b[0] ]
                                    # The vector perpendicular to a_to_b;
                                        This step can also be combined with the next

  Q = Point.new(:x => P.x + perpendicular[0], :y => P.y + perpendicular[1])
                                    # Finding Q, the point "in the right direction"
                                    # If you want a mess, you can also combine this
                                    # with the next step.

  return Point.new (:x => ((A.x*B.y - A.y*B.x)*(P.x - Q.x) - (A.x-B.x)*(P.x*Q.y - P.y*Q.x)) / ((A.x - B.x)*(P.y-Q.y) - (A.y - B.y)*(P.y-Q.y)),
                    :y => ((A.x*B.y - A.y*B.x)*(P.y - Q.y) - (A.y-B.y)*(P.x*Q.y - P.y*Q.x)) / ((A.x - B.x)*(P.y-Q.y) - (A.y - B.y)*(P.y-Q.y)) )

end

Кэширование, пропуски и т.д. возможны по соображениям производительности.

Ответ 2

если кто-либо интересуется функцией С# XNA на основе вышеперечисленного:

    public static Vector2 GetClosestPointOnLineSegment(Vector2 A, Vector2 B, Vector2 P)
    {
        Vector2 AP = P - A;       //Vector from A to P   
        Vector2 AB = B - A;       //Vector from A to B  

        float magnitudeAB = AB.LengthSquared();     //Magnitude of AB vector (it length squared)     
        float ABAPproduct = Vector2.Dot(AP, AB);    //The DOT product of a_to_p and a_to_b     
        float distance = ABAPproduct / magnitudeAB; //The normalized "distance" from a to your closest point  

        if (distance < 0)     //Check if P projection is over vectorAB     
        {
            return A;

        }
        else if (distance > 1)             {
            return B;
        }
        else
        {
            return A + AB * distance;
        }
    }

Ответ 3

Ваша точка (X) будет линейной комбинацией точек A и B:

X = k A + (1-k) B

Для X, чтобы быть фактически на сегменте линии, параметр k должен быть между 0 и 1 включительно. Вы можете вычислить k следующим образом:

k_raw = (P-B).(A-B)  /  (A-B).(A-B)

(где период обозначает произведение точек)

Затем, чтобы убедиться, что точка на самом деле находится в сегменте линии:

if k_raw < 0:
    k= 0
elif k_raw > 1:
    k= 1
else:
    k= k_raw

Ответ 4

Ответ от Джастина Л. почти прекрасен, но он не проверяет, является ли нормализованное расстояние меньше 0 или выше величины АВ-вектора. Тогда это не сработает, когда P-векторная proyection выходит за пределы (от отрезка AB). Здесь скорректированный псевдокод:

    function GetClosestPoint(A, B, P)
{
  vectorAP = (p.x - a.x, p.y - a.y)     //Vector from A to P
  vectorAB = (b.x - a.x, b.y - a.y)     //Vector from A to B

  magnitudeAB = vectorAB[0]^2 + vectorAB[1]^2  
  //Magnitude of AB vector (it length)


  ABAPproduct = vectorAB[0]*vectorAP[0] + vectorAB[1]*vectorAP[1] 
  //The product of a_to_p and a_to_b


  distance = ABAPproduct / magnitudeAB       
  //The normalized "distance" from a to your closest point

  if ( distance < 0)     //Check if P projection is over vectorAB
    {
        returnPoint.x = a.x
        returnPoint.y = a.y
    }   
  else if (distance > magnitudeAB)
    {
        returnPoint.x = b.x
        returnPoint.y = b.y
    }
  else
    {
        returnPoint.x = a.x + vectorAB[0]*distance
        returnPoint.y = a.y + vectorAB[1]*distance
    }

}

Ответ 5

Найдите наклон a1 из AB путем деления y-разности с x-разностью; затем нарисуйте перпендикулярную линию (с наклоном a2 = -1/a1, вам нужно решить для смещения (b2), положив координаты P в y = a2 * x + b2); то у вас есть две линии (т.е. два линейных уравнения), и вам нужно решить пересечение. Это будет ваша ближайшая точка.

Сделайте правильную математику, и функция будет довольно тривиальной для записи.

Чтобы разработать немного:

Original line:
y = a1 * x + b1
a1 = (By - Ay) / (Bx - Ax)   <--
b1 = Ay - a1 * Ax            <--

Perpendicular line:
y = a2 * x + b2
a2 = -1/a1                   <--
b2 = Py - a2 * Px            <--

Now you have P which lies on both lines:
y = a1 * x + b1
y = a2 * x + b2
--------------- subtract:
0 = (a1 - a2) * Px + (b1 - b2)
x = - (b1 - b2) / (a1 - a2)  <--
y = a1 * x + b1              <--

Надеюсь, я где-то не испортил:) ОБНОВЛЕНИЕ Конечно. Служите мне правильно, чтобы не работать на бумаге в первую очередь. Я заслужил каждый снимок, но я ожидал, что кто-то исправит меня. Исправлено (надеюсь).

Стрелки указывают путь.

ОБНОВЛЕНИЕ А, угловые случаи. Да, некоторые языки не справляются с бесконечностями. Я действительно сказал, что решение не было языка...

Вы можете проверить специальные случаи, они довольно просты. Первый - когда разность х равна 0. Это означает, что линия вертикальна, а ближайшая точка находится в горизонтальном перпендикуляре. Таким образом, x = Ax, y = Px.

Во-вторых, когда y-разность равна 0, и наоборот. Таким образом, x = Px, y = Ay

Ответ 6

Этот ответ основан на идеях проективной геометрии.

Вычислить поперечное произведение (Ax, Ay, 1) & times; (Bx, By, 1) = (u, v, w). Полученный вектор описывает линию, соединяющую А и В: она имеет уравнение ux + vy + w = ​​0. Но вы также можете интерпретировать (u, v, 0) как точку, бесконечно удаленную в направлении, перпендикулярном этой линии. Выполняя другой кросс-продукт, вы получаете линию, соединяющую точку шляпы с P: (u, v, 0) & times; (Px, Py, 1). И чтобы пересечь эту линию с линией AB, вы делаете другое кросс-произведение: ((u, v, 0) & times; (Px, Py, 1)) & times; (u, v, w). Результатом будет однородный координатный вектор (x, y, z), из которого вы можете прочитать координаты этой ближайшей точки как (x/z, y/z).

Возьмите все вместе, и вы получите следующую формулу:

{\scriptsize\begin{pmatrix}x\y\z\end{pmatrix}}=\Bigl(\bigl({\scriptsize\begin{pmatrix}1&0&0\0&1&0\0&0&0\end{pmatrix}}(A\times B)\bigr)\times P\Bigr)\times(A\times B)

Используя систему компьютерной алгебры, вы можете найти результирующие координаты следующим образом:

x = ((Ax - Bx)*Px + (Ay - By)*Py)*(Ax - Bx) + (Ay*Bx - Ax*By)*(Ay - By)
y = -(Ay*Bx - Ax*By)*(Ax - Bx) + ((Ax - Bx)*Px + (Ay - By)*Py)*(Ay - By)
z = (Ax - Bx)^2 + (Ay - By)^2

Как вы заметили, существует много повторяющихся терминов. Изобретая (в значительной степени произвольные) имена для них, вы можете получить следующий окончательный результат, написанный в псевдокоде:

dx = A.x - B.x
dy = A.y - B.y
det = A.y*B.x - A.x*B.y
dot = dx*P.x + dy*P.y
x = dot*dx + det*dy
y = dot*dy - det*dx
z = dx*dx + dy*dy
zinv = 1/z
return new Point(x*zinv, y*zinv)

Преимущества такого подхода:

  • Нет различий в делах
  • Нет квадратных корней
  • Только одно подразделение

Ответ 7

Ближайшая точка C будет на линии, наклон которой является обратным AB и пересекается с P. Это звучит так, будто это может быть домашнее задание, но я дам несколько довольно сильных намеков, чтобы увеличить уровень оповещений:

  • Может быть только одна такая строка.

  • Это система двух линейных уравнений. Просто решите для x и y.

  • Нарисуйте сегмент линии между A и B; назовите это L. Уравнение для L составляет y = mx + b, где m - отношение y-координат к x-координатам. Решите для B используя A или B в выражении.

  • Сделайте то же, что и выше, но для CP. Теперь разрешите одновременную линейную систему уравнений.

  • Поиск в Google даст вам список примеров.

Ответ 8

Я написал это давным-давно, он не сильно отличается от того, что говорили другие, но это решение для копирования/вставки на С#, если у вас есть класс (или структура) с именем PointF с членами X и Y:

private static PointF ClosestPointToSegment(PointF P, PointF A, PointF B)
{
    PointF a_to_p = new PointF(), a_to_b = new PointF();
    a_to_p.X = P.X - A.X;
    a_to_p.Y = P.Y - A.Y; //     # Storing vector A->P  
    a_to_b.X = B.X - A.X;
    a_to_b.Y = B.Y - A.Y; //     # Storing vector A->B

    float atb2 = a_to_b.X * a_to_b.X + a_to_b.Y * a_to_b.Y;
    float atp_dot_atb = a_to_p.X * a_to_b.X + a_to_p.Y * a_to_b.Y; // The dot product of a_to_p and a_to_b
    float t = atp_dot_atb / atb2;  //  # The normalized "distance" from a to the closest point
    return new PointF(A.X + a_to_b.X * t, A.Y + a_to_b.Y * t);
}

Обновление. Рассматривая комментарии, похоже, что я адаптировал его к С# из того же исходного кода, что и в принятом ответе.

Ответ 9

Вот методы расширения, которые должны выполнить трюк:

public static double DistanceTo(this Point from, Point to)
    {
        return Math.Sqrt(Math.Pow(from.X - to.X, 2) + Math.Pow(from.Y - to.Y, 2));
    }

public static double DistanceTo(this Point point, Point lineStart, Point lineEnd)
    {
        double tI = ((lineEnd.X - lineStart.X) * (point.X - lineStart.X) + (lineEnd.Y - lineStart.Y) * (point.Y - lineStart.Y)) / Math.Pow(lineStart.DistanceTo(lineEnd), 2);
        double dP = ((lineEnd.X - lineStart.X) * (point.Y - lineStart.Y) - (lineEnd.Y - lineStart.Y) * (point.X - lineStart.X)) / lineStart.DistanceTo(lineEnd);

        if (tI >= 0d && tI <= 1d)
            return Math.Abs(dP);
        else
            return Math.Min(point.DistanceTo(lineStart), point.DistanceTo(lineEnd));
    }

Затем просто позвоните:

P.DistanceTo(A, B);

Чтобы получить расстояние от точки "P" от линии | AB |. Это должно быть легко изменить для PointF.

Поиск ближайшей точки - это просто поиск минимального расстояния. LINQ имеет методы для этого.

Ответ 10

Если кто-то ищет способ сделать это с помощью Java + LibGdx:

Intersector.nearestSegmentPoint