Algorithm for intersecting lines

sohel · Post by **sohel** » Sun Mar 30, 2003 11:57 am

How to determine whether two lines intersect, given the end points of the two lines?

Shahab · Post by **Shahab** » Sun Mar 30, 2003 2:44 pm

at first, u need an algorithm to determine whether a point is over a line or under it( u can do it using the line equation)

i mean that if u have the line aX+bY+c=0 and also u have the point (x0,y0), if u replace the point in the equation the result of next expression "sign(a*x0+b*y0+c)" shows wheter a point is on the line, over the line or under it. let us know this fuxtion as f(x0,y0). i.e. f(x0,y0)=sign(a*x0+b*y0+c)

so a limited line has intersect with an unlimited line if the two endpoints are not in the same region. it means that if we know that f(x1,y1)*f(x2,y2)<=0 , we also know that the limited line has intersect with the unlimited one.

and when u go to two limited lines, u must do the above procedure 2 times, the first time u must consider the first as an unlimited line and the second line as a limited line, and in the second time, u must do it vice versa, if the the 2 experiments say that they have crossing, u can be sure that they have an intersect, but if it was not like it, u can be sure that they haven't an intersect

Moni · Post by **Moni** » Sun Mar 30, 2003 8:35 pm

Yes! At my computational geometry classes my teacher gave me this topic to solve. That time first I took the help from:

http://mathworld.wolfram.com/Line-LineIntersection.html

And then found a very good help:

http://cm.bell-labs.com/who/clarkson/cis677/lecture/3/

Now I think you will also find it very useful.

Good Luck!

Partha · Post by **Partha** » Mon Mar 31, 2003 8:17 pm

Book name: "Algorithm in C++"
Writer : Robert Sedgewick

See page no. 349. I think this is one of the most efficient algorithm about Line Segment Intersection.

Best of luck....