Line segments intersection? (SOLVED)

Sebastian

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
pass

class 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.x-p1.x)(p3.y-p2.y)-(p2.y-p1.y)(p3.x-p2.x)
ans2 = (p2.x-p1.x)(p4.y-p2.y)-(p2.y-p1.y)(p4.x-p2.x)
ans3 = (p4.x-p3.x)(p1.y-p4.y)-(p4.y-p3.y)(p1.x-p4.x)
ans4 = (p4.x-p3.x)(p2.y-p4.y)-(p4.y-p3.y)(p2.x-p4.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>

yodayoda230

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

yodayoda230

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 + c2

both 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 = (c2-c1) / (g1-g2)

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>

Gerzer

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

yodayoda230

Okay Coder123, that's slightly easier! :)

Sebastian

@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.

eliskan175

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/how-can-i-check-if-two-segments-intersect

yodayoda230

The (pseudo)code snippet there:
def ccw(A,B,C):
return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.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.

Sebastian

I think I got it working :) I used "Beta's" answer on <a href="http://stackoverflow.com/questions/7069420/check-if-two-line-segments-are-colliding-only-check-if-they-are-intersecting-n">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.x-p1.x)(p3.y-p2.y)-(p2.y-p1.y)(p3.x-p2.x)
ans2 = (p2.x-p1.x)(p4.y-p2.y)-(p2.y-p1.y)(p4.x-p2.x)
ans3 = (p4.x-p3.x)(p1.y-p4.y)-(p4.y-p3.y)(p1.x-p4.x)
ans4 = (p4.x-p3.x)(p2.y-p4.y)-(p4.y-p3.y)(p2.x-p4.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

eliskan175

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.

Sebastian

I agree, @yoodayoda's solution was pretty good, but in my case the other solution was more precise.

Thanks for the help everyone :)

yodayoda230

Can't wait for the game! :)

Sebastian

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

yodayoda230

Cheers. Just been playing it :)