omz:forum

    • Register
    • Login
    • Search
    • Recent
    • Popular

    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)

    Pythonista
    4
    14
    9904
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • Sebastian
      Sebastian last edited by

      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>

      1 Reply Last reply Reply Quote 0
      • yodayoda230
        yodayoda230 last edited by

        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

        1 Reply Last reply Reply Quote 0
        • yodayoda230
          yodayoda230 last edited by

          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>

          1 Reply Last reply Reply Quote 0
          • Gerzer
            Gerzer last edited by

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

            1 Reply Last reply Reply Quote 0
            • yodayoda230
              yodayoda230 last edited by

              Okay Coder123, that's slightly easier! :)

              1 Reply Last reply Reply Quote 0
              • Sebastian
                Sebastian last edited by

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

                1 Reply Last reply Reply Quote 0
                • eliskan175
                  eliskan175 last edited by

                  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

                  1 Reply Last reply Reply Quote 0
                  • yodayoda230
                    yodayoda230 last edited by

                    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.

                    1 Reply Last reply Reply Quote 0
                    • Sebastian
                      Sebastian last edited by

                      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

                      1 Reply Last reply Reply Quote 0
                      • eliskan175
                        eliskan175 last edited by

                        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.

                        1 Reply Last reply Reply Quote 0
                        • Sebastian
                          Sebastian last edited by

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

                          Thanks for the help everyone :)

                          1 Reply Last reply Reply Quote 0
                          • yodayoda230
                            yodayoda230 last edited by

                            Can't wait for the game! :)

                            1 Reply Last reply Reply Quote 0
                            • Sebastian
                              Sebastian last edited by

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

                              1 Reply Last reply Reply Quote 0
                              • yodayoda230
                                yodayoda230 last edited by

                                Cheers. Just been playing it :)

                                1 Reply Last reply Reply Quote 0
                                • First post
                                  Last post
                                Powered by NodeBB Forums | Contributors