Normalized coordinate of point on 4-sided concave polygon

Question

Considering I have concave polygon made up of 4 points: P1, P2, P3, P4, and a point M which I already know is inside this polygon.

How would I go about determining its "normalized" position in an equivalent, non-deformed rectangle?

Here is an example with a grid which makes it easy to see "with the eyes".

I am trying to write an algorithm to calibrate a touch-screen which is projected on a possibly non-flat surface and I need to know what a point corresponds to on a rectangle.

Math is not exactly my strong, so I would love an analytical, ready-to-code solution to this math problem!

Answer 1

Well, that was hard, but I figured it out!

The answer by @Andrei was correct, but it only works for an affine transform, which consists of just scaling, translating, shearing and rotating. An affine transform means parallel lines remain parallel. This was not my case as you can see the quadrilateral is more akin to a perspective transform.

The key was that in the case of a non-affine transform, also known as a perspective transform, the transformation matrix $T$ is more complex. The terms $g$ and $h$ are non-zero. Also, the $x$ and $y$ coordinates of the resulting transformation needs to be divided by $z$:

$$p_r'=\begin{pmatrix}x_r\\y_r\\1\end{pmatrix}T=\begin{pmatrix}x'\\y'\\z'\end{pmatrix}$$ $$p_r=\begin{pmatrix}x\\y\\1\end{pmatrix}=\begin{pmatrix}x' \over z'\\y' \over z'\\1\end{pmatrix}$$

Where $p_r$ is the resulting point position after being transformed by the matrix (forward transform).

Now, what we want is to find the inverse transformation. The formula is quite similar

$$p_b'=p_r T^{-1}=\begin{pmatrix}x'\\y'\\z'\end{pmatrix}$$ $$p_b=\begin{pmatrix}x\\y\\1\end{pmatrix}=\begin{pmatrix}x' \over z'\\y' \over z'\\1\end{pmatrix}$$

Now the hard part is finding the coefficients for the transform matrix, since it has no zero element.

$$T=\begin{pmatrix}a_{11}& a_{12}& a_{13}\\a_{21}& a_{22}& a_{23}\\a_{31}& a_{32}& a_{33}\end{pmatrix}$$

Thanks to the paper linked below, I was able to find these coefficients rather easily (watch out, the interesting part has a few typos!): https://www.ldv.ei.tum.de/fileadmin/w00bfa/www/content_uploads/Vorlesung_3.2_SpatialTransformations.pdf

Considering $$P_1=\begin{pmatrix} x_1 \\y_1 \\0 \end{pmatrix}$$ $$P_2=\begin{pmatrix} x_2 \\y_2 \\0 \end{pmatrix}$$ $$P_3=\begin{pmatrix} x_3 \\y_3 \\0 \end{pmatrix}$$ $$P_4=\begin{pmatrix} x_4 \\y_4 \\0 \end{pmatrix}$$

are the 4 points of the quadrilateral in clockwise order (in the case of a "computer graphics" referential; in the case of a "mathematical" referential, the order would be anti-clockwise)

$$\Delta x_1=x_1 - x_2, \Delta x_2=x_3 - x_2, \Delta x_3=x_0 - x_1 + x_2 - x_3$$ $$\Delta y_1=y_1 - y_2, \Delta y_2=y_3 - y_2, \Delta y_3=y_0 - y_1 + y_2 - y_3$$

$$a_{13}={\begin{vmatrix} \Delta x_3& \Delta x_2\\ \Delta y_3& \Delta y_2 \end{vmatrix} \over \begin{vmatrix} \Delta x_1& \Delta x_2\\ \Delta y_1& \Delta y_2 \end{vmatrix}}$$

$$a_{23}={\begin{vmatrix} \Delta x_1& \Delta x_3\\ \Delta y_1& \Delta y_3 \end{vmatrix} \over \begin{vmatrix} \Delta x_1& \Delta x_2\\ \Delta y_1& \Delta y_2 \end{vmatrix}}$$

$$a_{11}=x_1-x_0+a_{13}x_1$$ $$a_{12}=y_1-y_0+a_{13}y_1$$ $$a_{21}=x_3-x_0+a_{23}x_3$$ $$a_{22}=y_3-y_0+a_{23}y_3$$ $$a_{31}=y_0$$ $$a_{32}=y_0$$ $$a_{33}=1$$

Then, it was just a matter of inversing this matrix and doing the operation I described above.

Here is a jsfiddle showing the process in action:

https://jsfiddle.net/floriansegginger/jm57pbzg/40/

Answer 2

You can write the transformation matrix from the final state (let's use a square of side $1$) to the stretched polygon as a 3x3 affine matrix $T$. You can read more about it on wikipedia. Look at the last image. The matrix has the form $$T=\begin{pmatrix}a& b& c\\d& e& f\\0& 0& 1\end{pmatrix}$$ For the coordinates you use a vector notation $$\begin{pmatrix}x\\y\\1\end{pmatrix}$$ Let's suppose that $P_1$ is the transform of $(0,0)$. Then $c=x_1$ and $f=y_1$. Then continue with $P_2$ as the transform of $(1,0)$. You get $$a+c=x_2\\d+f=y_2$$ or $$a=x_2-x_1\\d=y_2-y_1$$ You can work out the other matrix elements. Now we know that $$T\begin{pmatrix}x_r\\y_r\\1\end{pmatrix}=\begin{pmatrix}x_M\\y_M\\1\end{pmatrix}$$ You can now multiply on the left with $T^{-1}$ and you get $$\begin{pmatrix}x_r\\y_r\\1\end{pmatrix}=T^{-1}\begin{pmatrix}x_M\\y_M\\1\end{pmatrix}$$