Как найти кратчайшее расстояние между точкой и отрезком линии в C#

В этом примере рассматривается сегмент как параметризованный вектор, где параметр t изменяется от 0 до 1. Он находит значение t, которое минимизирует расстояние от точки до линии.

Если t находится между 0.0 и 1.0, то точка на сегменте, ближайшем к другой точке, лежит на сегменте. В противном случае ближайшая точка является одной из конечных точек сегмента. Программа находит эту ближайшую точку и вычисляет расстояние между ней и целевой точкой.

Следующий код показывает, как программа находит расстояние между точкой pt и отрезком p1 - & gt; p2 .

// Рассчитайте расстояние между
// точка pt и отрезок p1 -> p2.
private double FindDistanceToSegment(
    PointF pt, PointF p1, PointF p2, out PointF closest)
{
    float dx = p2.X - p1.X;
    float dy = p2.Y - p1.Y;
    if ((dx == 0) && (dy == 0))
    {
        // Это точка не отрезка.
        closest = p1;
        dx = pt.X - p1.X;
        dy = pt.Y - p1.Y;
        return Math.Sqrt(dx * dx + dy * dy);
    }

    // Вычислим t, который минимизирует расстояние.
    float t = ((pt.X - p1.X) * dx + (pt.Y - p1.Y) * dy) /
        (dx * dx + dy * dy);

    // Посмотрим, представляет ли это один из сегментов
    // конечные точки или точка в середине.
    if (t < 0)
    {
        closest = new PointF(p1.X, p1.Y);
        dx = pt.X - p1.X;
        dy = pt.Y - p1.Y;
    }
    else if (t > 1)
    {
        closest = new PointF(p2.X, p2.Y);
        dx = pt.X - p2.X;
        dy = pt.Y - p2.Y;
    }
    else
    {
        closest = new PointF(p1.X + t * dx, p1.Y + t * dy);
        dx = pt.X - closest.X;
        dy = pt.Y - closest.Y;
    }

    return Math.Sqrt(dx * dx + dy * dy);
}

Менее очевидной частью этого кода является следующая инструкция.

// Вычислить t, который минимизирует расстояние.
float t = ((pt.X - p1.X) * dx + (pt.Y - p1.Y) * dy) /
    (dx * dx + dy * dy);

Итак, откуда эта формула?

Чтобы найти кратчайшее расстояние между этой точкой и сегментом линии, вам нужно знать некоторые относительно простые исчисления и один умный факт. Умный факт состоит в том, что если T минимизирует уравнение, то T ^{2 минимизирует квадрат уравнения. В этом примере это означает, что мы можем минимизировать расстояние между точками и отрезком линии, а затем найденное нами значение t также минимизирует неквадратное расстояние.}

Точка на отрезке линии имеет координаты X = Pt1.X + t * dx, Y = Pt1.Y + t * dy.

Расстояние между этой точкой и точкой P равно:

[Pt.X - (Pt1.X + t*dx)]2 + [Pt.Y - (Pt1.Y + t*dy)]2

Взяв производную по t, получим:

2*[Pt.X - (Pt1.X + t*dx)]*dx + 2*[Pt.Y - (Pt1.Y + t*dy)]*dy

Чтобы найти минимум, мы устанавливаем его равным 0 и решаем для t.

2*[Pt.X - (Pt1.X + t*dx)]*dx + 2*[Pt.Y - (Pt1.Y + t*dy)]*dy = 0

Теперь, если вы разделите обе стороны на 2 и затем соедините полученные вами термы:

-t*(dx2 + dy2) + dx*(Pt.X - Pt1.X) + dy*(Pt.Y - Pt1.Y) = 0

Вычитая t-член с обеих сторон уравнения, получим:

dx*(Pt.X - Pt1.X) + dy*(Pt.Y - Pt1.Y) = t*(dx2 + dy2)

Теперь вы можете разделить обе стороны на (dx ^{2 + dy 2 ), чтобы получить:}

t = [dx*(Pt.X - Pt1.X) + dy*(Pt.Y - Pt1.Y)] / (dx2 + dy2)

Источник: http://csharphelper.com/blog/2016/09/find-the-shortest-distance-between-a-point-and-a-line-segment-in-c/

(1 оценок, среднее: 5,00 из 5)