# How to find the original coordinates of a point inside an irregular rectangle?

I'm a third year computer science student. I'm working on a project Data-show touch screen In schools classrooms.

I'll try to explain my problem as much as I can.

The project has three main components; A computer, a Data-show and a webcam.

The teacher will plug the data-show in the computer and the computer screen will appear on the wall of the classroom to all students.

The main purpose of the project is to turn the image of the screen displayed on the classroom wall into interactive screen; when the teacher tabs with his finger on an image of a Button displayed on the wall, the webcam that is connected to the computer will capture the position of the teacher's finger and find his (x,y) coordinates for a reference point on the wall, and raise a click event in the related (x,y) position on the screen.

The screen of the computer has two dimensions; Width->X and Height->Y. And for every point in the screen such as P, it could be located on the screen using two numbers (Px,Py), where Px is the distance between the point P and the left side of the screen, and Py is the distance between the point P and the top side of the screen. In other words, the reference for all points in the screen is the top left corner of the screen.

The data-show will display an irregular Quadrilateral shape of the screen on the wall. the shapes will not be regular squares or rectangles due to the angle that the teacher puts the data-show in. What I'm asking for are the equations that will calculate the (x,y) point on the screen that represents the (x,y) tapped point on the wall.

There is mainly four shapes the data-show may display on the wall. For each shape of them the only known things are the coordinates of the four angles(corners) of the quadrilateral shape.

# 1. an optimal rectangle

The displayed image on wall has a very low chance to shape an optimal rectangle, but it's the basic shape that could be formed.

Suppose that the red point P'(Px',Py') represents the coordinates of the place the teacher tapped on with his finger.

To get the original (Px,Py) coordinates from the point (Px',Py') on the wall, I can do the following.

1. Calculate the width->X' and the height->Y' of the displayed image by the law of distance between two points.

1. find the ratio between X&X', and between Y&Y'. I'll call the first ratio rx and the second ratio ry.

1. Multiply Px' by rx to get Px, and multiply Py' by ry to get Py.

# 2. an optimal trapezoidal.

The displayed image on wall could also shape an optimal trapezoidal. I asked some of my friends from the applied mathematics college to help me to find the two equations to find the original coordinates of the point, and they did some calculations and came out with these two equations;

In this shape

To find X:

and to find Y I can use the same way used in the rectangle; finding the ratio between Y and the height of the trapezoidal H.

My question is about this shape, the data-show in most times will shape an irregular shape. Imagine this shape like

None of the shape's lines is vertical or horizontal, all lines may have different lengths and they may have different angels from each other.

# My question is

I'm searching for equations that will find the original P(x,y) point of the point P'(X',Y'). Things I know are the coordinates of the points P1, P2, P3, P4, P'

What are those equations? and how are they derived?

• Looks like a perspective transformation might do the trick in the third case. If it does, it will also include the other two as special cases. – amd Mar 2 '16 at 21:40
• If I'm not mistaken, this requires knowledge aboutt how the projector looks. If we assume that your window fills the entire window of the projector and that it has a point like light source, it is fairly easy to work out the projection of a rectangle on a plane. – Étienne Bézout Mar 2 '16 at 21:46
• If I may, I would like to propose an alternative approach. When you set up the system, display say a hexagonal lattice with an appropriate lattice constant on the screen. Use the webcam to record the positions of the lattice points. Then turn off the lattice. When your teacher points at the screen, you could for example find the closest lattice point to his finger. Then you simply find the corresponding lattice point in your rectangular window on the computer. – Étienne Bézout Mar 2 '16 at 21:49
• I like Étienne’s suggestion of projecting some sort of grid as part of set-up. Since there’s going to be some amount of slop in the event coordinates anyway, returning the nearest grid point given a fine enough grid (or via some simple interpolation between grid points) will likely be good enough. – amd Mar 3 '16 at 21:55

If you want to code this up for yourself, it’s not terribly difficult to work out the necessary mapping. Without going into the detailed derivation, a general planar perspective transformation can be represented (in homogeneous coordinates) by a matrix of the form $$M=\pmatrix{m_{00} & m_{01} & m_{02} \\ m_{10} & m_{11} & m_{12} \\ m_{20} & m_{21} & 1},$$ which corresponds to the mapping \begin{align} x' &= {m_{00}x+m_{01}y+m_{02} \over m_{20}+m_{21}+1} \\ y' &= {m_{10}x+m_{11}y+m_{12} \over m_{20}+m_{21}+1}. \end{align} Given a set of corner-to-corner correspondences between a pair of quadrilaterals, the eight coefficients can by found by solving a system of linear equations.
If one of the quads is a rectangle aligned with the coordinate axes, this transformation can be built up in stages, which can be more convenient for implementation in software. Assuming that we have the matrix $A$ which maps from the unit square to the quadrilateral, the rectangle-to-quadrilateral transformation can be derived by composing it with suitable translation and scaling transformations: $$M = A\cdot S\left(\frac1w,\frac1h\right)\cdot T(-x_{LL},-y_{LL}).$$ The inverse map is then $$M^{-1}=T(x_{LL},y_{LL})\cdot S(w,h)\cdot A^{-1} = \pmatrix{w&0&x_{LL} \\ 0&h&y_{LL} \\ 0&0&1 }\cdot A^{-1},$$ where $(x_{LL},y_{LL})$ are the coordinates of the rectangle’s lower-left corner. Left-handed coordinate systems can be accommodated by throwing in the appropriate reflections, and skew rectangles can be dealt with by adding a rotation to the transformation cascade.
Now, it’s just a matter of finding the matrix $A$. Let the corners of the quadrilateral be given by the points $q_i'$, and map the corners of the unit square to them as follows: \begin{align} (0,0)&\mapsto q_0' \\ (1,0)&\mapsto q_1' \\ (0,1)&\mapsto q_2' \\ (1,1)&\mapsto q_3'. \end{align} Solving the resulting system of equations is tedious, but straightforward. One form of the solution is as follows: \begin{align} a_{00} &= a_{20}x_1'+\Delta x_{10} \\ a_{10} &= a_{20}y_1'+\Delta y_{10} \\ a_{20} &= {\omega(\Delta_{10},\Delta_{32})+\omega(\Delta_{20},\Delta_{32})-\omega(\Delta_{30},\Delta_{32}) \over \omega(\Delta_{31},\Delta_{32})} \\ a_{01} &= a_{21}x_2'+\Delta x_{20} \\ a_{11} &= a_{21}y_2'+\Delta y_{20} \\ a_{21} &= -{\omega(\Delta_{10},\Delta_{31})+\omega(\Delta_{20},\Delta_{31})-\omega(\Delta_{30},\Delta_{31}) \over \omega(\Delta_{31},\Delta_{32})} \\ a_{02} &= x_0' \\ a_{12} &= y_0', \\ \end{align} where $\Delta_{ij}=q_i'-q_j'$, $\Delta x_{ij}$ and $\Delta y_{ij}$ are the corresponding coordinate deltas, and $\omega$ is the symplectic form $\omega(\mathbf u, \mathbf v) = u_xv_y-u_yv_x$. (That this looks like a lot of cross products is no coincidence—there’s a geometric interpretation of the solution as the intersection of various planes.)
Since you’re mainly interested in mapping from a quadrilateral to a rectangle, it might be more efficient, and probably more computationally stable, to compute $A^{-1}$ directly from the corner coordinates. It’s similar to the solution for the other direction, but I’ll leave that calculation to you.