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

Detecting the point of collision between a rotating point and a rotating line.

  1. Oct 3, 2008 #1
    I'm trying to formulate an algorithm that will calculate the point where an independently rotating point collides with an independently rotating line.This will only concern instances where the rotating point, which will be called P1 from now on, and the rotating line, which will be called L1 from now on, are rotating in a two-dimensional plane where the axes of rotation for both P1 and L1 are parallel. L1 will also be expressed as two rotating points, P2 and P3, around the same point of rotation.

    Both the systems associated with P1 and L1 will have the following known values:
    w - The angular velocity of each system, expressed in degrees/frame.
    r - The distance to each system's point of rotation, expressed in pixels.
    (cx,cy) - The coordinates of the point of each system that is being rotated around
    (P1.x,P1.y)... - The coordinates of P1,P2, and P3 when the systems are at their final state.
    O° - The angle to the rotating point, P1, from C1, which is the point of rotation in the system that deals with P1. It is also the angle to the point on the rotating line, P2, from C2, which is the point of rotation in the system that deals with L1.
    w2/w1 - The ratio of the angular velocities of each system. It will be assumed that w1 > 0. w2 is the angular velocity of the system that deals with L1, and w1 is the angular velocity of the system that deals with P1.

    The point where P1 collides with L1 is where the angle to P1 from P2 is the same as the angle to P3 from P2. Here's an example to further explain what I mean.

    * cw = clockwise and will be expressed in negative degrees
    * ccw = counter-clockwise and will be expressed in positive degrees

    There are three pictures of two objects rotating. The red circle on the left shows the system that deals with P1, and the green circle on the right shows the system that deals with L1. L1 is the line segment that connects P2 and P3 together. The initial state shows the starting position of each point before they are rotated. The intermediate state shows the position of P1 and L1 after they each have half of their angular velocities added to the angle to each point from the point of rotation of each system (C1 and C2). This is also where P1 intersects L1, as the angle to P1 from P2 is the same as the angle to P3 from P2, which is 0°. The final state is what is shows after the total angular velocity is added to each system. As you can see, P1's orientation is 180° different from its initial state, and P2's and P3's orientations are 90° different from their initial states. Also, the coordinate system in this example mimics the coordinate system found in most computer programs, where the top-left corner is the origin and the value of the y-axis increases as you move downwards.

    The only state the program will be able to detect is the final state, and since all of the factors that dictate where the point of collision occurs are known, it should be possible to find a function to give that point. A way to find that point is to simply know how much, in degrees, that P1 needs to "back up" in order to be in the orientation where it collides with L1. This value will now be known as F°.

    In the above example F° = 90°,as that is the amount needed to "back up" P1 to be in the same position as it is in the intermediate state where the collision happened. To find the corresponding angle for L1, just multiply the ratio of the angular velocities of each system by F°. In the above example, the ratio is -1/2 (w2/w1 = 90/-180 = -1/2), so the corresponding angle would be -45° (w2*F°/w1 = 90*90/-180 = -45°).

    The problem is finding a way to find F°. The means to find F° must include each systems' angular velocities(w1 and w2), position of the points of rotation(C1 and C2), final state orientation (O1° and O2°), radius from P1 and P2 to the points of rotation (r1 and r2). Another value, the offset added to the angle to P2 from C2 to find the angle to P3 from P2, which will be known as K°, must also be known. In the final state in the above example, K° = 180° as you need to add 180° to the angle to P2 from C2 to get the angle to P3 from P2 (O2° = 225°, angle to P3 from P2 = 45°, 225° - 45° = 180°. To check if this is right, O2 + K = angle to P3 from P2, 225° + 180 = 405° - (360°) = 45°, so this is right).
    The position that P1 will be when the collision occurs will be the ordered pair (x1, y1), and the position that P2 will be when the collision occurs will be the ordered pair (x2, y2). The angle between these two points must be the same as the angle to P3 from P2 when the collision occurs, which can be expressed as (O2 + w2*F°/w1) + K°. (O2 + w2*F°/w1) will find what O2 was when the collision occurred, and adding the offset, K°, to that value will get the angle to P3 from P2 when the collision occurred.
    To find the angle between two points, you must subtract the coordinates of the point that will be used as the origin, P2, from the point you want to find the angle to, P1, and then use these values in the inverse of the tangent function. These two values will be known as simply x and y.

    To clarify...
    arctan(-y/x) = (O2 + w2*F°/w1) + K
    y = y1 - y2
    x = x1 - x2
    (y is multiplied by -1 to correct the fact that we are working in a computer-based coordinate system)

    The arctan function is not accurate at all times, and some rules needed to be combined with the result in order to get the correct angle between the two coordinates. In the above example, however, these rules do not need to be applied.

    (x1,y1) and (x2,y2) can be expressed as follows:
    x1 = cos(O1 + F°) * r1 + C1x
    y1 = -sin(O1 + F°) * r1 + C1y

    x2 = cos(O2 + w2*F°/w1) * r2 + C2x
    y2 = -sin(O2 + w2*F°/w1) * r2 + C2y
    (sin is multiplied by -1 to correct the fact that we are working in a computer-based coordinate system)
    (C1x means the x-coordinate of C1, C1y means the y-coordinate of C1, etc..)

    Using the above example, we will use this method to show that P1 and L1 collide when we substitute the variables needed with the values found in the final stage and with the already-known information that F° = 90°.
    Using the information given in the final stage...
    O1 = 270°, O2 = 225°
    w1 = -180°, w2 = 90°
    r1 = 50, r2 = 50
    C1 = (50,50), C2 = (137.5,50)
    angle to P3 from P2 = 45°
    K° = O2 - angle to P3 from P2 = 180°
    F° = 90 (Already known given the example. In other problems this value is not known but needs to be found. The method to find this is unknown, and it is the reason I'm posting all of this in the first place.)

    Using this information to see if it works...
    x1 = cos(O1 + F°) * r1 + C1x = cos(270° + 90) * 50 + 50 = 100
    y1 = -sin(O1 + F°) * r1 + C1y = -sin(270° + 90) * 50 + 50 = 50

    x2 = cos(O2 + w2*F°/w1) * r2 + C2x = cos(225° + 90*90°/-180) * 50 + 137.5 = 87.5
    y1 = -sin(O2 + w2*F°/w1) * r2 + C2y = -sin(225° + 90*90°/-180) * 50 + 50 = 50

    x = x1 - x2 = 100 - 87.5 = 12.5
    y = y1 - y2 = 50 - 50 = 0

    O2 + w2*F°/w1 + K = 225° + 90*90°/-180 + 180° = 360° = 0°

    arctan(-y/x) = arctan(0) = 0°

    arctan(-y/x) = O2 + w2*F°/w1 + K = 0°
    Since the above statement is true, P1 collides with L1 when P1 is "backed up" by 90° and when P2 is "backed up" by -45° (w2*F°/w1 = 90*90°/-180 = -45°).

    The problem is that I don't know how to turn the equation (arctan(-y/x) = O2 + w2*F°/w1 + K = 0°) into a function that will return F°. F° is found on both sides of the equation, and when you factor in the rules that need to be applied to arctan to find the real angle when given any two points, it seems pretty impossible.

    I realize that no one will read this whole thing completely understanding what I'm saying, and I apologize sincerely for this. I've tried very hard to express this problem in the clearest way that I could, but I don't think I'll get an answer anytime soon. If you actually know what I'm talking about, please let me know how you would approach this problem. If you know some genius that can solve any mathematical problem, please let me know this person so that I can contact him/her. If you know of a forum that exists somewhere else on the internet that handles problems like this, it would be very nice to show me the link to such a place. Thank you in advance.
  2. jcsd
  3. Oct 3, 2008 #2
    I have not followed your full reasoning, but I can give you an idea, in the hope it helps.

    Suppose the coordinates of P2 and P3, at some moment of their rotation, are (x2,y2) and (x3,y3). Now, define the function f(x,y) = (y-y2)*(x3-x2) - (x-x2)*(y3-y2). This function is exactly zero for any point (x,y) "aligned" with L1 (that is, if you extend infinitely the segment L1 to produce an infinite line passing through P2 and P3, then f(x,y)=0 whenever the point (x,y) is ON that line). Also, f(x,y) > 0 for all points (x,y) on one side of the line, and < 0 for all points on the other side.

    Now, if the coordinates of P1 are (x1,y1), what you need is to note the sign of f(x1,y1) in the initial state, and begin rotating on small increments until the sign of f(x1,y1) changes. Then rotate back, but with a smaller increment, until the sign changes again. By going back and forth and reducing the rotating step, you can get as close as you wish to the "alignment" state, within some tolerance you determine.

    Once P1 is aligned with L1, it should be an easy matter to determine if P1 is between P2 and P3 (thus colliding with the segment), or outside the segment.
  4. Oct 3, 2008 #3
    Thank you for your speedy reply and the formula you provided. It is possible to perform a method similar to a binary search to check the positions of the points in small increments to see where they align, but such a method would be costly, as it would have to use the processor-intensive trigonometry functions multiple times, and somewhat inaccurate (to a degree). It may be what I finally have to do, however, if there is no precise, mathematical way to judge when and where the collision happened based on the values of the angular velocities, ending positions of the points, positions of the points of rotation, etc.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook