I was trying to implement the vector based segment intersection algorithm described here(the most up-voted answer) in Java but as it usually goes with implementing algorithms you don't fully understand, I keep failing. I would very much appreciate if someone could proofread my code and tell me what I'm doing wrong.
boolean intersect(PVector p, PVector r, PVector q, PVector s){
// r x s
double rxs = r.x*s.y + r.y*s.x;
//(q-p) x r
double qpxr = (q.x-p.x)*r.y + (q.y-p.y)*r.x;
PVector qp = q.sub(p).copy(); //q - p
//case one lines parallel might intersect:
if(rxs==0 && qpxr==0){
println("case one: collinear might intersect");
double t0 = qp.dot(r);
double t1 = qp.dot(r)/r.dot(r)+(s.dot(r)/r.dot(r));
return max((float)t0 , 0.f) <= min((float)t1, 1.f);//if ranges intersect the segments intersect
}else if(rxs==0 && qpxr!=0){
println("case two: parallel no intersect");
return false;
}else if(rxs!=0){
println("case three");
double u = qpxr/rxs;
double t = (qp.x*r.y + qp.y*r.x)/rxs;
if((u>=0 && u<=1) && (t<=1 && t>=0)){
PVector intersect = p.copy();
intersect.add(r.copy().mult((float)t));
point(intersect.x, intersect.y);
return true;
}else{
println("no intersect");
print(u);
print(" ");
println(t);
}
}else{
println("case four no intersect");
return false;
}
return false;
}
Also I tried working some answers by hand and still seemed to fail, so now I'm sort of lost. For example:
p=(0;0), r=(10;10)
q=(10;0), s=(-10;10)
then the r x s = 10*10 + (-10*10) = 0 which would pass up to the second case where parallelity is assumed, even though the segments are not.
P.S. Is there a way to make this code more readable?
