Shortest distance between a Line and a Point in a 3-D plane
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 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; } |
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 math class 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 line def 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 program if __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 line function 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 program let 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)); |
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.