Seems like a beginner question maybe? So I posted it here.
Im creating a program that draws two lines to keep it simple and I know there is a method in Java2D to determine if 2 lines intersect but its possible to zoom in and out and when zooming out the lines can eventually intersect.
What I want to know is how I can accuratly calculate when I have coordinate for 2 lines, if they will cross or not, what calculations does the method ‘intersectLine()’ use to work this out?
Thanks,
Ken
http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
Basically find the equations for the two lines and find the point at which they’re equal. Then check to see if this point is within the interval of both segments to decide if they intersect or not.
Wow you where quick and straight to the point!
Thanks alot Orangy Tang for the help, as stupid as it sounds I never actually thought about doing it that way lmao.
Ken
in the case you are a lazy guy:
public static V2 lineIntersection(Line2D line1, Line2D line2) {
V2 cp = null;
double a1, b1, c1, a2, b2, c2, denom;
a1 = line1.getY2() - line1.getY1();
b1 = line1.getX1() - line1.getX2();
c1 = line1.getX2() * line1.getY1() - line1.getX1() * line1.getY2();
// a1x + b1y + c1 = 0 line1 eq
a2 = line2.getY2() - line2.getY1();
b2 = line2.getX1() - line2.getX2();
c2 = line2.getX2() * line2.getY1() - line2.getX1() * line2.getY2();
// a2x + b2y + c2 = 0 line2 eq
denom = a1 * b2 - a2 * b1;
if (denom != 0)
cp = new V2((b1 * c2 - b2 * c1) / denom, (a2 * c1 - a1 * c2) / denom);
else {
// lines are parallel
}
return cp;
}
replace V2 with Vec2f or Point or your V2
Im not a lazy guy but thanks alot for the code! lol
Gives me a good idea on how to do it although I would mainly be using the last bit as I already have the coordinates as BigDecimals and I personally wouldnt use Doubles because they arnt reliable enough accuracy wise for the purpose I want the equation.
Your code returns a coordinate right? I already have an equation to work out the intersection point but the problem with it is if the lines dont actually cross then the point it comes out with is completely wrong (infact there shouldnt be one lol), I just need some way of checking if they cross before even worring about a coordinate.
I will review both of your replies later and see if I can come up with something that will suit my needs.
Thanks,
Ken
There are three cases you need to worry about:
The lines are parallel and never cross. This gives a denominator of 0 (mentioned in my link and the above code).
The (infinite) lines cross, but the actual (bounded) line segments do not cross.
The lines cross, and do so within the interval of the line segments.
Once you’ve solved the equation and got Ua and Ub if they’re both in the range of [0, 1] then the actual intersection point lies on the two segments and you should then use them to calculate the actual intersection position.
Ah ok that makes it more clear.
So by using the equation I can eliminate number 1. and 2. by working out an answer between 0 and 1 but not including 0.
thanks alot for the help, I dont want to seem lazy I just havent had time to look at it yet and I’ve never written anything like this before so sometimes I over complicate it or cant get my head around it at first.
Do you know any other good websites for geometry calculations such as offsets, triangulations etc.
Thanks,
Ken
There is also a 4th case:-
You can go to the same site for more geometry formulas.
To be honest that fourth one should be counted as a crossing anyway, basically anytime the lines touch at all they should count.
The reason being the lines represent pipes so really what I actually do is check for clashes vertically and from plan view and if both clash then it need to be flagged up.
Thanks for the help anyway, that contouring Algorithm on that site looks interesting not sure if I could pull that off but its something that would be very useful.
Thanks,
Ken