Intersection Point of two lines
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, r1 = a1 + t1d1 and for the second line the parametric equation will be, r2 = a2 + t2d2. We can further simplify the second equation:
=> r2 – a2 = t2d2
Taking Cross Product with d2 vector on both sides.
=> (r2 – a2) X d2 = 0
As the lines intersect at any point, the value of r1 and r2 will be same at that intersection point. So, by substituting the value of r1 in the above equation,
=> (a1 + t1d1 – a2) X d2 = 0
=> t1 = ((a2 – a1) X d2) / (d1 X d2)
Now, we can find the intersection point by putting the value of t1 into r1 = a1 + t1d1
Implementation:
#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;
}
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]);
}
}
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])
// 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