Given a line passing through two points A and B and an arbitrary point C in a 3-D plane, the task is to find the shortest distance between the point C and the line passing through the points A and B.
Examples:
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
Consider a point C and a line that passes through A and B as shown in the below figure.
Now Consider the vectors, AB and AC and the shortest distance as CD. The Shortest Distance is always the perpendicular distance. The point D is taken on AB such that CD is perpendicular to AB.
Construct BP and CP as shown in the figure to form a Parallelogram. Now C is a vertex of parallelogram ABPC and CD is perpendicular to Side AB. Hence CD is the height of the parallelogram.
Note: In the case when D does not fall on line segment AB there will be a point D’ such that PD’ is perpendicular to AB and D’ lies on line segment AB with CD = PD’.
The magnitude of cross product AB and AC gives the Area of the parallelogram. Also, the area of a parallelogram is Base * Height = AB * CD. So,
CD = |ABxAC| / |AB|
Below is the CPP program to find the shortest distance:
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 Vectorpublic: 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 VectorsVector 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 vectorsVector 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 vectorsint 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 vectorsVector 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 Vectorostream& 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 linefloat 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 programint 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;} |
Java
// Java program to find the Shortest// Distance Between A line and a// Given point.public 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; } // ADD 2 Vectors public Vector add(Vector v) { int x1, y1, z1; x1 = x + v.x; y1 = y + v.y; z1 = z + v.z; return new Vector(x1, y1, z1); } // Subtract 2 vectors public Vector subtract(Vector v) { int x1, y1, z1; x1 = x - v.x; y1 = y - v.y; z1 = z - v.z; return new Vector(x1, y1, z1); } // Dot product of 2 vectors public int dotProduct(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 public Vector crossProduct(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 new Vector(x1, y1, z1); } public float magnitude() { return (float)Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2) + Math.pow(z, 2)); } public String toString() { return x + "i " + (y >= 0 ? "+ " : "") + y + "j " + (z >= 0 ? "+ " : "") + z + "k"; } // calculate shortest dist. from point to line public static float shortDistance(Vector line_point1, Vector line_point2, Vector point) { Vector AB = line_point2.subtract(line_point1); Vector AC = point.subtract(line_point1); float area = (AB.crossProduct(AC)).magnitude(); float CD = area / AB.magnitude(); return CD; } // Driver Code public static void main(String[] args) { // Taking point C as (2, 2, 2) // Line Passes through A(4, 2, 1) // and B(8, 4, 2). Vector line_point1 = new Vector(4, 2, 1); Vector line_point2 = new Vector(8, 4, 2); Vector point = new Vector(2, 2, 2); System.out.println("Shortest Distance is : " + shortDistance(line_point1, line_point2, point)); }} |
Python
import mathclass Vector: def __init__(self, x, y, z): # Constructor self.x = x self.y = y self.z = z # ADD 2 Vectors def __add__(self, v): x1, y1, z1 = self.x + v.x, self.y + v.y, self.z + v.z return Vector(x1, y1, z1) # Subtract 2 vectors def __sub__(self, v): x1, y1, z1 = self.x - v.x, self.y - v.y, self.z - v.z return Vector(x1, y1, z1) # Dot product of 2 vectors def __xor__(self, v): x1, y1, z1 = self.x * v.x, self.y * v.y, self.z * v.z return x1 + y1 + z1 # Cross product of 2 vectors def __mul__(self, v): x1 = self.y * v.z - self.z * v.y y1 = self.z * v.x - self.x * v.z z1 = self.x * v.y - self.y * v.x return Vector(x1, y1, z1) # Display Vector def __str__(self): out = self.x+"i " if self.y >= 0: out += "+ " out += self.y+"j " if self.z >= 0: out += "+ " out += self.z+"k\n" return out def magnitude(self): return math.sqrt(self.x ** 2 + self.y ** 2 + self.z ** 2)# calculate shortest dist. from point to linedef shortDistance(line_point1, line_point2, point): AB = line_point2 - line_point1 AC = point - line_point1 area = (AB * AC).magnitude() CD = area / AB.magnitude() return CD# Driver programif __name__ == "__main__": # Taking point C as (2, 2, 2) # Line Passes through A(4, 2, 1) # and B(8, 4, 2). line_point1 = Vector(4, 2, 1) line_point2 = Vector(8, 4, 2) point = Vector(2, 2, 2) print("Shortest Distance is:", shortDistance(line_point1, line_point2, point)) |
C#
// C# program to find the Shortest// Distance Between A line and a// Given point.using System;using System.Collections.Generic;class Vector { public int x, y, z; // 3D Coordinates of the Vector public Vector(int x1, int y1, int z1) { // Constructor x = x1; y = y1; z = z1; } public double magnitude() { return Math.Sqrt(Math.Pow(x, 2) + Math.Pow(y, 2) + Math.Pow(z, 2)); } // To output the Vector // ADD 2 Vectors public static Vector operator + (Vector v1, Vector v) { int x1, y1, z1; x1 = v1.x + v.x; y1 = v1.y + v.y; z1 = v1.z + v.z; return new Vector(x1, y1, z1); } // Subtract 2 vectors public static Vector operator - (Vector v1, Vector v) { int x1, y1, z1; x1 = v1.x - v.x; y1 = v1.y - v.y; z1 = v1.z - v.z; return new Vector(x1, y1, z1); } // Cross product of 2 vectors public static Vector operator*(Vector v, Vector v1) { int x1, y1, z1; x1 = v1.y * v.z - v1.z * v.y; y1 = v1.z * v.x - v1.x * v.z; z1 = v1.x * v.y - v1.y * v.x; return new Vector(x1, y1, z1); }}class GFG { // calculate shortest dist. from point to line static double shortDistance(Vector line_point1, Vector line_point2, Vector point) { Vector AB = line_point2 - line_point1; Vector AC = point - line_point1; double area = (AB * AC).magnitude(); double CD = area / AB.magnitude(); return CD; } // Driver program public static void Main(string[] args) { // Taking point C as (2, 2, 2) // Line Passes through A(4, 2, 1) // and B(8, 4, 2). Vector line_point1 = new Vector(4, 2, 1); Vector line_point2 = new Vector(8, 4, 2); Vector point = new Vector(2, 2, 2); Console.WriteLine("Shortest Distance is : " + shortDistance(line_point1, line_point2, point)); }}// This code is contributed by phasing17 |
Javascript
class Vector { constructor(x, y, z) { // Constructor this.x = x; this.y = y; this.z = z; } // ADD 2 Vectors add(v) { let x1 = this.x + v.x; let y1 = this.y + v.y; let z1 = this.z + v.z; return new Vector(x1, y1, z1); } // Subtract 2 vectors sub(v) { let x1 = this.x - v.x; let y1 = this.y - v.y; let z1 = this.z - v.z; return new Vector(x1, y1, z1); } // Dot product of 2 vectors dot(v) { let x1 = this.x * v.x; let y1 = this.y * v.y; let z1 = this.z * v.z; return x1 + y1 + z1; } // Cross product of 2 vectors cross(v) { let x1 = this.y * v.z - this.z * v.y; let y1 = this.z * v.x - this.x * v.z; let z1 = this.x * v.y - this.y * v.x; return new Vector(x1, y1, z1); } // Display Vector toString() { let out = this.x + "i "; if (this.y >= 0) { out += "+ "; } out += this.y + "j "; if (this.z >= 0) { out += "+ "; } out += this.z + "k\n"; return out; } magnitude() { return Math.sqrt(this.x ** 2 + this.y ** 2 + this.z ** 2); }}// calculate shortest dist. from point to linefunction shortDistance(line_point1, line_point2, point) { let AB = line_point2.sub(line_point1); let AC = point.sub(line_point1); let area = AB.cross(AC).magnitude(); let CD = area / AB.magnitude(); return CD;}// Driver programlet line_point1 = new Vector(4, 2, 1);let line_point2 = new Vector(8, 4, 2);let point = new Vector(2, 2, 2);console.log("Shortest Distance is:", shortDistance(line_point1, line_point2, point)); |
Output
Shortest Distance is : 1.63299
Time Complexity: O(log N), for using the inbuilt sqrt() function.
Auxiliary Space: O(1), as constant space is required.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
