Archived

This topic is now archived and is closed to further replies.

tj963

2D Intersecting Lines

Recommended Posts

Hi, How do I find the point of intersection of two lines in the form Ax+By=C. I know how the basic method works (both subtraction and substitution) but in either case there are numerous possibilities for divide by 0 errors (horizontal and vertical lines). Is there any way to do this without having so many checks for 0 divisors? THanks, tj963

Share this post


Link to post
Share on other sites
I calculated this method a week ago. I could have made mistakes, but it seems to work. It assumes that you have for two lines: xinitial, yinitial, xdelta, and the ydelta. It returns the "time" of intersection:

x2i(x1v - x2v) + x1i(x2v - x1v) - y2i(y1v - y2v) - y1i(y1v + y2v)
t = - -----------------------------------------------------------------
(x1v - x2v)^2 + (y1v - y2v)^2

Hopefully the comes out correctly. If the denominator is zero the lines are parallel.

Share this post


Link to post
Share on other sites
Hi !

Just make a special case to check if the two lines are parallel. I highly recommend you to treat lines with linear algebra, it becomes much easier when it comes to planes, R^n subspaces, and so on.

If the two director vectors (a director vector for a line is simply a vector from a point to another point on that same line, that is a vector that tells the direction) are colinear (that is, u = kv, where u and v are the vectors and k a scalar), then your lines are not parallel.

This works just fine with lines in R^2 since any non-parallel lines in R^2 always intersect. If you want to intersect two lines in R^3 (that is, in 3D) then you''ll also have to check the special case in wich the two lines simply don''t intersect and are not parallel. But since you wrote ax + by = c, I won''t explain it.

Hope this helps.


Share this post


Link to post
Share on other sites
Well, if you make that a 3 x 2 matrix then you can make three 2 x 2 matrices by removing one column. If you call those m# where the # is replaced by the number of the column removed then x=-|m0|/||m2| and y=|m1|/|m2| where |a| is the determinant of a. It works similarly for 3D with x=|m0|/|m3|, y=-|m1|/|m3| and z=|m2|/|m3|. You only have to check for one zero either way.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:

If the two director vectors (a director vector for a line is simply a vector from a point to another point on that same line, that is a vector that tells the direction) are colinear (that is, u = kv, where u and v are the vectors and k a scalar), then your lines are not parallel.



Besides this there''s quite simple way of determining if the lines are parallel:
If you have 2 lines, which are given by the following equations:
y=k*x+b and y=K*x+B (which can be derived from initial ones "Ax+By=C", then these lines are parralel if k=K, else if k*K=-1 they are perpendicular, and so on...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
...so first of all you check if in first equation (ax+by=c) b==0, and also in the second (Ax+By=C) B==0 - that means lines are parralel! if only one of B or b is equaled zero, then lines are not parallel, and if neither b nor B is zero, you consider k and K! That is it!

Share this post


Link to post
Share on other sites
If a/b = A/B then the lines are parallel. If you multiply both sides by b*B you get a*B = A*b. Then if you subtract A*b from both sides you get a*B-A*b=0 and a*B-A*b is the determinant. So if the determinant is zero the lines are parallel. Ignore what I said about 3D since that would be planes, not lines. You can find the intersection of two lines in 3D in a similar manner, but you have to create three planes from the two lines.

Share this post


Link to post
Share on other sites