1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – abiessu
    May 25 at 3:20
  • $\begingroup$ 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. $\endgroup$
    – abiessu
    May 25 at 3:25
  • $\begingroup$ You might find this article interesting: developer.mozilla.org/en-US/docs/Games/Techniques/… $\endgroup$
    – abiessu
    May 25 at 3:30
  • $\begingroup$ 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) $\endgroup$
    – Neo Wang
    May 25 at 3:43
  • $\begingroup$ 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. $\endgroup$
    – abiessu
    May 25 at 4:16
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ To clarify, to account for the changing movement between the two, should I add the vectors together (with one complement) to compensate? $\endgroup$
    – Neo Wang
    May 25 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.