Минимальное расстояние от точки до сегмента линии с использованием векторов

Опубликовано: 5 Января, 2022

Даны координаты двух конечных точек A (x1, y1) , B (x2, y2) отрезка прямой и координаты точки E (x, y) ; задача - найти минимальное расстояние от точки до отрезка, образованного с заданными координатами.
Обратите внимание, что оба конца линии могут уходить в бесконечность, т.е. линия не имеет конечных точек. С другой стороны, линейный сегмент имеет начальную и конечную точки, благодаря которым длина линейного сегмента является фиксированной.
Примеры:

Input: A = {0, 0}, B = {2, 0}, E = {4, 0} 
Output: 2 
To find the distance, dot product has to be found between vectors AB, BE and AB, AE. 
AB = (x2 – x1, y2 – y1) = (2 – 0, 0 – 0) = (2, 0) 
BE = (x – x2, y – y2) = (4 – 2, 0 – 0) = (2, 0) 
AE = (x – x1, y – y1) = (4 – 0, 0 – 0) = (4, 0) 
AB . BE = (ABx * BEx + ABy * BEy) = (2 * 2 + 0 * 0) = 4 
AB . AE = (ABx * AEx + ABy * AEy) = (2 * 4 + 0 * 0) = 8 
Therefore, nearest point from E to line segment is point B. 
Minimum Distance = BE = 

= 2
Input: A = {0, 0}, B = {2, 0}, E = {1, 1} 
Output: 1 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать концепцию векторов для решения проблемы, поскольку ближайшая точка всегда лежит на отрезке линии. Предполагая, что вектор AB направлен от A к B, возникают три случая:

1. Ближайшей точкой от точки E на отрезке AB является сама точка B , если скалярное произведение вектора AB (от A до B) и вектора BE (от B до E) положительно, где E - заданная точка. Поскольку AB. BE> 0 , данная точка лежит в том же направлении, что и вектор AB, и ближайшая точка должна быть самой B, потому что ближайшая точка лежит на отрезке прямой.

2. Ближайшей точкой от точки E на отрезке AB является сама точка A , если скалярное произведение вектора AB (от A до B) и вектора BE (от B до E) отрицательно, где E - заданная точка. Поскольку AB. BE <0 , данная точка лежит в направлении, противоположном направлению отрезка AB, и ближайшая точка должна быть самой A, потому что ближайшая точка лежит на отрезке прямой.

3. Если скалярное произведение равно 0, то точка E перпендикулярна отрезку AB, а расстояние по перпендикуляру к данной точке E от отрезка AB является кратчайшим расстоянием. Если некоторая произвольная точка F является точкой на отрезке, перпендикулярном E, то перпендикулярное расстояние можно вычислить как | EF | = | (AB X AE) / | AB ||

Ниже представлена реализация описанного выше подхода:

C ++

// C++ implementation of the approach
#include <bits/stdc++.h>
// To store the point
#define Point pair<double, double>
#define F first
#define S second
using namespace std;
// Function to return the minimum distance
// between a line segment AB and a point E
double minDistance(Point A, Point B, Point E)
{
// vector AB
pair< double , double > AB;
AB.F = BF - AF;
AB.S = BS - AS;
// vector BP
pair< double , double > BE;
BE.F = EF - BF;
BE.S = ES - BS;
// vector AP
pair< double , double > AE;
AE.F = EF - AF,
AE.S = ES - AS;
// Variables to store dot product
double AB_BE, AB_AE;
// Calculating the dot product
AB_BE = (AB.F * BE.F + AB.S * BE.S);
AB_AE = (AB.F * AE.F + AB.S * AE.S);
// Minimum distance from
// point E to the line segment
double reqAns = 0;
// Case 1
if (AB_BE > 0) {
// Finding the magnitude
double y = ES - BS;
double x = EF - BF;
reqAns = sqrt (x * x + y * y);
}
// Case 2
else if (AB_AE < 0) {
double y = ES - AS;
double x = EF - AF;
reqAns = sqrt (x * x + y * y);
}
// Case 3
else {
// Finding the perpendicular distance
double x1 = AB.F;
double y1 = AB.S;
double x2 = AE.F;
double y2 = AE.S;
double mod = sqrt (x1 * x1 + y1 * y1);
reqAns = abs (x1 * y2 - y1 * x2) / mod;
}
return reqAns;
}
// Driver code
int main()
{
Point A = make_pair(0, 0);
Point B = make_pair(2, 0);
Point E = make_pair(1, 1);
cout << minDistance(A, B, E);
return 0;
}

Джава

// Java implementation of the approach
class GFG
{
static pair class
{
double F, S;
public pair( double F, double S)
{
this .F = F;
this .S = S;
}
public pair() {
}
}
// Function to return the minimum distance
// between a line segment AB and a point E
static double minDistance(pair A, pair B, pair E)
{
// vector AB
pair AB = new pair();
AB.F = BF - AF;
AB.S = BS - AS;
// vector BP
pair BE = new pair();
BE.F = EF - BF;
BE.S = ES - BS;
// vector AP
pair AE = new pair();
AE.F = EF - AF;
AE.S = ES - AS;
// Variables to store dot product
double AB_BE, AB_AE;
// Calculating the dot product
AB_BE = (AB.F * BE.F + AB.S * BE.S);
AB_AE = (AB.F * AE.F + AB.S * AE.S);
// Minimum distance from
// point E to the line segment
double reqAns = 0 ;
// Case 1
if (AB_BE > 0 )
{
// Finding the magnitude
double y = ES - BS;
double x = EF - BF;
reqAns = Math.sqrt(x * x + y * y);
}
// Case 2
else if (AB_AE < 0 )
{
double y = ES - AS;
double x = EF - AF;
reqAns = Math.sqrt(x * x + y * y);
}
// Case 3
else
{
// Finding the perpendicular distance
double x1 = AB.F;
double y1 = AB.S;
double x2 = AE.F;
double y2 = AE.S;
double mod = Math.sqrt(x1 * x1 + y1 * y1);
reqAns = Math.abs(x1 * y2 - y1 * x2) / mod;
}
return reqAns;
}
// Driver code
public static void main(String[] args)
{
pair A = new pair( 0 , 0 );
pair B = new pair( 2 , 0 );
pair E = new pair( 1 , 1 );
System.out.print(( int )minDistance(A, B, E));
}
}
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
from math import sqrt
# Function to return the minimum distance
# between a line segment AB and a point E
def minDistance(A, B, E) :
# vector AB
AB = [ None , None ];
AB[ 0 ] = B[ 0 ] - A[ 0 ];
AB[ 1 ] = B[ 1 ] - A[ 1 ];
# vector BP
BE = [ None , None ];
BE[ 0 ] = E[ 0 ] - B[ 0 ];
BE[ 1 ] = E[ 1 ] - B[ 1 ];
# vector AP
AE = [ None , None ];
AE[ 0 ] = E[ 0 ] - A[ 0 ];
AE[ 1 ] = E[ 1 ] - A[ 1 ];
# Variables to store dot product
# Calculating the dot product
AB_BE = AB[ 0 ] * BE[ 0 ] + AB[ 1 ] * BE[ 1 ];
AB_AE = AB[ 0 ] * AE[ 0 ] + AB[ 1 ] * AE[ 1 ];
# Minimum distance from
# point E to the line segment
reqAns = 0 ;
# Case 1
if (AB_BE > 0 ) :
# Finding the magnitude
y = E[ 1 ] - B[ 1 ];
x = E[ 0 ] - B[ 0 ];
reqAns = sqrt(x * x + y * y);
# Case 2
elif (AB_AE < 0 ) :
y = E[ 1 ] - A[ 1 ];
x = E[ 0 ] - A[ 0 ];
reqAns = sqrt(x * x + y * y);
# Case 3
else :
# Finding the perpendicular distance
x1 = AB[ 0 ];
y1 = AB[ 1 ];
x2 = AE[ 0 ];
y2 = AE[ 1 ];
mod = sqrt(x1 * x1 + y1 * y1);
reqAns = abs (x1 * y2 - y1 * x2) / mod;
return reqAns;
# Driver code
if __name__ = = "__main__" :
A = [ 0 , 0 ];
B = [ 2 , 0 ];
E = [ 1 , 1 ];
print (minDistance(A, B, E));
# This code is contributed by AnkitRai01

C #

// C# implementation of the approach
using System;
class GFG
{
pair class
{
public double F, S;
public pair( double F, double S)
{
this .F = F;
this .S = S;
}
public pair() {
}
}
// Function to return the minimum distance
// between a line segment AB and a point E
static double minDistance(pair A, pair B, pair E)
{
// vector AB
pair AB = new pair();
AB.F = BF - AF;
AB.S = BS - AS;
// vector BP
pair BE = new pair();
BE.F = EF - BF;
BE.S = ES - BS;
// vector AP
pair AE = new pair();
AE.F = EF - AF;
AE.S = ES - AS;
// Variables to store dot product
double AB_BE, AB_AE;
// Calculating the dot product
AB_BE = (AB.F * BE.F + AB.S * BE.S);
AB_AE = (AB.F * AE.F + AB.S * AE.S);
// Minimum distance from
// point E to the line segment
double reqAns = 0;
// Case 1
if (AB_BE > 0)
{
// Finding the magnitude
double y = ES - BS;
double x = EF - BF;
reqAns = Math.Sqrt(x * x + y * y);
}
// Case 2
else if (AB_AE < 0)
{
double y = ES - AS;
double x = EF - AF;
reqAns = Math.Sqrt(x * x + y * y);
}
// Case 3
else
{
// Finding the perpendicular distance
double x1 = AB.F;
double y1 = AB.S;
double x2 = AE.F;
double y2 = AE.S;
double mod = Math.Sqrt(x1 * x1 + y1 * y1);
reqAns = Math.Abs(x1 * y2 - y1 * x2) / mod;
}
return reqAns;
}
// Driver code
public static void Main(String[] args)
{
pair A = new pair(0, 0);
pair B = new pair(2, 0);
pair E = new pair(1, 1);
Console.Write(( int )minDistance(A, B, E));
}
}
// This code is contributed by 29AjayKumar

Javascript

<script>
// JavaScript implementation of the approach
// Function to return the minimum distance
// between a line segment AB and a point E
function minDistance( A, B, E)
{
// vector AB
var AB=[];
AB.push (B[0] - A[0]);
AB.push(B[1] - A[1]);
// vector BP
var BE=[];
BE.push(E[0] - B[0]);
BE.push(E[1] - B[1]);
// vector AP
var AE=[];
AE.push(E[0] - A[0]),
AE.push(E[1] - A[1]);
// Variables to store dot product
var AB_BE, AB_AE;
// Calculating the dot product
AB_BE=(AB[0] * BE[0] + AB[1] * BE[1]);
AB_AE=(AB[0] * AE[0] + AB[1] * AE[1]);
// Minimum distance from
// point E to the line segment
var reqAns = 0;
// Case 1
if (AB_BE > 0) {
// Finding the magnitude
var y = E[1] - B[1];
var x = E[0] - B[0];
reqAns = Math.sqrt(x * x + y * y);
}
// Case 2
else if (AB_AE < 0) {
var y = E[1] - A[1];
var x = E[0] - A[0];
reqAns = Math.sqrt(x * x + y * y);
}
// Case 3
else {
// Finding the perpendicular distance
var x1 = AB[0];
var y1 = AB[1];
var x2 = AE[0];
var y2 = AE[1];
var mod = Math.sqrt(x1 * x1 + y1 * y1);
reqAns = Math.abs(x1 * y2 - y1 * x2) / mod;
}
return reqAns;
}
var A =[0, 0];
var B = [2, 0];
var E = [1, 1];
document.write( minDistance(A, B, E));
</script>
Выход:
 1

Сложность времени: O (1)

Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ