Расчет расстояния до пути

Question

У меня есть набор точек, которые образуют путь.Я хотел бы определить минимальное расстояние от любой данной точки до этого пути.Путь может выглядеть примерно так:

points = [
    [50, 58],
    [53, 67],
    [59, 82],
    [64, 75],
    [75, 73]
];

, где первое значение - это координата x, а второе - координата y.Путь с открытым концом (он не будет образовывать замкнутый контур) и состоит из прямых отрезков между точками.

Таким образом, с учетом точки, например.[90, 84], как рассчитать кратчайшее расстояние от этой точки до пути?

Я не обязательно ищу полное решение, но любые указатели и идеи будут оценены.

Answer 1

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

Вот простой пример:

(5,1)-(4,2)-(1,3)-(20,3)-(15,2)-(14,1)

Для данной точки (10,1) ближайшее расстояние до пути будет до точки (10,3), которая находится вдоль отрезка (1,3) - (20,3), но эти две точки дальше (10,1) от любой другой точки пути.

Так что я не верю, что есть какие-либо сокращения в наивном алгоритме нахождения расстояния до каждого отрезка и определения минимума.

Answer 2

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

Answer 3

Итак, я просто об этом на секунду. Эрекалпер уже разместил расстояние между точкой и линией. Однако проблема с этой формулой состоит в том, что она предполагает, что линия имеет бесконечную длину, что не относится к вашей проблеме. Просто пример для задачи: предположим простую линию, которая идет от (0,0) до (0,1), и точку с координатами (0,10). Приведенная выше формула вернет o на расстояние 0, потому что, если вы продолжите линию, она попадет в точку. К сожалению, в вашем случае линия заканчивается на (0,1), таким образом, расстояние на самом деле равно 9.

Таким образом, мой алгоритм будет таким: Проверьте, не составляют ли углы в конечных точках ваших линий <= 90 °. Если это так, кратчайшее расстояние для этого пути будет вычисляться по формуле уже размещены. Если нет, самое короткое расстояние - это расстояние до одной из конечных точек. Сделайте это для всех частей пути, выберите минимум </p>

Answer 4

Расстояние от точки C до отрезка AB - это площадь параллелограмма ABCC '.

Answer 5

Расстояние между точкой и линией определяется как:

d = | (x_2 - x_1) (y_1 - y_0) - (x_1 - x_0) (y_2 - y_1) |/ sqrt ((x_2 - x_1) ^ 2 - (y_2 - y_1) ^ 2),

, которая является расширением точечного произведения, где (x_0, y_0) - координаты точки, и (x_1, y_1) & (x_2, y_2) являются конечными точками линии.

Было бы довольно просто рассчитать это для каждого набора точек, а затем просто определить, какая из них является самой низкой.Я не уверен, что нет более элегантного способа сделать это, но я не знаю об этом.Хотя я бы хотел посмотреть, ответит ли кто-нибудь здесь одним из них!

Редактировать: Извините, что математика здесь выглядит такой грязной без форматирования.Вот изображение того, как выглядит это уравнение, выполненное красиво:

Точка к строке!http://mathworld.wolfram.com/images/equations/Point-LineDistance2-Dimensional/NumberedEquation8.gif

Другое редактирование: Как указал Крис в своем посте, это не работает, если точки находятся в линии, т. Е. Если линия определена как (0,0) - (0,1) иточка на (0,10).Как он объясняет, вам нужно проверить, чтобы убедиться, что рассматриваемая точка на самом деле не находится на «расширенном пути» самой линии.Если это так, то это просто расстояние между ближайшей конечной точкой и точкой.Вся заслуга Криса!

Answer 6

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

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

Answer 7

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

Вот ссылка на статью, которая описывает математику: http://mathforum.org/library/drmath/view/55501.html

А вот довольно хорошая библиотека .Вам нужно взглянуть на методы, называемые PointSegmentDistance. сегмент , по-видимому, является линией, которая начинается в одной точке и заканчивается во второй точке, тогда как линия имеет две точки, но продолжаетсяв бесконечности.