Simple way to find position on square given angle at center

Question

Suppose I have a square with a diameter $2R$ centered at the origin of a 2D plane, and an angle theta from the horizontal axis. I want to find the cartesian co-ordinates of the intersection of a ray at this angle and the border of this square.

I could calculate the intersection of the ray with a line extended from each square and take the minimum of the two, or I could calculate which side I am intersecting based on the angle and calculate the position based on the known value (i.e. $x=R$ for the right wall, $y=R$ for the top wall, etc). But all of these require a number of conditions/checks.

Is there a way to determine the unknown point without a series of if/else checks to determine the wall being intersected?

Answer 1

There is, if you allow rounding and modulo operations to be used, and you number the right, top, left, and bottom edges as 0, 1, 2, and 3, respectively.

If the ray starts at the center of the square, and you know the angle $\varphi$ the ray makes with the positive $x$ axis, and $0 \le \varphi \lt 360°$, the edge $k$ ($0$, $1$, $2$, or $3$) the ray intersects is

$$k = \left\lfloor \frac{\varphi + 45°}{90°} \right\rfloor \mod{4}$$ where the $\lfloor \, \rfloor$ is the floor operation (or round towards zero), and $\mod{4}\,\,$ refers to the nonnegative remainder after dividing by four. In C, with phi in radians, you might use k = (int)round(2*phi/PI + 0.5) & 3;.

Do note that the lower right corner is considered part of the right edge, upper right corner part of the top edge, upper left corner part of the left edge, and lower left corner part of the bottom edge.

For the intersection point, we only need to consider the square in a polar coordinate system. Unfortunately, this function is defined piecewise. Fortunately, we can reuse the "trick" from calculating $k$ to avoid that.

Let $\alpha$ be the angle the ray and the line from origin to the center of the edge the ray intersects, measured counterclockwise: $$\alpha = \varphi - 90° \left\lfloor \frac{\varphi}{90°} \right\rceil$$ where $\lfloor \rceil$ indicates rounding to nearest integer. Note that $-45° \le \alpha \lt +45°$.

Now, we can simply consider the square in polar coordinates. Let $r(\varphi)$ be the distance from the ray origin to the square. It turns out that $$r(\varphi) = r(\alpha) = \frac{R}{\cos\alpha}$$

We can use that to find the coordinates $(x , y)$ to the intersection: $$\left\lbrace \begin{aligned} x(\varphi) &= R \frac{\cos\varphi}{\cos\alpha} \\ y(\varphi) &= R \frac{\sin\varphi}{\cos\alpha} \end{aligned}\right.$$

In practice, floating-point operations like trigonometric functions $\sin$ and $\cos$, and to a lesser degree division and rounding, tend to be slow compared to addition, subtraction, and multiplication.

If we compare the approach shown here to a more generic pseudo-code implementation that uses if-then-else clauses, we'll find that the if-then-else clauses typically allow a much simpler/efficient/faster implementation.