2

There are two moving rectangles A and B in a 2D space.

  • Initially the centers of the rectangles are (x_A, y_A) and (x_B, y_B).
  • The widths and lengths are w_A, h_A, w_B, h_B.
  • The velocities are (v_Ax, v_Ay), (v_Bx, v_By).
  • The angles between the longer edges and the velocities are θ_A, θ_B. In other words, θ is the angle that the rectangle needs to rotate counterclockwise so that the longer edges are parallel to the velocity. (see the picture below).

The questions are:

  1. check if the two rectangles would collide while moving;

  2. if there is no collision, what is the minimum distance (between any two points of the rectangles).

enter image description here

Similar questions are: How to check intersection between 2 rotated rectangles? and Collision detection between two rectangles in java However, they consider only static rectangles.

Thanks!

Community
  • 1
  • 1
user8020774
  • 21
  • 2
  • Please tell us what have you tried. This is important in process of learning as well as to ask a question on stackoverflow. You could also have done some research before right away posting the question. A quick search gave me enough information to solve this question. http://stackoverflow.com/questions/10962379/how-to-check-intersection-between-2-rotated-rectangles Other link: http://stackoverflow.com/questions/31022269/collision-detection-between-two-rectangles-in-java – Shridhar R Kulkarni May 16 '17 at 16:52
  • 2
    One observation: The minimum distance between the rectangles will be the distance between two vertices. – Jared Goguen May 16 '17 at 16:53
  • 1
    @JaredGoguen I don't think that is always true. In the initial configuration the minimum distance might be between a vertex of one rectangle and an non-vertex point on the edge of the other. If the rectangles are moving away from each other, the minimal distance ever achieved will be in the initial configuration, which isn't a vertex-vertex distance. – John Coleman May 16 '17 at 16:59
  • @JohnColeman True, if time is constrained to be positive. If negative time is allowed, then a vertex-vertex distance should appear. But since your scenario should be easily identifiable from the initial conditions, it might be possible to only look at the vertex-vertex distances. – Jared Goguen May 16 '17 at 17:03
  • @JaredGoguen I think that you are correct (although *proving* that you are correct might be somewhat tricky). That certainly simplifies matters. Good observation. – John Coleman May 16 '17 at 17:10
  • @Shridhar R. Kulkarni, thanks. Yes, I've done some research and looked at those posts, but they only deal with static rectangles. – user8020774 May 16 '17 at 17:36
  • @JaredGoguen thanks. I also thought about this, but it seems tricky to prove that you are right as John Coleman mentioned. Is it possible that the minimum distance is between a vertex and an edge and it does not happen in the initial step? The time is positive. – user8020774 May 16 '17 at 17:40
  • 1
    @JohnColeman Consider the rectangle with the vertex to be moving and the rectangle with the edge to be stationary (by changing your reference frame). Then, if the minimum distance occurs between the vertex and the edge, then the vertex must be moving parallel to the edge (or the distance would either be smaller at a previous time or a future time). This means that both vertices that are adjacent to the edge are also at the minimum distance. This is similar to the logic used in the simplex method. – Jared Goguen May 16 '17 at 17:43
  • @user8020774 See the above explanation. The caveat is that the minimum will either occur between two vertices, or at t=0. – Jared Goguen May 16 '17 at 17:49
  • @JaredGoguen Thanks for the explanation! If the two rectangles collide, however, the minimum distance, which is 0, could be between a vertex and an edge, e.g. a corner hits an edge, right? It seems that one has to compute minimum distance between a moving point and a static edge to detect collisions. – user8020774 May 16 '17 at 18:23
  • @user8020774 Yes, vertices can collide with edges, but it doesn't make sense to bother calculating the minimum distance when the rectangles collide (this needs to be determined separately anyway). The collision detection can be done by looking at the moving points and static edges (as explained in the answer below). – Jared Goguen May 16 '17 at 18:26

1 Answers1

3

Simplify the problem using Galileo principle. Work in virtual moving coordinate system connected with the first rectangle.

In that system the first rectangle center is (0, 0), its first corner coordinates are (w/2*Cos(θ_A)-h/2*Sin(θ_A), w/2*Sin(θ_A)+h/2*Cos(θ_A)) and so on.

The second rectangle initial center is (X_B-X_A, Y_B-Y_A) and has velocity (v_Bx -v_Ax, v_By-v_Ay). Corner coordinates might be calculated in the same way.

To check for collision, make equations (Ax+By+C=0) for edges of the first rectangle and find whether corners of the second rectangle ever lie on these segments (point lie on the rectangle edge if its coordinates, being substituted in that edge equation, give zero sign, and give different signs for neighbor edges equations)

To find minimal distance, you can write expression for squared distances between corners depending on time and find minimum analytically (through zero derivative)

MBo
  • 77,366
  • 5
  • 53
  • 86