# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-11-13 22:16
|
A fairly simple and readable solution for finding intersection of two lines that relies on vector arithmetic. Returns a (NaN, NaN)
pair in case lines are parallel
#include<tuple>
#include<cmath>
struct Vector {
double x;
double y;
Vector operator-(const Vector r) const {
return {x - r.x, y - r.y};
}
Vector operator+(const Vector r) const {
return {x + r.x, y + r.y};
}
Vector operator*(double r) const {
return {x*r, y*r};
}
Vector operator/(double r) const {
return {x/r, y/r};
}
double operator*(const Vector r) const {
return x * r.x + y * r.y;
}
};
Vector get_intersection(std::pair<Vector, Vector> l1, std::pair<Vector, Vector> l2) {
Vector d1 = l1.second - l1.first;
Vector d2 = l2.second - l2.first;
Vector n2 = Vector({d2.y, -d2.x}) / std::hypot(d2.y, -d2.x); // Normal of the second line
double h = (l1.first - l2.first) * n2; // height of the first point of l1 on vector l2
double hd = d1 * n2; // height differential of the vector that defines l1
const double threshold = 0.0f; // A threshold where height differential is considered to correspond to parallel lines
if(std::abs(hd) <= threshold) {
return {NAN, NAN};
}
return l1.first + d1 * (h / -hd);
}
int main() {
std::pair<Vector, Vector> l1 = {Vector({1, 2}), Vector({5, 1})};
std::pair<Vector, Vector> l2 = {Vector({3, 7}), Vector({6, 2})};
Vector intersection = get_intersection(l2, l1);
return 0;
}
functions | ||
abs |
en.cppreference.com | cplusplus.com |
hypot |
en.cppreference.com | cplusplus.com |
classes | ||
std::pair |
en.cppreference.com | cplusplus.com |
Implement an algorithm for finding an intersection of two 2D lines, and use it to find the intersection of some arbitrary pair of lines. Solution should be fast and strive for simplicity.