Magnus2552 - 1 year ago 43
C++ Question

# What is wrong with my intersection checking algorithm?

I know there are many sites which explain how to check for an intersection of two lines, but I find it utterly boring to just copy and paste code for such a simple mathematical task. The more it frustrates me that I cannot get my code to work. I know questions with "What is wrong in my code?" are stupid, but I don't know what the hell is wrong with my mathematics / code, also my code is documented nicely (except of admittedly bad variable naming), so I guess there should be someone who is interested in the math behind it:

bool segment::checkforIntersection(QPointF a, QPointF b) { //line 1: a+bx, line 2: c+dx, note that a and c are called offset and bx and dx are called gradients in this code
QPointF bx = b-a;
double firstGradient = bx.y() / bx.x(); //gradient of line 1
//now we have to calculate the offset of line 1: we have b from a+bx. Since QPointF a is on that line, it is:
//a + b * a.x = a.y with a as free variable, which yields a = a.y - b*a.x.
//One could also use the second point b for this calculation.
double firstOffset = a.y() - firstGradient * a.x();
for (int i = 0; i < poscount-3; i++) { //we dont check with the last line, because that could be the same line, as the one that emited intersection checking
QPointF c = pos[i];
QPointF d = pos[i+1];
QPointF dx = d-c;
secondGradient = dx.y() / dx.x(); //same formula as above
secondOffset = c.y() - secondGradient * c.x();
//a+bx=c+dx <=> a-c = (d-b)x <=> (a-c)/(d-b) = x
double x = (firstOffset - secondOffset) / (secondGradient - firstGradient);
//we have to check, if those lines intersect with a x \in [a.x,b.x] and x \in [c.x,d.x]. If this is the case, we have a collision
if (x >= a.x() && x <= b.x() && x >= c.x() && x <= d.x()) {
return true;
}
}
return false;
}


So what this does, it has 4 points a, b, c, d (line 1: a--b, line 2: c--d) (ignore the for loop) which have an absolute x and y value. First it calculates the gradient of the lines by calculating deltay/deltax. Then it calculates the offset by using the fact that point a (or c respectively) are on the lines. This way we transformed the 4 points into mathematical representation of these lines as equation a+bx, whereas a x of 0 means that we are at the first point (a / c) and a x of 1 means that we are on the second point (b/d). Next we calculate the intersection of those two lines (basic algebra). After that we check if the intersection's x value is valid. To my understanding this is all correct. Does anyone see the error?

This was empirically checked to be incorrect. The code does not give any false Positives (says there is an intersection, when there isn't), but it gives false Negatives (says there is no intersection, when there actually is). So when it says there is an Intersection it is correct, however if it says there is no intersection, you cannot always believe my algorithm.

Again, I checked online, but the algorithms are different (with some orientation tricks and something), I just wanted to come up with my own algorithm, I would be so glad if someone could help. :)

Edit: Here is a minimal reproducable not working example, this time without Qt but with C++ only:

#include <iostream>
#include <math.h>

using namespace std;
class Point {
private:
double xval, yval;
public:
// Constructor uses default arguments to allow calling with zero, one,
// or two values.
Point(double x = 0.0, double y = 0.0) {
xval = x;
yval = y;
}

// Extractors.
double x() { return xval; }
double y() { return yval; }

Point sub(Point b)
{
return Point(xval - b.xval, yval - b.yval);
}
};

bool checkforIntersection(Point a, Point b, Point c, Point d) { //line 1: a+bx, line 2: c+dx, note that a and c are called offset and bx and dx are called gradients in this code
Point bx = b.sub(a);
double firstGradient = bx.y() / bx.x(); //gradient of line 1
//now we have to calculate the offset of line 1: we have b from a+bx. Since Point a is on that line, it is:
//a + b * a.x = a.y with a as free variable, which yields a = a.y - b*a.x.
//One could also use the second point b for this calculation.
double firstOffset = a.y() - firstGradient * a.x();
Point dx = d.sub(c);
secondGradient = dx.y() / dx.x(); //same formula as above
secondOffset = c.y() - secondGradient * c.x();
//a+bx=c+dx <=> a-c = (d-b)x <=> (a-c)/(d-b) = x
double x = (firstOffset - secondOffset) / (secondGradient - firstGradient);
//we have to check, if those lines intersect with a x \in [a.x,b.x] and x \in [c.x,d.x]. If this is the case, we have a collision
if (x >= a.x() && x <= b.x() && x >= c.x() && x <= d.x()) {
return true;
}
return false;
}

int main(int argc, char const *argv[]) {
if (checkforIntersection(Point(310.374,835.171),Point(290.434,802.354), Point(333.847,807.232), Point(301.03,827.172)) == true) {
cout << "These lines do intersect so I should be printed out\n";
} else {
cout << "The algorithm does not work, so instead I do get printed out\n";
}
return 0;
}


So as example I took the points ~ (310,835) -- (290,802), and (333,807) -- (301,827). These lines do intersect:

\documentclass[crop,tikz]{standalone}
\begin{document}
\begin{tikzpicture}[x=.1cm,y=.1cm]
\draw (310,835) -- (290,802);
\draw (333,807) -- (301,827);
\end{tikzpicture}
\end{document}


Proof of intersection
However when running the above C++ code, it says that they do not intersect

(you may call me a pedant, but the terminology is important)

If you want to see if the line segments intersect, then rely on the parametric representation of your two segments, solve the system in the two parameters and see if both of the solution for both of the parameters falls into [0,1] range.

Parametric representation for segment [a, b], component-wise

{x, y}(t) = {(1-t)*ax+t*bx, (1-t)*ay+t*by} with t in the [0,1] range

Quick check - at t=0 you get a, at t=1 you get b, the expression is linear in t, so there you have it.

So, your (a,b) (c,d) intersection problem becomes:

// for some t1 and t2, the x coordinate is the same
(1-t1)*ax+t*bx=(1-t2)*cx+t2*dx;
(1-t1)*ay+t*by=(1-t2)*cy+t2*dy; // and so is the y coordinate


Solve the system in t1 and t2. If t1 is in the [0,1] range, then the intersection lies between a and b, the same goes for t2 in respect with c and d.

It is left as an exercise for the reader the study of what effects will have on the system above the following conditions and what checks should be implemented for a robust algorithm:

1. segment degeneracy - coincident ends for one or both segments
2. collinear segments with non-void overlap. Particular case when there's a single point of overlap (necessary, that point will be one of the ends)
3. collinear segments with no overlap
4. parallel segments