Я хотел бы иметь прямолинейную функцию С#, чтобы получить ближайшую точку (от точки P) до линейного сегмента AB. Абстрактная функция может выглядеть так. Я искал SO, но не нашел полезного (по мне) решения.
public Point getClosestPointFromLine(Point A, Point B, Point P);
Здесь 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
Кэширование, пропуски и т.д. возможны по соображениям производительности.
если кто-либо интересуется функцией С# XNA на основе вышеперечисленного:
public static Vector2 GetClosestPointOnLineSegment(Vector2 A, Vector2 B, Vector2 P)
{
Vector2 AP = P - A; //Vector from A to P
Vector2 AB = B - A; //Vector from A to B
float magnitudeAB = AB.LengthSquared(); //Magnitude of AB vector (it length squared)
float ABAPproduct = Vector2.Dot(AP, AB); //The DOT product of a_to_p and a_to_b
float distance = ABAPproduct / magnitudeAB; //The normalized "distance" from a to your closest point
if (distance < 0) //Check if P projection is over vectorAB
{
return A;
}
else if (distance > 1) {
return B;
}
else
{
return A + AB * 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
Ответ от Джастина Л. почти прекрасен, но он не проверяет, является ли нормализованное расстояние меньше 0 или выше величины АВ-вектора. Тогда это не сработает, когда P-векторная proyection выходит за пределы (от отрезка AB). Здесь скорректированный псевдокод:
function GetClosestPoint(A, B, P)
{
vectorAP = (p.x - a.x, p.y - a.y) //Vector from A to P
vectorAB = (b.x - a.x, b.y - a.y) //Vector from A to B
magnitudeAB = vectorAB[0]^2 + vectorAB[1]^2
//Magnitude of AB vector (it length)
ABAPproduct = vectorAB[0]*vectorAP[0] + vectorAB[1]*vectorAP[1]
//The product of a_to_p and a_to_b
distance = ABAPproduct / magnitudeAB
//The normalized "distance" from a to your closest point
if ( distance < 0) //Check if P projection is over vectorAB
{
returnPoint.x = a.x
returnPoint.y = a.y
}
else if (distance > magnitudeAB)
{
returnPoint.x = b.x
returnPoint.y = b.y
}
else
{
returnPoint.x = a.x + vectorAB[0]*distance
returnPoint.y = a.y + vectorAB[1]*distance
}
}
Найдите наклон 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 <--
Надеюсь, я где-то не испортил:) ОБНОВЛЕНИЕ Конечно. Служите мне правильно, чтобы не работать на бумаге в первую очередь. Я заслужил каждый снимок, но я ожидал, что кто-то исправит меня. Исправлено (надеюсь).
Стрелки указывают путь.
ОБНОВЛЕНИЕ А, угловые случаи. Да, некоторые языки не справляются с бесконечностями. Я действительно сказал, что решение не было языка...
Вы можете проверить специальные случаи, они довольно просты. Первый - когда разность х равна 0. Это означает, что линия вертикальна, а ближайшая точка находится в горизонтальном перпендикуляре. Таким образом, x = Ax, y = Px.
Во-вторых, когда y-разность равна 0, и наоборот. Таким образом, x = Px, y = Ay
Этот ответ основан на идеях проективной геометрии.
Вычислить поперечное произведение (Ax, Ay, 1) & times; (Bx, By, 1) = (u, v, w). Полученный вектор описывает линию, соединяющую А и В: она имеет уравнение ux + vy + w = 0. Но вы также можете интерпретировать (u, v, 0) как точку, бесконечно удаленную в направлении, перпендикулярном этой линии. Выполняя другой кросс-продукт, вы получаете линию, соединяющую точку шляпы с P: (u, v, 0) & times; (Px, Py, 1). И чтобы пересечь эту линию с линией AB, вы делаете другое кросс-произведение: ((u, v, 0) & times; (Px, Py, 1)) & times; (u, v, w). Результатом будет однородный координатный вектор (x, y, z), из которого вы можете прочитать координаты этой ближайшей точки как (x/z, y/z).
Возьмите все вместе, и вы получите следующую формулу:
Используя систему компьютерной алгебры, вы можете найти результирующие координаты следующим образом:
x = ((Ax - Bx)*Px + (Ay - By)*Py)*(Ax - Bx) + (Ay*Bx - Ax*By)*(Ay - By)
y = -(Ay*Bx - Ax*By)*(Ax - Bx) + ((Ax - Bx)*Px + (Ay - By)*Py)*(Ay - By)
z = (Ax - Bx)^2 + (Ay - By)^2
Как вы заметили, существует много повторяющихся терминов. Изобретая (в значительной степени произвольные) имена для них, вы можете получить следующий окончательный результат, написанный в псевдокоде:
dx = A.x - B.x
dy = A.y - B.y
det = A.y*B.x - A.x*B.y
dot = dx*P.x + dy*P.y
x = dot*dx + det*dy
y = dot*dy - det*dx
z = dx*dx + dy*dy
zinv = 1/z
return new Point(x*zinv, y*zinv)
Преимущества такого подхода:
Ближайшая точка C будет на линии, наклон которой является обратным AB и пересекается с P. Это звучит так, будто это может быть домашнее задание, но я дам несколько довольно сильных намеков, чтобы увеличить уровень оповещений:
Может быть только одна такая строка.
Это система двух линейных уравнений. Просто решите для x и y.
Нарисуйте сегмент линии между A и B; назовите это L. Уравнение для L составляет y = mx + b, где m - отношение y-координат к x-координатам. Решите для B используя A или B в выражении.
Сделайте то же, что и выше, но для CP. Теперь разрешите одновременную линейную систему уравнений.
Поиск в Google даст вам список примеров.
Я написал это давным-давно, он не сильно отличается от того, что говорили другие, но это решение для копирования/вставки на С#, если у вас есть класс (или структура) с именем PointF с членами X и Y:
private static PointF ClosestPointToSegment(PointF P, PointF A, PointF B)
{
PointF a_to_p = new PointF(), a_to_b = new PointF();
a_to_p.X = P.X - A.X;
a_to_p.Y = P.Y - A.Y; // # Storing vector A->P
a_to_b.X = B.X - A.X;
a_to_b.Y = B.Y - A.Y; // # Storing vector A->B
float atb2 = a_to_b.X * a_to_b.X + a_to_b.Y * a_to_b.Y;
float atp_dot_atb = a_to_p.X * a_to_b.X + a_to_p.Y * a_to_b.Y; // The dot product of a_to_p and a_to_b
float t = atp_dot_atb / atb2; // # The normalized "distance" from a to the closest point
return new PointF(A.X + a_to_b.X * t, A.Y + a_to_b.Y * t);
}
Обновление. Рассматривая комментарии, похоже, что я адаптировал его к С# из того же исходного кода, что и в принятом ответе.
Вот методы расширения, которые должны выполнить трюк:
public static double DistanceTo(this Point from, Point to)
{
return Math.Sqrt(Math.Pow(from.X - to.X, 2) + Math.Pow(from.Y - to.Y, 2));
}
public static double DistanceTo(this Point point, Point lineStart, Point lineEnd)
{
double tI = ((lineEnd.X - lineStart.X) * (point.X - lineStart.X) + (lineEnd.Y - lineStart.Y) * (point.Y - lineStart.Y)) / Math.Pow(lineStart.DistanceTo(lineEnd), 2);
double dP = ((lineEnd.X - lineStart.X) * (point.Y - lineStart.Y) - (lineEnd.Y - lineStart.Y) * (point.X - lineStart.X)) / lineStart.DistanceTo(lineEnd);
if (tI >= 0d && tI <= 1d)
return Math.Abs(dP);
else
return Math.Min(point.DistanceTo(lineStart), point.DistanceTo(lineEnd));
}
Затем просто позвоните:
P.DistanceTo(A, B);
Чтобы получить расстояние от точки "P" от линии | AB |. Это должно быть легко изменить для PointF.
Поиск ближайшей точки - это просто поиск минимального расстояния. LINQ имеет методы для этого.
Если кто-то ищет способ сделать это с помощью Java + LibGdx:
Intersector.nearestSegmentPoint
Алгоритм будет довольно прост:
у вас есть 3 балла - треугольник. Оттуда вы сможете найти AB, AC, BC.
Вот это: http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static#line_point_distance