Intersection Point of Lines¶
You are given two lines, described via the equations
Solution¶
If two lines are not parallel, they intersect. To find their intersection point, we need to solve the following system of linear equations:
Using Cramer's rule, we can immediately write down the solution for the system, which will give us the required intersection point of the lines:
If the denominator equals
then either the system has no solutions (the lines are parallel and distinct) or there are infinitely many solutions (the lines overlap).
If we need to distinguish these two cases, we have to check if coefficients
Notice, a different approach for computing the intersection point is explained in the article Basic Geometry.
Implementation¶
struct pt {
double x, y;
};
struct line {
double a, b, c;
};
const double EPS = 1e-9;
double det(double a, double b, double c, double d) {
return a*d - b*c;
}
bool intersect(line m, line n, pt & res) {
double zn = det(m.a, m.b, n.a, n.b);
if (abs(zn) < EPS)
return false;
res.x = -det(m.c, m.b, n.c, n.b) / zn;
res.y = -det(m.a, m.c, n.a, n.c) / zn;
return true;
}
bool parallel(line m, line n) {
return abs(det(m.a, m.b, n.a, n.b)) < EPS;
}
bool equivalent(line m, line n) {
return abs(det(m.a, m.b, n.a, n.b)) < EPS
&& abs(det(m.a, m.c, n.a, n.c)) < EPS
&& abs(det(m.b, m.c, n.b, n.c)) < EPS;
}