Dada una línea que pasa por dos puntos A y B y un punto C arbitrario en un plano tridimensional, la tarea es encontrar la distancia más corta entre el punto C y la línea que pasa por los puntos A y B.
Ejemplos:
Input: A = (5, 2, 1), B = (3, 1, -1), C = (0, 2, 3) Output: Shortest Distance is 5 Input: A = (4, 2, 1), B = (3, 2, 1), C = (0, 2, 0) Output: Shortest Distance is 1
Considere un punto C y una línea que pasa por A y B como se muestra en la siguiente figura.
Ahora considere los vectores AB y AC y la distancia más corta como CD. La distancia más corta es siempre la distancia perpendicular. El punto D se toma sobre AB tal que CD es perpendicular a AB.
Construya BP y CP como se muestra en la figura para formar un paralelogramo. Ahora C es un vértice del paralelogramo ABPC y CD es perpendicular al Lado AB. Por lo tanto, CD es la altura del paralelogramo.
Nota: En el caso de que D no caiga sobre el segmento de línea AB habrá un punto D’ tal que PD’ sea perpendicular a AB y D’ esté sobre el segmento de línea AB con CD = PD’.
La magnitud del producto vectorial AB y AC da el área del paralelogramo. Además, el área de un paralelogramo es Base * Altura = AB * CD . Asi que,
CD = |ABxAC| / |AB|
A continuación se muestra el programa CPP para encontrar la distancia más corta:
CPP
// C++ program to find the Shortest
// Distance Between A line and a
// Given point.
#include<bits/stdc++.h>
using namespace std;
class Vector {
private:
int x, y, z;
// 3D Coordinates of the Vector
public:
Vector(int x, int y, int z)
{
// Constructor
this->x = x;
this->y = y;
this->z = z;
}
Vector operator+(Vector v); // ADD 2 Vectors
Vector operator-(Vector v); // Subtraction
int operator^(Vector v); // Dot Product
Vector operator*(Vector v); // Cross Product
float magnitude()
{
return sqrt(pow(x, 2) + pow(y, 2) + pow(z, 2));
}
friend ostream& operator<<(ostream& out, const Vector& v);
// To output the Vector
};
// ADD 2 Vectors
Vector Vector::operator+(Vector v)
{
int x1, y1, z1;
x1 = x + v.x;
y1 = y + v.y;
z1 = z + v.z;
return Vector(x1, y1, z1);
}
// Subtract 2 vectors
Vector Vector::operator-(Vector v)
{
int x1, y1, z1;
x1 = x - v.x;
y1 = y - v.y;
z1 = z - v.z;
return Vector(x1, y1, z1);
}
// Dot product of 2 vectors
int Vector::operator^(Vector v)
{
int x1, y1, z1;
x1 = x * v.x;
y1 = y * v.y;
z1 = z * v.z;
return (x1 + y1 + z1);
}
// Cross product of 2 vectors
Vector Vector::operator*(Vector v)
{
int x1, y1, z1;
x1 = y * v.z - z * v.y;
y1 = z * v.x - x * v.z;
z1 = x * v.y - y * v.x;
return Vector(x1, y1, z1);
}
// Display Vector
ostream& operator<<(ostream& out,
const Vector& v)
{
out << v.x << "i ";
if (v.y >= 0)
out << "+ ";
out << v.y << "j ";
if (v.z >= 0)
out << "+ ";
out << v.z << "k" << endl;
return out;
}
// calculate shortest dist. from point to line
float shortDistance(Vector line_point1, Vector line_point2,
Vector point)
{
Vector AB = line_point2 - line_point1;
Vector AC = point - line_point1;
float area = Vector(AB * AC).magnitude();
float CD = area / AB.magnitude();
return CD;
}
// Driver program
int main()
{
// Taking point C as (2, 2, 2)
// Line Passes through A(4, 2, 1)
// and B(8, 4, 2).
Vector line_point1(4, 2, 1), line_point2(8, 4, 2);
Vector point(2, 2, 2);
cout << "Shortest Distance is : "
<< shortDistance(line_point1, line_point2, point);
return 0;
}
Shortest Distance is : 1.63299
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por KartikArora y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA