Distancia mínima de un punto al segmento de línea usando Vectores

Posted on by Rudeus Greyrat

Dadas las coordenadas de dos extremos A(x1, y1) , B(x2, y2) del segmento de recta y las coordenadas de un punto E(x, y) ; la tarea es encontrar la distancia mínima desde el punto hasta el segmento de línea formado con las coordenadas dadas.
Tenga en cuenta que ambos extremos de una línea pueden llegar al infinito, es decir, una línea no tiene puntos finales. Por otro lado, un segmento de línea tiene puntos de inicio y final debido a que la longitud del segmento de línea es fija.
Ejemplos: 

Entrada: A = {0, 0}, B = {2, 0}, E = {4, 0} 

Salida: 2 
Para encontrar la distancia, se debe encontrar el producto escalar entre los vectores AB, BE y 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 . SER = (AB x * BE x + AB y * BE y ) = (2 * 2 + 0 * 0) = 4 
AB . AE = (AB x * AE x + AB y * AE y ) = (2 * 4 + 0 * 0) = 8 
Por lo tanto, el punto más cercano de E al segmento de línea es el punto B. 
Distancia mínima = BE = 

= 2
Entrada: A = {0, 0}, B = {2, 0}, E = {1, 1} 
Salida: 1 

Enfoque: La idea es utilizar el concepto de vectores para resolver el problema ya que el punto más cercano siempre se encuentra en el segmento de línea. Suponiendo que la dirección del vector AB es de A a B, surgen tres casos:  

1. El punto más cercano al punto E en el segmento de línea AB es el mismo punto B si el producto escalar del vector AB(A a B) y el vector BE(B a E) es positivo donde E es el punto dado. Desde AB. BE > 0 , el punto dado se encuentra en la misma dirección que el vector AB y el punto más cercano debe ser el mismo B porque el punto más cercano se encuentra en el segmento de línea. 
 

2. El punto más cercano al punto E en el segmento de línea AB es el mismo punto A si el producto escalar del vector AB(A a B) y el vector AE(A a E) es negativo donde E es el punto dado. Desde AB. AE < 0 , el punto dado se encuentra en la dirección opuesta al segmento de línea AB y el punto más cercano debe ser el mismo A porque el punto más cercano se encuentra en el segmento de línea. 
 

3. De lo contrario, si el producto escalar es 0, entonces el punto E es perpendicular al segmento AB y la distancia perpendicular al punto E dado desde el segmento AB es la distancia más corta. Si algún punto arbitrario F es el punto en el segmento de línea que es perpendicular a E, entonces la distancia perpendicular se puede calcular como |EF| = |(AB X AE)/|AB|| 
 

A continuación se muestra la implementación del enfoque anterior: 

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 = B.F - A.F;
    AB.S = B.S - A.S;
 
    // vector BP
    pair<double, double> BE;
    BE.F = E.F - B.F;
    BE.S = E.S - B.S;
 
    // vector AP
    pair<double, double> AE;
    AE.F = E.F - A.F,
    AE.S = E.S - A.S;
 
    // 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 = E.S - B.S;
        double x = E.F - B.F;
        reqAns = sqrt(x * x + y * y);
    }
 
    // Case 2
    else if (AB_AE < 0) {
        double y = E.S - A.S;
        double x = E.F - A.F;
        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

// Java implementation of the approach
class GFG
{
 
static class pair
{
    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 = B.F - A.F;
    AB.S = B.S - A.S;
 
    // vector BP
    pair BE = new pair();
    BE.F = E.F - B.F;
    BE.S = E.S - B.S;
 
    // vector AP
    pair AE = new pair();
    AE.F = E.F - A.F;
    AE.S = E.S - A.S;
 
    // 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 = E.S - B.S;
        double x = E.F - B.F;
        reqAns = Math.sqrt(x * x + y * y);
    }
 
    // Case 2
    else if (AB_AE < 0)
    {
        double y = E.S - A.S;
        double x = E.F - A.F;
        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
{
 
class pair
{
    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 = B.F - A.F;
    AB.S = B.S - A.S;
 
    // vector BP
    pair BE = new pair();
    BE.F = E.F - B.F;
    BE.S = E.S - B.S;
 
    // vector AP
    pair AE = new pair();
    AE.F = E.F - A.F;
    AE.S = E.S - A.S;
 
    // 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 = E.S - B.S;
        double x = E.F - B.F;
        reqAns = Math.Sqrt(x * x + y * y);
    }
 
    // Case 2
    else if (AB_AE < 0)
    {
        double y = E.S - A.S;
        double x = E.F - A.F;
        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>
Producción: 

1

 

Complejidad de tiempo: O(1 )

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por rrlinus y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *