Sign in to follow this  

Line intersection algorithm without using equation of a line, how is it possible?

This topic is 4689 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

sorry to bother you, but in my search for algorithms to check for intersections, i found this site, and although after testing them they do work, i cant see how this fits in with the formulas i got in my maths book for lines. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2 where does he get the slope?how does he do away with the need for similtaneous equations? i have tried to work this back to an equation of line formula ( y = mx + c or y- y1 = m(x-x1) ) but i cant get it . can anyone explain it to me?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You have:
Quote:

A1x + B1y = C1
A2x + B2y = C2


and then it's right there:

Quote:

To see where this comes from, consider multiplying the top equation by B2, and the bottom equation by B1. This gives you
A1B2x + B1B2y = B2C1
A2B1x + B1B2y = B1C2
Now, subtract the bottom equation from the top equation to get
A1B2x - A2B1x = B2C1 - B1C2
Finally, divide both sides by A1B2 - A2B1, and you get the equation for x. The equation for y can be derived similarly.


Determinants. Linear algebra.

Share this post


Link to post
Share on other sites
y = mx + c

is the not a good way to represent a line. Perhaps easier to explain to kids but the problem is that it is unable to represent lines parallel to the y axis.

this representation does not have such a limitation:

Ax + By = C

Share this post


Link to post
Share on other sites
Quote:

i have tried to work this back to an equation of line formula ( y = mx + c or y- y1 = m(x-x1) ) but i cant get it . can anyone explain it to me?

thats not the equation of a line. its the equation for a linear function. not all lines can be described that way, take a vertical one for example, hence its a sucky formula to work with.

when defining lines either the explict origin + direction * t, or the implicit form a*x+b*y=c is used. the latter is used to derive the formula you link to.

the explicit form is most usefull for most practical purposes i know of, since it contains the most information. implict has only position and direction, while explict gives position, direction and length/speed/howeveryouwanttointerpretit. hence the intersection of two implict lines only gives you the intersectionpoint, while the intersection of explicit lines also gives you the intersectionpoint as a parameter on the line, which is often needed.

Share this post


Link to post
Share on other sites

This topic is 4689 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this