Shortest distance between a Line and a Point in a 3-D plane

0 0 8 minutes read

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));

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.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!