Find collision between laser and grid of circular obstacles

Assume you have a regular grid of circular obstacles, defined by the equation:

$$\left[\textrm{mod}\left(x-x_{0}+\frac{d_{x}}{2},d_{x}\right)-\frac{d_{x}}{2}\right]^{2}+\left[\textrm{mod}\left(y-y_{0}+\frac{d_{y}}{2},d_{y}\right)-\frac{d_{y}}{2}\right]^{2}\le R^{2}\\R\leq\frac{1}{2}\min\left\{ d_{x},d_{y}\right\}$$

Where $$d_{x,y}$$ are the distances between the circles in each axis, $$\left(x_0,y_0\right)$$ is the center of a specific circle, and $$R$$ is the radues of the circles.
Assume also that in such a grid, we shoot a laser ray from location $$\mathbf{r_0}$$ with direction $$\theta$$ (I made a simple Desmos plot of the situation here). In this setup, is there a closed-form way to find the location of the first hit of the ray with the obstacles?

I searched and found many answers to questions similar to this one, but couldn't find an exact match, nor could I convert their answer to fit my question. If you successfully find an existing answer, this will suffice too.

Thanks a lot!

• So treat the circles as lattice points ? Sep 20 '21 at 15:45
• You may, if it gives any useful insight. Just remember that they have radius $R$ Sep 22 '21 at 8:52
• I think a closed form expression is very unlikely. Will pseudocode for a search be useful? The continued fraction expansion of the slope might help, since it should tell you when the ray comes close to a lattice point. Sep 22 '21 at 16:17
• @EthanBolker As long the search is efficient, I think this may be enough. Apparently this question is a lot more complicated then I thought... Sep 22 '21 at 21:45
• I think it could be useful to imagine the problem as a laser in a room of mirrors with quarter circles on it's corners. All we need to do then is find how many times it bounces off the walls before it hits a circle Sep 22 '21 at 21:59

Another view at the problem is the following. For simplicity assume $$\mathbf{r}_0 = (0,0)$$ and $$d_x=d_y=1$$, $$x_0=y_0=0$$ (The ray actually starts in a circle, however, we will disregard this hit later). This is only for reasons of presentation and I believe that the idea generalizes to the general setting that you presented.

Let $$r_x,r_y$$ be the unit-length vector, which is perpendicular to your ray. Now, projecting the circles onto this vector, will give line segments on that vector. If such a line segment includes the origin, the ray will hit a circle. The circles have centers $$t_x,t_y \in \mathbb{N}$$, whose projection onto the line is $$t_xr_x + t_yr_y$$. The condition for a ray to hit a circle with center $$r_x,r_y$$ eventually is thus $$(t_xr_x+t_yr_y)^2 \leq R^2.$$ Since you want to find the first hit of the ray with a circle, the problem that you are looking to solve is $$\min_{t_x,t_y \in \mathbb{N}} t_x^2+t_y^2~\text{ s.t. } (t_xr_x+t_yr_y)^2 \leq R^2.$$ This is a non-linear integer optimization problem, which you could try and solve with standard solvers. You might want to take care that you only consider those $$t_x,t_y$$ that are actually in the correct direction (the projection also gives you solutions which are behind your ray).

• This is a really nice way to look at the problem! I don't know if optimization is the solution I was looking for (I think it would be easier and faster to just simulate the movement of the laser and find the first hit point), but +50 points for style. Sep 27 '21 at 17:10
• I'm glad you appreciate it - I'll come forward, if I have an idea how to solve this problem efficiently! It's a nice problem by the way. Sep 27 '21 at 20:06

You can always rescale the grid such that the midpoints of the circles have integer coordinates. We then need to solve for $$t$$ in

$$\big| \vec{r} + \vec{v}t - [\vec{r} + \vec{v}t] \big| = R$$

$$(r_x + v_x t - [r_x + v_x t])^2 + (r_y + v_y t - [r_y + v_y t])^2 = R^2$$

where I used square brackets to indicate rounding to the nearest integer values. There is no closed formula for this but you can easily write a program that computes the distances and finds the first intersection.