I solved it. Not pretty, and not NEARLY as fast as I'd like to have done, but it works I guess.
//Tests to see if two lines intersect
//Returns a b2dPoint with the location of the point if they do
//Can handle both vertical and horizontal lines, but it uses a rough approximation for infinity
//Should be sufficient for the small viewing area i'm using
public b2dPoint lineIntersection(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3) {
//Initialize some variables
float m0;
float m1;
if ((x1-x0) != 0) {
m0 = (y1-y0)/(x1-x0);
}
else {
m0 = 1000000000;//One billion may not be infinity, but it's close enough
}
if ((x3-x2) != 0) {
m1 = (y3-y2)/(x3-x2);
}
else {
m1 = 1000000000;//One billion may not be infinity, but it's close enough
}
//If the slopes are not equal, then the lines will intersect somewhere. Find that point.
if (m0 != m1) {
float xIntersection;
float yIntersection;
//Use substitution to try and find the intersection.
yIntersection = ((y0*m1 - m1*m0*x0 - m0*y2 + m0*m1*x2)/(m1-m0));
if (m1 != 0) {
xIntersection = ((yIntersection - y2 + m1*x2)/m1);
}
else {
xIntersection = ((yIntersection - y0 + m0*x0)/m0);
}
//It's possible, because of my not-so-perfect approximation to infinity, that some
//xIntersections may be off a tiny, TINY bit, but they'll still mess up the program.
//Round them off ever so slightly, if they need it.
if (m1 == 1000000000) {
xIntersection = Math.round(xIntersection);
}
//Screw it, round them both off. Not like it matters in this program.
xIntersection = Math.round(xIntersection);
yIntersection = Math.round(yIntersection);
//Round off all the other variables too for the next step
//We're already done using them for the important calculations
x0 = Math.round(x0);
x1 = Math.round(x1);
x2 = Math.round(x2);
x3 = Math.round(x3);
y0 = Math.round(y0);
y1 = Math.round(y1);
y2 = Math.round(y2);
y3 = Math.round(y3);
//If the intersection lies on BOTH lines, return it
if ((((x0 <= xIntersection && xIntersection <= x1) || (x1 <= xIntersection && xIntersection <= x0)) && ((x2 <= xIntersection && xIntersection <= x3) || (x3 <= xIntersection && xIntersection <= x2))) && (((y0 <= yIntersection && yIntersection <= y1) || (y1 <= yIntersection && yIntersection <= y0)) && ((y2 <= yIntersection && yIntersection <= y3) || (y3 <= yIntersection && yIntersection <= y2)))) {
return new b2dPoint(xIntersection,yIntersection);
}
//Otherwise, return the endpoints of the first line
else {
return new b2dPoint(x1,y1);
//return new b2dPoint(xIntersection,yIntersection);
}
}
//If they are equal, return the endpoint of the first line
else {
return new b2dPoint(x1,y1);
}
}
I cleaned it up a tad also. Perhaps later when I have more free time, I'll go back and get it to work the matrix way, but for now it works and I'd rather not fix waht isn't broken at the moment. |
