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 ?

enter image description here

  • $\begingroup$ I am programming a simple UI to visualize the problem, but It seem useless just visualizing. I've tried Pythagoras but I can't realize how to find more then one side of the triangle. $\endgroup$ – Splitlook Apr 2 '16 at 16:43
  • $\begingroup$ What is your level of study ? High school or University undergraduate ? $\endgroup$ – Jean Marie Apr 2 '16 at 16:48
  • $\begingroup$ I'm in high school. $\endgroup$ – Splitlook Apr 2 '16 at 16:52
  • $\begingroup$ What information do you have on the size of the rectangle? That knowledge is necessary. $\endgroup$ – Rory Daulton Apr 2 '16 at 16:57

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


Solve for $t$ and keep the smallest value among


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

  • $\begingroup$ Can you please express in a pseudo code ? $\endgroup$ – Splitlook Apr 2 '16 at 17:16
  • $\begingroup$ @Splitlook: sorry no, this is too trivial. Spend more effort. $\endgroup$ – Yves Daoust Apr 2 '16 at 17:17
  • $\begingroup$ Why using absolute if the coordinate system is from 0 to infinity? $\endgroup$ – Splitlook Apr 2 '16 at 17:24
  • $\begingroup$ After translation, it is not. $\endgroup$ – Yves Daoust Apr 2 '16 at 17:37

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)
X3=W*(x3+y3)+X2; % formulas (1b)
Y3=H*(-x3+y3)+Y2; % applied to (x,y)=(x3,y3)

enter image description here

  • 1
    $\begingroup$ @Yves Daoust I don't agree with your remark: there is an affine (not an isometric) transform from any square (what you call a diamond) to any rectangle. $\endgroup$ – Jean Marie Apr 2 '16 at 23:25
  • $\begingroup$ Could you say if the solution I have proposed is convenient for you ? $\endgroup$ – Jean Marie Apr 4 '16 at 0:54

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.