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

Question

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.

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

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

3. an irregular quadrilateral.

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?

Answer 1

This is what the concept of a homography was invented for. You know the coordinates of the four corners on your screen and on the wall, and you want to find a transformation that maps from screen coordinates to wall coordinates. There will be a homography that maps between the two coordinate systems. So, your task is: given four points with known mappings, find a homography that is consistent with that.

If you're using OpenCV, see the findHomography() method, as well as warpPerspective().

Answer 2

1. If we look at simple example with rectangle: finding of Y coordinate of point P $\equiv$ finding straight line $L$ parallel to $OX$ to which point $P$ belongs.
2. In case of trapezoidal it's still true except that we can not say "parallel" and we will use more generic definition: we will be looking for some straight line $L$ which satisfy next conditions. $$ P \in L \\ \frac{AI}{AB}=\frac{DJ}{DC}=\alpha, \text{for some }0 \leq \alpha \leq 1 $$

3. In common case such "parallel" lines (actually such lines are parallel, but in 3d space and I think it can be proved by considering quadrangular pyramid cut) is that what we want to find. And actual you need to find such $\alpha$ that $$ F \in AB, \frac{AF}{AB} = \alpha \\ E \in DC, \frac{DE}{DC} = \alpha \\ P \in FE $$

4. One way is to use binary search on $\alpha$. Also I want to explicitly mention that you can find $X$ and $Y$ independently.

5. $O(1)$ solution:

   a. Coordinates of points $J$ and $F$ $$ \overline{OJ} = \overline{OD} + \alpha * \overline{DC}\\ \overline{OF} = \overline{OA} + \alpha * \overline{AB}\\ $$ b. By coordinates of $J$ and $F$ line equation can be composed: $$ Ax + By + C = 0$$ c. Suppose in previous equation $x=P_x, y=P_y$ and solve relatively to $\alpha$.