Мне нужна базовая функция, чтобы найти кратчайшее расстояние между точкой и отрезком. Не стесняйтесь написать решение на любом языке, который вы хотите; Я могу перевести это в то, что я использую (Javascript).
РЕДАКТИРОВАТЬ: мой сегмент линии определяется двумя конечными точками. Так что мой отрезок AB
определяется двумя точками A (x1,y1)
и B (x2,y2)
. Я пытаюсь найти расстояние между этим отрезком и точкой C (x3,y3)
. Мои навыки геометрии ржавые, поэтому примеры, которые я видел, сбивают с толку, извините, чтобы признать.
language-agnostic
geometry
distance
line-segment
Eli Courtwright
источник
источник
Ответы:
Эли, код, на котором ты остановился, неверен. Точка около линии, на которой лежит сегмент, но далеко от одного конца сегмента, будет неверно оценена около сегмента.Обновление: упомянутый неверный ответ больше не является принятым.Вот некоторый правильный код на C ++. Предполагается, что класс 2D-вектор
class vec2 {float x,y;}
, по существу, содержит операторы сложения, вычитания, масштабирования и т. Д., А также функцию произведения расстояния и точки (т.е.x1 x2 + y1 y2
).РЕДАКТИРОВАТЬ: Мне нужна реализация Javascript, так что здесь, без каких-либо зависимостей (или комментариев, но это прямой порт вышеупомянутого). Очки представлены в виде объектов
x
иy
атрибутов.РЕДАКТИРОВАТЬ 2: Мне нужна версия Java, но что более важно, мне нужно было в 3d вместо 2d.
источник
p
на линию - это точка на линии, ближайшей кp
. (А перпендикулярно к линии в проекции будет проходить черезp
.) Числоt
, как далеко вдоль отрезка отv
до ,w
что проекция падает. Так что, еслиt
0, проекция падает прямоv
; если это 1, это включеноw
; например, если это 0,5, то это на полпути между ними. Еслиt
он меньше 0 или больше 1, он попадает на линию после одного конца или другого сегмента. В этом случае расстояние до сегмента будет расстоянием до ближайшего конца.Вот самый простой полный код в Javascript.
x, y - ваша целевая точка, а x1, y1 - x2, y2 - ваш отрезок.
ОБНОВЛЕНО: исправлена проблема с длиной линии в комментариях.
источник
Это реализация, сделанная для сегментов FINITE LINE, а не бесконечные линии, как большинство других функций здесь (вот почему я сделал это).
Реализация теории Пола Бурка .
Python:
AS3:
Ява
источник
distAnother(0, 0, 4, 0, 2, 2)
дает 2.8284271247461903 (неверно).distAnother(0., 0., 4., 0., 2., 2.)
дает 2,0 (правильно). Пожалуйста, помните об этом. Я думаю, что код может быть улучшен, чтобы иметь где-то преобразование с плавающей точкой.В моей собственной теме вопроса, как рассчитать кратчайшее 2D расстояние между точкой и отрезком линии во всех случаях в C, C # / .NET 2.0 или Java? Меня попросили поместить ответ C # здесь, когда я его найду: вот он, измененный с http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :
Я @ SO, чтобы не отвечать, а задавать вопросы, поэтому я надеюсь, что по некоторым причинам я не получу миллион голосов, но создаю критику. Я просто хотел (и был воодушевлен) поделиться чужими идеями, поскольку решения в этой теме либо на каком-то экзотическом языке (Fortran, Mathematica), либо кем-то помечены как ошибочные. Единственный полезный (от Grumdrig) для меня написан на C ++, и никто не пометил его как неисправный. Но в нем отсутствуют методы (точки и т. Д.), Которые вызываются.
источник
В F # расстояние от точки
c
до отрезка междуa
иb
определяется как:Вектор
d
указывает отa
доb
вдоль отрезка. Точечное произведениеd/s
сc-a
дает параметр точки ближайшего сближения между бесконечной линией и точкойc
. Функцияmin
иmax
используется для фиксации этого параметра в диапазоне,0..s
так что точка находится междуa
иb
. Наконец, длинаa+p-c
- это расстояние отc
ближайшей точки на отрезке.Пример использования:
источник
(a + p - c).Length
lambda
иp
какlet lambda = (c - a) * d / (s * s)
иlet p = a + (lambda |> max 0.0 |> min 1.0) * d
, соответственно. После того, что функция возвращает правильное расстояние , например , для случая , когдаa = (0,1)
,b = (1,0)
иc = (1,1)
.Для тех, кто заинтересован, вот тривиальное преобразование кода Javascript Джошуа в Objective-C:
Мне нужно было работать с этим решением,
MKMapPoint
поэтому я поделюсь им, если кому-то еще это понадобится. Просто небольшое изменение, и это вернет расстояние в метрах:источник
В Mathematica
Он использует параметрическое описание сегмента и проецирует точку в линию, определенную сегментом. Поскольку параметр изменяется от 0 до 1 в сегменте, если проекция выходит за эти границы, мы вычисляем расстояние до соответствующей точки вместо прямой, перпендикулярной сегменту.
Результат печати:
Нанесите эти точки ближе, чем расстояние отсечки :
Контур Участка:
источник
Эй, я только что написал это вчера. Это в ActionScript 3.0, который в основном является Javascript, хотя у вас может не быть того же класса Point.
Кроме того, здесь есть довольно полное и читаемое обсуждение проблемы: notejot.com
источник
Для ленивых, вот мой порт Objective-C решения @ Grumdrig выше:
источник
return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)))
sqrtf(x) = x*x
.Не смог устоять перед написанием кода на python :)
То же самое для Фортрана :)
источник
Вот более полное изложение решения Грумдрига. Эта версия также возвращает самую близкую точку.
источник
Однолинейное решение с использованием арктангенсов:
Идея состоит в том, чтобы переместить A в (0, 0) и повернуть треугольник по часовой стрелке, чтобы заставить C лежать на оси X, когда это произойдет, By будет расстоянием.
C #
Одна строка C # (для преобразования в SQL)
источник
Рассмотрим эту модификацию ответа Грамдрига выше. Много раз вы обнаружите, что неточность с плавающей запятой может вызвать проблемы. Я использую двойники в версии ниже, но вы можете легко перейти на плавающие. Важной частью является то, что он использует эпсилон для обработки "помои". Кроме того, вы много раз захотите узнать, ГДЕ произошло пересечение или произошло ли оно вообще. Если возвращенное значение t <0,0 или> 1,0, столкновения не произошло. Тем не менее, даже если столкновения не произошло, много раз вы захотите узнать, где находится ближайшая точка на сегменте к P, и поэтому я использую qx и qy, чтобы вернуть это местоположение.
источник
Я предполагаю, что вы хотите найти самый короткийрасстояние между точкой и отрезком; Для этого вам нужно найти линию (lineA), которая перпендикулярна вашему отрезку (lineB), который проходит через вашу точку, определить пересечение между этой линией (lineA) и вашей линией, проходящей через ваш отрезок line (lineB). ; если эта точка находится между двумя точками вашего отрезка, то расстояние - это расстояние между вашей точкой и только что найденной точкой, которая является пересечением линии A и линии B; если точка не находится между двумя точками вашего отрезка, вам нужно получить расстояние между вашей точкой и ближе к двум концам отрезка; это можно легко сделать, взяв квадратное расстояние (чтобы избежать квадратного корня) между точкой и двумя точками отрезка; в зависимости от того, что ближе, возьмите квадратный корень этого.
источник
Реализация Grumdrig на C ++ / JavaScript была очень полезна для меня, поэтому я предоставил прямой порт Python, который я использую. Полный код здесь .
источник
Код Matlab со встроенным «самотестированием», если они вызывают функцию без аргументов:
источник
А теперь и мое решение ...... (Javascript)
Это очень быстро, потому что я стараюсь избегать любых функций Math.pow.
Как видите, в конце функции у меня есть расстояние до линии.
код взят из библиотеки http://www.draw2d.org/graphiti/jsdoc/#!/example
источник
закодировано в t-sql
точка (@px, @py) и отрезок линии проходит от (@ax, @ay) до (@bx, @by)
источник
Похоже, что почти все остальные в StackOverflow предоставили ответ (пока 23 ответа), так что вот мой вклад для C #. В основном это основано на ответе М. Каца, который, в свою очередь, основан на ответе Грумдрига.
И вот небольшая тестовая программа.
Как вы можете видеть, я попытался измерить разницу между использованием версии, которая избегает метода Sqrt (), и обычной версией. Мои тесты показывают, что вы можете сэкономить около 2,5%, но я даже не уверен в этом - различия в различных тестовых прогонах были одного порядка. Я также попытался измерить версию, опубликованную Матти (плюс очевидная оптимизация), и эта версия, кажется, примерно на 4% медленнее, чем версия, основанная на коде Каца / Грумдрига.
Изменить: Кстати, я также попытался измерить метод, который находит расстояние до бесконечной линии (не отрезок линии) с использованием перекрестного произведения (и Sqrt ()), и это примерно на 32% быстрее.
источник
Вот версия devnullicus's C ++, преобразованная в C #. Для моей реализации мне нужно было знать точку пересечения и найти его решение, чтобы хорошо работать.
источник
Вот он использует Swift
источник
C #
Адаптировано из @Grumdrig
источник
2D и 3D решение
Рассмотрим изменение базы таким образом, что отрезок линии становится
(0, 0, 0)-(d, 0, 0)
и точкой(u, v, 0)
. Кратчайшее расстояние происходит в этой плоскости и определяется как(Расстояние до одной из конечных точек или к опорной линии, в зависимости от проекции линии. ISO-расстояние локус состоит из двух полукругов и двух отрезков.)
В вышеприведенном выражении d - длина отрезка AB, а u, v - соответственно скалярное произведение и (модуль) перекрестное произведение AB / d (единичный вектор в направлении AB) и AC. Следовательно, в векторе
источник
см. набор инструментов Matlab GEOMETRY на следующем веб-сайте: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html
Ctrl + F и введите «сегмент», чтобы найти функции, связанные с сегментом линии. функции «plot_point_dist_2d.m» и «gment_point_dist_3d.m »- это то, что вам нужно.
Коды GEOMETRY доступны в версии C и версии C ++, версии FORTRAN77, версии FORTRAN90 и версии MATLAB.
источник
Версия AutoHotkeys, основанная на Javascript Джошуа:
источник
Я не видел здесь реализации Java, поэтому я перевел функцию Javascript с принятого ответа на код Java:
источник
Версия WPF:
источник
Вот код, который я в итоге написал. Этот код предполагает, что точка определена в форме
{x:5, y:7}
. Обратите внимание, что это не самый эффективный способ, но это самый простой и понятный код, который я мог придумать.источник
Вышеуказанная функция не работает на вертикальных линиях. Вот функция, которая работает нормально! Линия с точками p1, p2. и CheckPoint - это p;
источник
Это то же самое, что и ответ C ++, но перенесенный на паскаль. Порядок параметра точки изменился в соответствии с моим кодом, но это то же самое.
источник