Algorithm for intersecting lines
Posted: Sun Mar 30, 2003 11:57 am
How to determine whether two lines intersect, given the end points of the two lines?
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
