Line segments intersection? (SOLVED)

How do you know if two line segments intersect eachother?
If we use this as an example:
<PRE>
from scene import *def lines_intersect(line1, line2):
# I want this function to return True if line1 intersects with line2
passclass Test (Scene):
def setup(self):
self.line1 = [400, 600, 500, 600]
self.line2 = [400, 500, 460, 700]def draw(self): background(0,0,0) stroke_weight(5) stroke(1,0,0) line(*self.line1) line(*self.line2) if lines_intersect(self.line1, self.line2): print "Yay!"
run(Test())
</PRE>Update:
This seems to work
<PRE>def line_intersection(line1, line2):
p1 = Point(line1[0], line1[1])
p2 = Point(line1[2], line1[3])
p3 = Point(line2[0], line2[1])
p4 = Point(line2[2], line2[3])
ans1 = (p2.xp1.x)(p3.yp2.y)(p2.yp1.y)(p3.xp2.x)
ans2 = (p2.xp1.x)(p4.yp2.y)(p2.yp1.y)(p4.xp2.x)
ans3 = (p4.xp3.x)(p1.yp4.y)(p4.yp3.y)(p1.xp4.x)
ans4 = (p4.xp3.x)(p2.yp4.y)(p4.yp3.y)(p2.xp4.x)
return ((ans1 > 0 and ans2 < 0) or (ans1 < 0 and ans2 > 0) and
(ans3 > 0 and ans4) < 0 or (ans3 < 0 and ans4 > 0))</PRE>

I just sketched this out using linear equations and it worked, and it seems like others on the web do the same  find the point where both linear equations equal each other ( or if they don't, then your lines don't intersect)
Nice example here :
http://keisan.casio.com/has10/SpecExec.cgi?id=system/2006/1223519249
But wonder if something more elegant using the "in" function for rectangles might work...hmmm

This sorta works...
<pre>
#line1...
xd= line1[2]line1[0]
yd= line1[3]line1[1]
g1=yd/xd
c1=line1[1](g1*line1[0])
#formula is y= g1 * x + c1#line2...
xd2= line2[2]line2[0]
yd2= line2[3]line2[1]
g2=yd2/xd2
c2 = line2[1]  (g2 * line2[0])
#formula is y= g2 * x + c2both formulas will be equal at the intersection,
i.e. one minus the other equals zero
(g1 * x) + c1  (g2 * x)  c2 = 0
#solve for x...
xinter = (c2c1) / (g1g2)but is xinter somewhere in the correct range?
eg the range of one of the lines x bounds
note: needs work as needs to limit to overlapping x range
if xinter in range(line1[0],line1[2]):
return True
else:
return False
</pre>

If you draw the lines as rectangles, you can use the rect1.intersects(rect2).

Okay Coder123, that's slightly easier! :)

@Coder123 I used to do that, but this is actually for a breakout game where the line segments are each sides of the block and the line that will be intersecting is a line between the ball's current position and it's previous position to check which sides of the block is hit. As I said, I used rectangles before to check if the bounding box of the ball was intersecting one of the rectangles on each sides, but there were a lot of bugs and lagging.

This is an interesting read.. The guys at Stackoverflow always have good ideas for python, and several ways to solve this problem:
http://stackoverflow.com/questions/3838329/howcanicheckiftwosegmentsintersect

The (pseudo)code snippet there:
def ccw(A,B,C):
return (C.yA.y) * (B.xA.x) > (B.yA.y) * (C.xA.x)Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)Looks pretty interesting(and pretty concise!) I will try that.

I think I got it working :) I used "Beta's" answer on <a href="http://stackoverflow.com/questions/7069420/checkiftwolinesegmentsarecollidingonlycheckiftheyareintersectingn">this site</a>
Here's what I got:
<PRE>def line_intersection(line1, line2):
p1 = Point(line1[0], line1[1])
p2 = Point(line1[2], line1[3])
p3 = Point(line2[0], line2[1])
p4 = Point(line2[2], line2[3])
ans1 = (p2.xp1.x)(p3.yp2.y)(p2.yp1.y)(p3.xp2.x)
ans2 = (p2.xp1.x)(p4.yp2.y)(p2.yp1.y)(p4.xp2.x)
ans3 = (p4.xp3.x)(p1.yp4.y)(p4.yp3.y)(p1.xp4.x)
ans4 = (p4.xp3.x)(p2.yp4.y)(p4.yp3.y)(p2.xp4.x)
return ((ans1 > 0 and ans2 < 0) or (ans1 < 0 and ans2 > 0) and
(ans3 > 0 and ans4) < 0 or (ans3 < 0 and ans4 > 0))</PRE>
Edit:
Shortened the solution

That's the awesome thing about Python. It's a very well understood language and a thousand programmers have solved every problem us new programmers usually have. Of all the languages, I think Python is one of the strongest communities. Stackoverflow and Devshed are both great forums that I often find myself wandering through when I have a problem.
Glad to see you solved the problem :) But I will admit I am intrigued by yodayoda's solution. It's very short. And it's interesting to see the boolean return value set up like that, it's something I have never done.

I agree, @yoodayoda's solution was pretty good, but in my case the other solution was more precise.
Thanks for the help everyone :)

Can't wait for the game! :)

I found that my previous collision handling was better than using line intersection. I already uploaded the game <a href="http://omzsoftware.com/pythonista/forums/discussion/250/breakoutclone#Item_5">here</a>.

Cheers. Just been playing it :)