Intersection Point of two lines

Practice Problems on Basic Geometry for Competitive Programming:

We can find the intersection point of two lines in 2D using parametric equations. Parametric equations are a way of representing a curve in terms of one or more parameters. For a line in 2D, we can use the following parametric equation:

=> r = a + td

where a is the starting point of the line, t is a real parameter, d is the direction vector for the line and r is a point on the line.

So, for the first line the parametric equation will be, r₁ = a₁ + t₁d₁and for the second line the parametric equation will be, r₂ = a₂ + t₂d_2.We can further simplify the second equation:

=> r₂ – a₂ = t₂d₂

Taking Cross Product with d2 vector on both sides.
=> (r₂ – a₂) X d₂ = 0

As the lines intersect at any point, the value of r₁ and r₂ will be same at that intersection point. So, by substituting the value of r₁ in the above equation,
=> (a₁ + t₁d₁ – a₂) X d₂ = 0
=> t₁ = ((a₂ – a₁) X d₂) / (d₁ X d₂)

Now, we can find the intersection point by putting the value of t₁into r₁ = a₁ + t₁d₁

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;

// Since the product of 2D(x, y) vectors is a vector in z
// direction, we simply return the magnitude of the vector
double getCrossProduct(vector<double> v1, vector<double> v2)
{
    return v1[0] * v2[1] - v1[1] * v2[0];
}

vector<double> getDifference(vector<double> v1,
                            vector<double> v2)
{
    vector<double> diff(2);
    diff[0] = v2[0] - v1[0];
    diff[1] = v2[1] - v1[1];
    return diff;
}

vector<double> getSum(vector<double> v1, vector<double> v2)
{
    vector<double> sum(2);
    sum[0] = v1[0] + v2[0];
    sum[1] = v1[1] + v2[1];
    return sum;
}

int main()
{
    // Points of lines
    vector<double> pointA = { 1, 1 };
    vector<double> pointB = { 4, 4 };
    vector<double> pointC = { 1, 8 };
    vector<double> pointD = { 2, 4 };

    // direction vector d1
    vector<double> d1 = getDifference(pointA, pointB);
    // direction vector d2
    vector<double> d2 = getDifference(pointC, pointD);
    double t1
        = getCrossProduct(getDifference(pointA, pointC), d2)
        / (getCrossProduct(d1, d2) * 1.0);
    d1[0] *= t1;
    d1[1] *= t1;
    // Now, we can find the intersection point by putting
    // the value of t1 into r1 = A + t1d1
    vector<double> intersectionPoint = getSum(pointA, d1);

    cout << intersectionPoint[0] << " "
        << intersectionPoint[1];

    return 0;
}

Java

import java.util.*;

public class Main {
    // Since the product of 2D(x, y) vectors is a vector in z
    // direction, we simply return the magnitude of the vector
    public static double getCrossProduct(double[] v1, double[] v2) {
        return v1[0] * v2[1] - v1[1] * v2[0];
    }

    public static double[] getDifference(double[] v1, double[] v2) {
        double[] diff = new double[2];
        diff[0] = v2[0] - v1[0];
        diff[1] = v2[1] - v1[1];
        return diff;
    }

    public static double[] getSum(double[] v1, double[] v2) {
        double[] sum = new double[2];
        sum[0] = v1[0] + v2[0];
        sum[1] = v1[1] + v2[1];
        return sum;
    }

    public static void main(String[] args) {
        // Points of lines
        double[] pointA = { 1, 1 };
        double[] pointB = { 4, 4 };
        double[] pointC = { 1, 8 };
        double[] pointD = { 2, 4 };

        // direction vector d1
        double[] d1 = getDifference(pointA, pointB);
        // direction vector d2
        double[] d2 = getDifference(pointC, pointD);
        double t1 = getCrossProduct(getDifference(pointA, pointC), d2) / getCrossProduct(d1, d2);
        d1[0] *= t1;
        d1[1] *= t1;
        // Now, we can find the intersection point by putting
        // the value of t1 into r1 = A + t1d1
        double[] intersectionPoint = getSum(pointA, d1);

        System.out.println(intersectionPoint[0] + " " + intersectionPoint[1]);
    }
}

Python3

from typing import List

# Since the product of 2D(x, y) vectors is a vector in z
# direction, we simply return the magnitude of the vector
def getCrossProduct(v1: List[float], v2: List[float]) -> float:
    return v1[0] * v2[1] - v1[1] * v2[0]

def getDifference(v1: List[float], v2: List[float]) -> List[float]:
    diff = [0.0, 0.0]
    diff[0] = v2[0] - v1[0]
    diff[1] = v2[1] - v1[1]
    return diff

def getSum(v1: List[float], v2: List[float]) -> List[float]:
    sum = [0.0, 0.0]
    sum[0] = v1[0] + v2[0]
    sum[1] = v1[1] + v2[1]
    return sum

# Points of lines
pointA = [1, 1]
pointB = [4, 4]
pointC = [1, 8]
pointD = [2, 4]

# direction vector d1
d1 = getDifference(pointA, pointB)
# direction vector d2
d2 = getDifference(pointC, pointD)
t1 = getCrossProduct(getDifference(pointA, pointC), d2) / getCrossProduct(d1, d2)
d1[0] *= t1
d1[1] *= t1
# Now, we can find the intersection point by putting
# the value of t1 into r1 = A + t1d1
intersectionPoint = getSum(pointA, d1)

print(intersectionPoint[0], intersectionPoint[1])

JavaScript

// Function to calculate the cross product of two 2D vectors
function getCrossProduct(v1, v2) {
    return v1[0] * v2[1] - v1[1] * v2[0];
}

// Function to calculate the difference between two 2D vectors
function getDifference(v1, v2) {
    return [v2[0] - v1[0], v2[1] - v1[1]];
}

// Function to calculate the sum of two 2D vectors
function getSum(v1, v2) {
    return [v1[0] + v2[0], v1[1] + v2[1]];
}

// Main function
function main() {
    // Points of lines
    const pointA = [1, 1];
    const pointB = [4, 4];
    const pointC = [1, 8];
    const pointD = [2, 4];

    // Direction vector d1
    const d1 = getDifference(pointA, pointB);
    // Direction vector d2
    const d2 = getDifference(pointC, pointD);

    // Calculate t1
    const t1 = getCrossProduct(getDifference(pointA, pointC), d2) / getCrossProduct(d1, d2);

    // Calculate the scaled direction vector d1
    const scaledD1 = [d1[0] * t1, d1[1] * t1];

    // Calculate the intersection point by adding the scaled direction vector to pointA
    const intersectionPoint = getSum(pointA, scaledD1);

    // Output the intersection point
    console.log(intersectionPoint[0] + " " + intersectionPoint[1]);
}

// Invoke the main function
main();

Output

2.4 2.4

Click here to know about finding the intersection point using equation of lines.

Basic Geometry for Competitive Programming

Ever wondered how to tackle tricky problems in competitive programming? Well, basic geometry is your secret weapon! In this article, we’re diving into the basics Geometric Algorithms. It’s like a power-up for your problem-solving skills, giving you the tools to crack those coding challenges like a pro.

Table of Content

What are Geometric Algorithms?
Why to use Geometric Algorithms?
Vector Addition/Subtraction
Dot Product and Cross Product
Distance from a point to a line
Intersection Point of two lines
Practice Problems on Basic Geometry for Competitive Programming

Intersection Point of two lines

Click here to know about finding the intersection point using equation of lines.

Basic Geometry for Competitive Programming

Similar Reads