поймите самую близкую мысль к строке
Я хотел бы иметь прямую функцию C# для понимания самой близкой мысли (от точки P) к линейному сегменту, AB. Абстрактная функция может быть похожей на это. Я имею, перерывают ТАК, но не нашел применимое (мной) решением.
public Point getClosestPointFromLine(Point A, Point B, Point P);
5 ответов
Вот 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
В качестве альтернативы:
Из Линия-пересечение линии , в Википедии. Во-первых, найдите 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
Кеширование, пропуск шагов и т. Д. Возможно по соображениям производительности.
Алгоритм будет довольно простым:
у вас 3 точки - треугольник. Оттуда вы сможете найти AB, AC, BC.
Выясните это: http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static#line_point_distance
Ваша точка ( 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
Найдите наклон a1 AB, разделив разность y на разность x; затем проведите перпендикулярную линию (с наклоном a2 = -1/a1, вам нужно решить для смещения (b2), подставив координаты P в y = a2*x + b2); тогда у вас есть две линии (т.е. два линейных уравнения), и вам нужно решить пересечение. Это и будет ваша ближайшая точка.
Сделайте математику правильно, и функция будет довольно тривиально написана.
Немного подробнее:
Original line:
y = a1 * x + b1
a1 = (By - Ay) / (Bx - Ax) <--
b1 = Ay - a1 * Ax <--
Perpendicular line:
y = a2 * x + b2
a2 = -1/a1 <--
b2 = Py - a2 * Px <--
Now you have P which lies on both lines:
y = a1 * x + b1
y = a2 * x + b2
--------------- subtract:
0 = (a1 - a2) * Px + (b1 - b2)
x = - (b1 - b2) / (a1 - a2) <--
y = a1 * x + b1 <--
Надеюсь, я ничего не напутал :) UPDATE Конечно, напортачил. Поделом мне за то, что я сначала не проработал все на бумаге. Я заслужил каждый даунвот, но я ожидал, что кто-то меня поправит. Исправлено (я надеюсь).
Стрелки указывают путь.
UPDATE Ах, угловые случаи. Да, некоторые языки не очень хорошо справляются с бесконечностью. Я ведь говорил, что решение не зависит от языка...
Вы можете проверить особые случаи, они довольно просты. Первый - когда разность x равна 0. Это означает, что линия вертикальна, и ближайшая точка лежит на горизонтальном перпендикуляре. Таким образом, x = Ax, y = Px.
Второй вариант - когда разность y равна 0, и верно обратное. Таким образом, x = Px, y = Ay
Ближайшая точка C будет на линии, наклон которой обратный AB и пересекается с P . Звучит так, как будто это домашнее задание, но я дам несколько довольно сильных советов в порядке увеличения уровня спойлеров:
Такая строчка может быть только одна.
Это система двух линейных уравнений. Просто решите для
xиy.Проведите отрезок между
AиB; назовите этоL. Уравнение дляLимеет видy = mx + b, гдеm- это отношение y-координат к x-координатам. Решите относительноb, используя в выраженииAилиB.Сделайте то же, что и выше, но для
CP. Теперь решите одновременную линейную систему уравнений.Поиск в Google даст вам множество примеров на выбор.