Welcome!
This is the community forum for my apps Pythonista and Editorial.
For individual support questions, you can also send an email. If you have a very short question or just want to say hello — I'm @olemoritz on Twitter.
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.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> -
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 = (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> -
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/how-can-i-check-if-two-segments-intersect
-
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.
-
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 -
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://omz-software.com/pythonista/forums/discussion/250/breakout-clone#Item_5">here</a>.
-
Cheers. Just been playing it :)