An algorithm for finding the intersection point between a center of vision and a surrounding rectangle

Question

In plane $\mathbb{R}^2$, a rectangle $R$ with center $P_2(x_2,y_2)$ and vertices $(x_2 \pm w, y_2 \pm h)$ (sides parallel to axes) is given. We consider the transformation which, to a given point $P_1(x_1,y_1)$ outside the rectangle associates the intersection point $P_3$ of $P_2P_1$ with the sides of the rectangle, as shown on the figure. This kind of problem occurs in computer vision for mapping a scene onto the border of a "vision box".

Is it possible to build an "elegant" algorithm for this transformation $P_1 \rightarrow P_3$, that avoids as possible the consideration of 4 separate cases ?

Answer 1

Translate both points so that the center moves to the origin. Then the edges of the rectangle have equations $$2|X|=w,\\2|Y|=h,$$

and the line from the origin to the given point $(x,y)$ can be expressed as

$$X=tx,Y=ty.$$

Solve for $t$ and keep the smallest value among

$$t=\left|\frac{w}{2x}\right|,t=\left|\frac{h}{2y}\right|.$$

I leave it to you to adjust for the signs. (And don't forget to "untranslate".)

Note that you will have one of $|X|=\dfrac w2$ or $|Y|=\dfrac h2$.

Answer 2

Edit: I am going to make a complete exposition of what I have previously sketched. Consider figure 1 representing a certain rectangle centered in $P_2(X_2,Y_2)=(9,1)$ with half-width $W=4$ and half-height $H=2$.

The idea is to transform such a rectangle into a square by a certain affine transformation $L$, sending points $P_k$ onto points $P'_k$, then solve the problem in this particular case, i.e., obtain $P'_3$, then use the inverse affine transform $L^{-1}$ to obtain $P_3$.

Why is the solution of the problem simple in the square $(0,1)$, $(1,0)$, $(-1,0)$ and $(0,-1)$? Because all sides have a common expression: $|x|+|y|=1$. It is very easy to prove that if the coordinates of $P'_1$ are $(x_1,y_1)$, then the coordinates of the intersection point are $P'_3(ax_1,ay_1)$ with $a=1/(|x_1|+|y_1|)$.

Then it suffices to find the affine transformation $L$ that maps the rectangle (upper case coordinates $(X,Y)$) onto the square (lower case coordinates $(x,y)$):

$$L: \ \ \begin{cases}x&=&\dfrac{X-X_2}{2W}-\dfrac{Y-Y_2}{2H}\\ y&=&\dfrac{X-X_2}{2W}+\dfrac{Y-Y_2}{2H}\end{cases} (1a) \ \ \ \text{with} \ \ \ L^{-1}: \ \ \begin{cases}X&=&W(x+y)+X_2\\ Y&=&H(-x+y)+Y_2 \end{cases} (1b)$$

Remark: let us (partially) understand what $L^{-1}$ does: The $H$ and $W$ factors are there to do the appropriate scaling, the added $(X_2,Y_2)$ accounts for moving origin $(0,0)$ to the center of the rectangle; it remains to understand the mixture of coordinates with coefficients 1,1,-1,1; as you are in high school, you probably have not met yet the concept of matrix; in one or two years, you will see that this "means" a $+\pi/4$ rotation multiplied by $\sqrt{2}$.

Here is a Matlab program that implements all this (take care to the upper and lower case identifiers) :

W=4; % half width
H=2; % half height
X2=9;Y2=1; % coordinates of the rect. center
X1=5;Y1=-2; % coordinates of the exterior point
x1=(X1-X2)/(2*W)-(Y1-Y2)/(2*H); % formulas (1a)
y1=(X1-X2)/(2*W)+(Y1-Y2)/(2*H); % applied to (X,Y)=(X1,Y1)
a=1/(abs(x1)+abs(y1));
x3=a*x1;y3=a*y1;
X3=W*(x3+y3)+X2; % formulas (1b)
Y3=H*(-x3+y3)+Y2; % applied to (x,y)=(x3,y3)