# Is there a way to find the intersection of two rectangles given their current velocity and position in constant time?

Suppose I have two rectangles, let's define them as $$R_1$$ and $$R_2$$, which each contain a length and width. Given the headings $$\theta_1$$ and $$\theta_2$$ respectively, as well as the coordinates $$x_1, y_1, x_2, y_2$$ and constant velocity $$v_1, v_2$$ is there a feasible way to determine the collision points in constant or logarithmic time?

My idea so far is as follows: we can perform ternary search on the first collision time - assuming that the collisions are unimodal, which means that there will be a range $$[a, b]$$ such that the rectangles would be intersecting each other, which I have no proof for. Then, calculate the first time, and thus intersection points as well as locations from there. The running time of this algorithm would be $$\mathcal{O}(\log N)$$.

A setup of the rectangles

• Determine the intersection of the "closest corners" and the time that each rectangle will take for its corner to reach that point; the longer time will be the intersection time, and the positions of the rectangles at that time will be your result. Similarly there will be a related point which is the last moment of intersection from the two corners furthest from each other. May 25 at 3:20
• The rectangles may also meet at unexpected sides, so be ready to have a test for non-intersection for the above approach and try a trailing-side intersection test. May 25 at 3:25
• You might find this article interesting: developer.mozilla.org/en-US/docs/Games/Techniques/… May 25 at 3:30
• Thanks @abiessu . I am almost certain your approach is valid. By any chance, would you be able to provide insight onto applying this algorithm onto a polyline (the rectangle moves on a polyline, and has new heading on each polyline with interpolated values) May 25 at 3:43
• I'm not familiar with how polylines work, so I can't comment just yet on that. If they are sets of line segments joined at endpoints, I would guess that each segment could be treated to the above approach separately, but beyond that I'd have to do some research. May 25 at 4:16

## 1 Answer

Use a coordinate system where the larger rectangle is always $$(\pm 1, \pm 1)$$.

Then you only need to check if any of the four vertices of the smaller rectangle ever intersect with that square in that coordinate system.

• To clarify, to account for the changing movement between the two, should I add the vectors together (with one complement) to compensate? May 25 at 23:43