Как найти точку на ребре, которая является ближайшей к другой точке

Question

Я ищу способ эффективно найти точку на ребре, которая является ближайшей к какой-либо другой точке.

Допустим, я знаю две точки, которые являются вершинами ребра.Я могу рассчитать уравнение линии, которая пересекает эти точки.

Как лучше всего рассчитать точку на краю, которая является ближайшей точкой к какой-либо другой точке на плоскости.

Я бы опубликовал изображение, но у меня недостаточно репутацииточек.

Answer 1

Предположим, что линия определяется двумя точками (x1, y1), (x2, y2), а «другая точка» - (a, b).Точка, которую вы ищете: (x, y).

Вы можете легко найти уравнение черной линии.Чтобы найти уравнение синей линии, используйте тот факт, что m1 * m2 = -1 (m1 и m2 - наклоны двух линий).

Очевидно, что точка, которую вы ищете, является пересечением между двумялинии.

Есть два исключения из того, что я говорил:

1. Если x1 = x2, то (x, y) = (x1,b).
2. Если y1 = y2, то (x, y) = (a, y1).

Следующая функция Python находит точку (если вы не знаете Pythonпросто подумайте об этом как о псевдо-коде):

def get_closest_point( x1,y1, x2,y2, a,b ):
    if x1==x2: return (x1,b)
    if y1==y2: return (a,y1)
    m1 = (y2-y1)/(x2-x1)
    m2 = -1/m1
    x = (m1*x1-m2*a+b-y1) / (m1-m2)
    y = m2*(x-a)+b
    return (x,y)

Answer 2

У вас есть три зоны для рассмотрения.«Перпендикулярный» подход предназначен для зоны в середине:

Для двух других зон расстояние - это расстояние до ближайшей конечной точки сегмента.

Уравнение для сегмента:

y[x] = m x + b

Где

  m -> -((Ay - By)/(-Ax + By)), 
  b -> -((-Ax By + Ay By)/(Ax - By))  

И перпендикуляры имеют наклон -1 / м

Уравнения для перпендикулярного прохождения через A:

  y[x] = (-Ax + By)/(Ay - By) x + (Ax^2 + Ay^2 - Ax By - Ay By)/(Ay - By)

И перпендикулярное прохождение через B - это то же самое, что и А и В в приведенном выше уравнении.

Таким образом, вы можете узнать, в какой области находится ваша точка, введя ее координату x в приведенных выше уравнениях, а затем сравнив координату y точки с результатом y [x]

Edit

Как узнать, в каком регионе находится ваша точка?

Предположим, что Ax ≤ Bx (если все иначе, просто измените метки точек в следующих формулах)

Мы назовем вашу точку {x0, y0}

1) Рассчитайте

 f[x0] =  (-Ax + By)/(Ay - By) x0 + (Ax^2 + Ay^2 - Ax By - Ay By)/(Ay - By)

и сравните с y0.

Если y0> f [x0], то ваша точка находится в зеленом поле на рисунке выше, а ближайшая точка - A.

2) Иначе, вычислите

g[x0] =  (-Bx + Ay)/(By - Ay) x0 + (Bx^2 + By^2 - Bx Ay - By Ay)/(By - Ay)  

и сравните с y0.

Если y0

3) Иначе, вы находитесь в «перпендикулярной светло-голубой зоне», и любой другой ответ подскажет вам, как рассчитать ближайшую точку и расстояние (я не собираюсьПлагиат :))

HTH!

Answer 3

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

Линия, образующая ребро между двумя точками (x1, y1), (x2, y2), представлена ​​как функция

y = mx + b

(Вы сами понимаете, м и б, но это элементарно)

То, что вы хотите сделать, это минимизировать расстояние от вашей точки (p1, p2) до точки на этой линии, т.е.

(p1-x)^2 + (p2-y)^2     (equation I)

с учетом уравнения

y = mx + b              (equation II)

Подставьте уравнение II в уравнение I и решите для х. Вы получите два решения; выберите тот, который дает меньшее значение в уравнении I.

Answer 4

Я могу описать, что вы хотите сделать, в геометрических терминах, но у меня нет алгоритма под рукой. Это поможет?

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

Тогда вы хотите найти пересечение двух линий.