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).

A Desmos plot of the situation described

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!

  • $\begingroup$ So treat the circles as lattice points ? $\endgroup$ Sep 20 '21 at 15:45
  • $\begingroup$ You may, if it gives any useful insight. Just remember that they have radius $R$ $\endgroup$
    – DeadlosZ
    Sep 22 '21 at 8:52
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 22 '21 at 16:17
  • $\begingroup$ @EthanBolker As long the search is efficient, I think this may be enough. Apparently this question is a lot more complicated then I thought... $\endgroup$
    – DeadlosZ
    Sep 22 '21 at 21:45
  • 1
    $\begingroup$ 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 $\endgroup$ 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).

  • $\begingroup$ 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. $\endgroup$
    – DeadlosZ
    Sep 27 '21 at 17:10
  • $\begingroup$ 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. $\endgroup$ 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.


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.