Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need help testing vector separation.

  1. Jun 24, 2010 #1
    I'm writing code to check if polygons intersect, but I've ran into a problem.

    I have two "vectors." Each has an origin and x and y components. They are facing towards each other. I need to write code that determines if there's a perpendicular axis that separates them. Here's a picture of what I mean:


    I'm out of ideas. Any help would be greatly appreciated.
  2. jcsd
  3. Jun 24, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    Are the vectors perpendicular? Your question suggests that they are but your coordinates do not make that clear. (In particular, if the labels and my math are correct, they are perpendicular iff y=a.)
  4. Jun 24, 2010 #3
    Hint: If you constructed an infinite line that was perpendicular to the first vector and went through (x+a,y+a) of your first vector and then you ignore your first vector... now can you think of something useful to do to make progress towards your solution? See if you can figure it out from that hint before someone gives the answer away.
  5. Jun 24, 2010 #4
    My diagram was ambiguous on the point labels, here's what I meant:


    I also drew the line I think Bill Simpson was referring to. My guess is that I just need to check these lines for intersection. If so, I have further questions:

    a) http://en.wikipedia.org/wiki/Line_segment_intersection" [Broken] is a bit out of my scope, and I'm not sure how this would work in code. In particular, I can't tell the computer to use substitution. Is there an equation that works given the endpoints?

    b) The line can't be infinite length, but since I'm testing collision, it would work fine with an arbitrary value larger than the polygon.
    Last edited by a moderator: May 4, 2017
  6. Jun 24, 2010 #5
    As Bill Simpson told you, you construct the line that is perpendicular to the first vector and that goes through (x+a,y+b).
    After that, you can forget your first vector and concentrate on to calculate the distance between this line and the origin of your second vector.
    If this distance is lower than the length of the second vector, then it is possible to construct a separating axis (in fact, infinite of them).
    If the distance is greater or equal than the length of the second vector, then it is not possible to construct a separating axis.
    I hope this can help you.
  7. Jun 24, 2010 #6
    Following your diagram, you must calculate the distance between the green line (L) and the point (x2,y2).
    The green line is a separating axis iff

    distance [L,(x2,y2)] < sqrt[(x2-a2)^2+(y2-b2)^2]
  8. Jun 24, 2010 #7
    Testing for distance and comparing to the length of the second vector makes sense. Turns out there's already a method that takes care of calculating the distance, so I shouldn't have any problems.

    Thanks for the help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook