получить самую близкую точку к линии

Question

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

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

Answer 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

---

Альтернативно:

From Пересечение Линия-Линия , в Википедии.Во-первых, найдите 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

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

Answer 2

, если кто-то заинтересован в функции CNA 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's 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;
        }
    }

Answer 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

Answer 4

Ответ от Джастина Л. почти нормальный, но он не проверяет, является ли нормализованное расстояние меньше 0 или больше, чем величина вектора AB.Тогда это не будет хорошо работать, когда проекция вектора P выходит за границы (из отрезка 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's 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
    }

}

Answer 5

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

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);
}

Обновление : Глядя на комментарии, похоже, что я адаптировал его для C # из того же исходного кода, который указан в принятом ответе.

Answer 6

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

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

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

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

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)

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

• Нет различий в регистре
• без квадратных корней
• только одно деление

Answer 7

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

Делайте математические вычисления правильно, и функция будет довольно тривиальной для написания.

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

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

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

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

Вторым считается случай, когда у разность равна 0, и верно обратное.Таким образом, x = Px, y = Ay

Answer 8

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

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 имеет методы для этого.

Answer 9

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

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

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

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

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

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

Answer 10

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

Intersector.nearestSegmentPoint