How to build a projective transformation matrix without third party libraries?

Question

Programming

Good afternoon.
I want to solve this problem, but I could not find an answer on how to build a projective transformation matrix without using third-party libraries (OpenGL, OpenCV, ...).
I read a lot of material on this topic, read an article on Habré .
The following problem:
Given: a regular quadrilateral and a square, which are given by their coordinates A(x1,y1), B(x2,y2), C(x3,y3), D(x4,y4) and M(0,0), N(1.0), P(1.1), K(0.1) respectively.
There is a point P(x,y) that is in this quadrilateral.
Required: Build a projective transformation matrix to transform ABCD into a square MNPK. Next, you need to find the position of the point P`(x`,y`) in the square.

Understood the principle of constructing such a matrix. I can't figure out how to implement the solution of a system of equations in code.
I would be grateful if you could suggest the right way to solve this problem.
I spent several days searching for a solution on the Internet, but the result is almost zero.

Answer 1

The easiest way is to first build a transformation matrix from a square to a quad, and then take the inverse.
We will write the plane points, as is customary in computer graphics, as lines: (xy 1) for a proper point and (xy 0) for an improper one. The string (c* c*yc) denotes the same point as (xy 1) (with c!=0).
Let the transformation matrix M=((a11 a12 a13) (a21 a22 a23) (a31 a32 a33)). A point (u,v) of a square goes to a point (x,y) of a quadrilateral if
(uv 1)*M=(c*xc*yc) holds for some c!=0.
Let's take the vertex (0,0) first. We
get a31=c1*x1, a32=c1*y1, a33=c1. It can be seen that we can take a33=c1=1 (the matrix is ​​also defined up to proportionality), and we have the last line:
a31=x1, a32=y1, a33=1.
Now let's substitute the rest of the vertices. We get 9 equations:
a11+x1=c2*x2
a12+y1=c2*y2
a13+1=c2
a11+a21+x1=c3*x3
a12+a22+y1=c3*y3
a13+a23+1=c3
a21+ x1=c4*x4
a22+y1=c4*y4
a23+1=c4
This is a quadratic system of 9 linear equations. It is easy to solve by the Gaussian method. And you can manually eliminate all variables except c2,c3,c4, get a system of 3 equations, solve with some Cramer method (via determinants) and restore a11,a12,...,a23.
Then calculate the matrix inverse to the constructed one. You can also use the determinants.

Answer 2